Sojourn time asymptotics in the M/G/1 processor sharing queue

We show for the M/G/1 processor sharing queue that the service time distribution is regularly varying of index -ν, ν non-integer, iff the sojourn time distribution is regularly varying of index -ν. This result is derived from a new expression for the Laplace–Stieltjes transform of the sojourn time distribution. That expression also leads to other new properties for the sojourn time distribution. We show how the moments of the sojourn time can be calculated recursively and prove that the kth moment of the sojourn time is finite iff the kth moment of the service time is finite. In addition, we give a short proof of a heavy traffic theorem for the sojourn time distribution, prove a heavy traffic theorem for the moments of the sojourn time, and study the properties of the heavy traffic limiting sojourn time distribution when the service time distribution is regularly varying. Explicit formulas and multiterm expansions are provided for the case that the service time has a Pareto distribution. This revised version was published online in June 2006 with corrections to the Cover Date.     

Measure-valued Markov branching processes conditioned on non-extinction

We consider a particular class of measure-valued Markov branching processes that are constructed as “superprocesses” over some underlying Markov process. Such a processX dies out almost surely, so we introduce various conditioning schemes which keepX alive at large times. Under suitable hypotheses, which include the convergence of the semigroup for the underlying process to some limiting probability measureν, we show that the conditional distribution oft ⁻¹ X _t converges to that ofZν ast → ∞, whereZ is some strictly positive, real random variable. Research supported in part by NSF grant DMS 8701212. Research supported in part by an NSERC operating grant.     

Brownian bridge on hyperbolic spaces and on homogeneous trees

Let B be the Brownian motion on a noncompact non Euclidean rank one symmetric space H. A typical examples is an hyperbolic space H _n , n > 2. For ν > 0, the Brownian bridge B ^(ν) of length ν on H is the process B _t , 0 ≤t≤ν, conditioned by B ₀ = B _ν = o, where o is an origin in H. It is proved that the process converges weakly to the Brownian excursion when ν→ + ∞ (the Brownian excursion is the radial part of the Brownian Bridge on ℝ³). The same result holds for the simple random walk on an homogeneous tree. Received: 4 December 1998 / Revised version: 22 January 1999     

Metrizability and Coconnectedness

Solving the problem stated in Sichler and Trnková, Topol. Its Appl., 142: 159–179, 2004, we construct metrics μ, ν on a set P such that the spaces X=(P,μ) and Y=(P,ν) have the same monoid of all continuous selfmaps, the space Y is coconnected (in the sense that every continuous map Y×Y→Y depends on at most one coordinate) while X is not. Also, properties of the forgetful functors Metr → Unif → Top are investigated for the “simultaneous variant” of the above problem. Supported by the Grant Agency of Czech Republic under grant 201/06/0664 and by the project of Ministry of Education of Czech Republic MSM 0021620839.     

Transient phenomena for random walks in the absence of the expected value of jumps

Let ξ, ξ₁, ξ₂, ... be independent identically distributed random variables, and S _n :=Σ _j=1 ⁿ ,ξ _j , $ \bar S $ \bar S := sup _n≥0 S _n . If Eξ = −a < 0 then we call transient those phenomena that happen to the distribution $ \bar S $ \bar S as a → 0 and $ \bar S $ \bar S tends to infinity in probability. We consider the case when Eξ fails to exist and study transient phenomena as a → 0 for the following two random walk models:

How large delays build up in a GI/G/1 queue

LetW _k denote the waiting time of customerk, k 0, in an initially empty GI/G/1 queue. Fixa> 0. We prove weak limit theorems describing the behaviour ofW _k /n, 0kn, given W_n >na. LetX have the distribution of the difference between the service and interarrival distributions. We consider queues for which Cramer type conditions hold forX, and queues for whichX has regularly varying positive tail.The results can also be interpreted as conditional limit theorems, conditional on large maxima in the partial sums of random walks with negative drift.Research supported by the NSF under Grant NCR 8710840 and under the PYI Award NCR 8857731.     

