Large Deviations for the Empirical Mean of an M/M/1 Queue

J. Blanchet , P. W. Glynn, and S. Meyn

Queueing Systems: Theory and Applications, Vol 73, No. 4, 425-446 (2013)

BlanchetGMeyn13.pdf

Let (Q(k):kgeq 0) be an M/M/1 queue with traffic intensity rho in(0,1) . Consider the quantity

$S_n(p) = frac{1}{n} sum_{j=1}^n Q(j)^p$

for any p>0 . The ergodic theorem yields that S_n(p)to mu(p):= E[Q(infty)p] , where is geometrically distributed with mean rho/(1-rho) . It is known that one can explicitly characterize I(epsilon)>0 such that

$lim_{nto infty} frac{1}{n} log Pbig(S_n(p) < mu(p) - epsilonbig) = -I(epsilon), quad epsilon > 0$

In this paper, we show that the approximation of the right tail asymp-totics requires a different logarithm scaling, giving

$lim_{nto infty} frac{1}{n^{1/(1+p)}} log P(S_n(p) > mu (p) + epsilon) = - C(p) epsilon^{1/(1+p)},$

where C(p)>0 is obtained as the solution of a variational problem.

We discuss why this phenomenon — Weibullian right tail asymptotics rather than exponential asymptotics — can be expected to occur in more general queueing systems.