Heavy-Traffic Extreme-Value Limits for Queues

P. W. Glynn and W.Whitt

Operations Research Letters, Vol. 18, 107-111 (1995)

We consider the maximum waiting time among the first n customers in the GI/G/1 queue. We use strong approximations to prove, under regularity conditions, convergence of the normalized maximum wait to the Gumbel extreme-value distribution when the traffic intensity ρ approaches 1 from below and n approaches infinity at a suitable rate. The normalization depends on the interarrival-time and service-time distributions only through their first two moments, corresponding to the iterated limit in which first ρ approaches 1 and then n approaches infinity. We need n to approach infinity sufficiently fast so that n(1-ρ)2->∞. We also need n to approach infinity sufficiently slowly: If the service time has a pth moment for ρ>2, then it suffices for (1-ρ)n1/p to remain bounded; if the service time has a finite moment generating function, then it suffices to have (1-ρ)logn->0. This limit can hold even when the normalized maximum waiting time fails to converge to the Gumbel distribution as n->∞ for each fixed ρ. Similar limits hold for the queue length process.