Heavy Tails in Multi-Server Queue

In this paper, the asymptotic behaviour of the distribution tail of the stationary waiting time W in the GI/GI/2 FCFS queue is studied. Under subexponential-type assumptions on the service time distribution, bounds and sharp asymptotics are given for the probability P{W > x}. We also get asymptotics for the distribution tail of a stationary two-dimensional workload vector and of a stationary queue length. These asymptotics depend heavily on the traffic load. AMS subject classification: 60K25     

Asymptotic behaviour of the tandem queueing system with identical service times at both queues

Consider a tandem queue consisting of two single-server queues in series, with a Poisson arrival process at the first queue and arbitrarily distributed service times, which for any customer are identical in both queues. For this tandem queue, we relate the tail behaviour of the sojourn time distribution and the workload distribution at the second queue to that of the (residual) service time distribution. As a by-result, we prove that both the sojourn time distribution and the workload distribution at the second queue are regularly varying at infinity of index 1−ν, if the service time distribution is regularly varying at infinity of index −ν (ν>1). Furthermore, in the latter case we derive a heavy-traffic limit theorem for the sojourn time S ⁽²⁾ at the second queue when the traffic load ρ↑ 1. It states that, for a particular contraction factor Δ (ρ), the contracted sojourn time Δ (ρ) S ⁽²⁾ converges in distribution to the limit distribution H(·) as ρ↑ 1 where .     

Impact of Bursty Traffic on Queues

The impact of bursty traffic on queues is investigated in this paper. We consider a discrete-time single server queue with an infinite storage room, that releases customers at the constant rate of c customers/slot. The queue is fed by an M/G/∞ process. The M/G/∞ process can be seen as a process resulting from the superposition of infinitely many ‘sessions’: sessions become active according to a Poisson process; a station stays active for a random time, with probability distribution G, after which it becomes inactive. The number of customers entering the queue in the time-interval [t, t + 1) is then defined as the number of active sessions at time t (t = 0,1, ...) or, equivalently, as the number of busy servers at time t in an M/G/∞ queue, thereby explaining the terminology. The M/G/∞ process enjoys several attractive features: First, it can display various forms of dependencies, the extent of which being governed by the service time distribution G. The heavier the tail of G, the more bursty the M/G/∞ process. Second, this process arises naturally in teletraffic as the limiting case for the aggregation of on/off sources [27]. Third, it has been shown to be a good model for various types of network traffic, including telnet/ftp connections [37] and variable-bit-rate (VBR) video traffic [24]. Last but not least, it is amenable to queueing analysis due to its very strong structural properties. In this paper, we compute an asymptotic lower bound for the tail distribution of the queue length. This bound suggests that the queueing delays will dramatically increase as the burstiness of the M/G/∞ input process increases. More specifically, if the tail of G is heavy, implying a bursty input process, then the tail of the queue length will also be heavy. This result is in sharp contrast with the exponential decay rate of the tail distribution of the queue length in presence of ‘non-bursty’ traffic (e.g. Poisson-like traffic). This revised version was published online in August 2006 with corrections to the Cover Date.     

Uniform in bandwidth consistency of kernel estimators of the tail index

We consider a class of kernel estimators [^(t)]_n,h\hat{\tau}_{n,h} of the tail index of a Pareto-type distribution, which generalizes and includes the classical Hill estimator [^(a)]_n,k\hat{a}_{n,k}. It is well-known that [^(a)]_n,k\hat{a}_{n,k} is a consistent estimator of the tail index if and only if k→ ∞ and k/n→0. Under suitable assumptions on the kernel, [^(t)] _n,h\hat{\tau} _{n,h} is consistent whenever the bandwidth is taken to be a sequence of non-random numbers satisfying h _n →0 and nh _n → ∞. We extend this result and prove the consistency uniformly over a certain range of bandwidths. This permits the treatment of estimators of the tail index based upon data-dependent bandwidths, which are often used in practice. In the process, we establish a uniform in bandwidth result for kernel-type regression estimators with a fixed design, which will likely be of separate interest.     

