Large Deviations for the Empirical Mean of an M/M/1 Queue (with P. Glynn and S. Mean).

Summary:

This paper was started during the Newton Institute activity on Stochastic Networks in 2010, after Sean Meyn described this as an open problem. The theory that Donsker and Varadhan developed in the seventies allows computing large deviations for the empirical mean of functions of a Markov chain (i.e. Markov random walks). The results look qualitatively much like the i.i.d. case. Namely, large deviations of order $n$ away from the steady-state mean of $n$ summands has a probability that decreases exponentially in $n$ and with a rate that is the Legendre transform of an associated (asymptotic) logarithmic moment generating function. When one relaxes the assumptions of the Donsker-Varadhan one obtains a completely different behavior, which can be explained by heavy-tailed large deviations intuition.

We illustrate this in the setting of an M/M/1 queue. Suppose that {Q_k : k>=0} is the queue length process and consider the Markov random walk S_n = Q_1 + … + Q_n, starting say from Q_0 = 0. We know that S_n / n converges to $mu$ (computable as the mean of a suitable geometric r.v. but this is unimportant). What is the large deviations behavior of P(S_n > n*a) for a > $mu$ ? The answer is given in the paper. The idea is to note that S_n is just the area drawn under the queue length process up to time $n$. To obtain a deviation of size $n$ one just needs a busy period that is of length $n^1/2$, which will yield fluctuations of order $n^1/2$ and thus a total area of order $n$. The area in a busy period is then Weibullian with shape parameter ½ and thus, breaking the calculation in busy periods we see that, by the “principle of the single large jump” for heavy-tailed large deviations (which is verified in the current setting in logarithmic scale in this paper), the most likely way in which S_n > n*a is that most of the time the queue length behaves “regularly” and there is a single big busy period of order n^1/2 that causes the large deviation. We abstract in this paper the features that cause this type of behavior that we expect will be seen in more general queueing problems.

Bibtex:

@Article{BlaGlyMe11,

author = { J. Blanchet and P. Glynn and S. Meyn},

title = {Large deviations for the empirical mean of an M/M/1 queue},

journal = { Queueing Systems: Theory and Applications},

year = {2013},

volume = {73},

pages = {425-446}

}