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)

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 Q(infty) 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.