HEAVY-TRAFFIC EXTREME-VALUE LIMITS FOR QUEUES

We consider the maximum waiting time among the first n customers in th e GI/G/1 queue. We use strong approximations to prove, under regularit y conditions, convergence of the normalized maximum wait to the Gumbel extreme-value distribution when the traffic intensity rho approaches 1 from below and n approaches infinity at a suitable rate. The normali zation depends on the interarrival-time and service-time distributions only through their first two moments, corresponding to the iterated l imit in which first rho approaches 1 and then n approaches infinity. W e need n to approach infinity sufficiently fast so that n(1 - rho)(2) --> infinity. We also need n to approach infinity sufficiently slowly: If the service time has a pth moment for rho > 2, then it suffices fo r (1 - rho)n(1/p) to remain bounded; if the service time has a finite moment ting function, then it suffices to have (1 - rho)log n --> 0. T his limit can hold even when the normalized maximum waiting time fails to converge to the Gumbel distribution as n --> infinity for each fix ed rho. Similar limits hold for the queue-length process.