Delay moments for FIFO GI/GI/s queues

For stable FIFO GI/GI/s queues, s ≥ 2, we show that finite (k+1)st moment of service time, S, is not in general necessary for finite kth moment of steady-state customer delay, D, thus weakening some classical conditions of Kiefer and Wolfowitz (1956). Further, we demonstrate that the conditions required for E[D ^k]<∞ are closely related to the magnitude of traffic intensity ρ (defined to be the ratio of the expected service time to the expected interarrival time). In particular, if ρ is less than the integer part of s/2, then E[D] < ∞ if E[S^3/2]<∞, and E[D^k]<∞ if E[S^k]<∞, ^k≥ 2. On the other hand, if s-1 < ρ < s, then E[D^k]<∞ if and only if E[S^k+1]<∞, k ≥ 1. Our method of proof involves three key elements: a novel recursion for delay which reduces the problem to that of a reflected random walk with dependent increments, a new theorem for proving the existence of finite moments of the steady-state distribution of reflected random walks with stationary increments, and use of the classic Kiefer and Wolfowitz conditions. This revised version was published online in June 2006 with corrections to the Cover Date.     

A heavy-traffic analysis of a closed queueing system with a GI/∞ service center

This paper studies the heavy-traffic behavior of a closed system consisting of two service stations. The first station is an infinite server and the second is a single server whose service rate depends on the size of the queue at the station. We consider the regime when both the number of customers, n, and the service rate at the single-server station go to infinity while the service rate at the infinite-server station is held fixed. We show that, as n→∞, the process of the number of customers at the infinite-server station normalized by n converges in probability to a deterministic function satisfying a Volterra integral equation. The deviations of the normalized queue from its deterministic limit multiplied by √n converge in distribution to the solution of a stochastic Volterra equation. The proof uses a new approach to studying infinite-server queues in heavy traffic whose main novelty is to express the number of customers at the infinite server as a time-space integral with respect to a time-changed sequential empirical process. This gives a new insight into the structure of the limit processes and makes the end results easy to interpret. Also the approach allows us to give a version of the classical heavy-traffic limit theorem for the G/GI/∞ queue which, in particular, reconciles the limits obtained earlier by Iglehart and Borovkov. This revised version was published online in June 2006 with corrections to the Cover Date.     

C-semigroups and strongly continuous semigroups

We show that, whenA generates aC-semigroup, then there existsY such that [M(C)] →Y →X, andA| _Y , the restriction ofA toY, generates a strongly continuous semigroup, where ↪ means “is continuously embedded in” and ‖x‖_[Im(C)]≡‖C ⁻¹ x‖. There also existsW such that [C(W)] →X →W, and an operatorB such thatA=B| _X andB generates a strongly continuous semigroup onW. If theC-semigroup is exponentially bounded, thenY andW may be chosen to be Banach spaces; in general,Y andW are Frechet spaces. If ρ(A) is nonempty, the converse is also true. We construct fractional powers of generators of boundedC-semigroups. We would like to thank R. Bürger for sending preprints, and the referee for pointing out reference [37]. This research was supported by an Ohio University Research Grant.     

Sharp estimation of the almost-sure Lyapunov exponent for the Anderson model in continuous space

In this article we study the exponential behavior of the continuous stochastic Anderson model, i.e. the solution of the stochastic partial differential equation u(t,x)=1+∫₀^tκΔ_xu (s,x) ds+∫₀^t W(ds,x) u (s,x), when the spatial parameter x is continuous, specifically x∈R, and W is a Gaussian field on R₊×R that is Brownian in time, but whose spatial distribution is widely unrestricted. We give a partial existence result of the Lyapunov exponent defined as lim_t→∞t⁻¹ log u(t,x). Furthermore, we find upper and lower bounds for lim sup_t→∞t⁻¹ log u(t,x) and lim inf_t→∞t⁻¹ log u(t,x) respectively, as functions of the diffusion constant κ which depend on the regularity of W in x. Our bounds are sharper, work for a wider range of regularity scales, and are significantly easier to prove than all previously known results. When the uniform modulus of continuity of the process W is in the logarithmic scale, our bounds are optimal. This author's research partially supported by NSF grant no. : 0204999     

Sharp stability results for almost conformal maps in even dimensions

Let Ω, ⊂R ⁿ and n ≥ 4 be even. We show that if a sequence {u^j} in W^1,n/2(Ω;R ⁿ) is almost conformal in the sense that dist (∇u^j,R ⁺SO(n)) converges strongly to 0 in L^n/2 and if u^j converges weakly to u in W^1,n/2, then u is conformal and ∇u^j → ∇u strongly in L _loc ^q for all 1 < -q < n/2. It is known that this conclusion fails if n/2 is replaced by any smaller exponent p. We also prove the existence of a quasiconvex function f(A) that satisfies 0 ≤ f(A) ≤ C (1 + |A|^n/2) and vanishes exactly onR ⁺ SO(n). The proof of these results involves the Iwaniec-Martin characterization of conformal maps, the weak continuity and biting convergence of Jacobians, and the weak-L¹ estimates for Hodge decompositions.     

Regularly varying tail of the waiting time distribution in M/G/1 retrial queue

We consider an M/G/1 retrial queue where the service time distribution has a regularly varying tail with index −β, β>1. The waiting time distribution is shown to have a regularly varying tail with index 1−β, and the pre-factor is determined explicitly. The result is obtained by comparing the waiting time in the M/G/1 retrial queue with the waiting time in the ordinary M/G/1 queue with random order service policy.     

On a class of nonlinear integral equations

In this paper we consider abstract equations of the typeK _ν ν +ν =w ₀, in a closed convex subset of a separable Hilbert spaceH. For eachv in the closed convex subset,K _v :H →H is a bounded linear map. As an application of our abstract result we obtain an existence result for nonlinear integral equations of the typeν(s)+ν(s)∫ ₀ ¹ k(s,t)ν(t)dt =W ₀(s) in the spaceL ² [0,1].     

Unique ergodicity of flows on homogeneous spaces

LetG be a unimodular Lie group, Γ a co-compact discrete subgroup ofG and ‘a’ a semisimple element ofG. LetT _a be the mapgΓ →ag Γ:G/Γ →G/Γ. The following statements are pairwise equivalent: (1) (T _a, G/Γ,θ) is weak-mixing. (2) (T _a, G/Γ) is topologically weak-mixing. (3) (G ^u, G/Γ) is uniquely ergodic. (4) (G ^u, G/Γ,θ) is ergodic. (5) (G ^u, G/Γ) is point transitive. (6) (G ^u, G/Γ) is minimal. If in additionG is semisimple with finite center and no compact factors, then the statement “(T _a, G/Γ,θ) is ergodic” may be added to the above list. The authors were partially supported by NSF grant MCS 75-05250.     

One-sided local large deviation and renewal theorems in the case of infinite mean

Summary. If {S _n ,n≧0} is an integer-valued random walk such that S _n /a _n converges in distribution to a stable law of index α∈ (0,1) as n→∞, then Gnedenko’s local limit theorem provides a useful estimate for P{S _n =r} for values of r such that r/a _n is bounded. The main point of this paper is to show that, under certain circumstances, there is another estimate which is valid when r/a _n → +∞, in other words to establish a large deviation local limit theorem. We also give an asymptotic bound for P{S _n =r} which is valid under weaker assumptions. This last result is then used in establishing some local versions of generalized renewal theorems. Received: 9 August 1995 / In revised form: 29 September 1996