Home | Articles | Past volumes | About | Login | Notify | Contact | Search

 Large deviation asymptotics for busy periods
 Ken R. Duffy, Hamilton Institute, National University of Ireland Maynooth, IrelandSean P. Meyn, University of Florida

 Abstract The busy period for a queue is cast as the area swept under the random walk until it first returns to zero. Encompassing non-i.i.d. increments, the large-deviations asymptotics of the busy period $$B$$ is addressed, under the assumption that the increments satisfy standard conditions, including a negative drift. The main conclusions provide insight on the probability of a large busy period, and the manner in which this occurs. The scaled probability of a large busy period has the asymptote, for any $$b>0$$, \begin{align*} &\lim_{n\to\infty} \frac{1}{\sqrt{n}} \log P(B\geq bn) = -K\sqrt{b},\3pt] \hbox{where}\quad K = 2& \sqrt{-\int_0^{\lambda^*} \Lambda(\theta)\, d\theta}, \quad \hbox{with }\lambda^*=\sup\{\theta:\Lambda(\theta)\leq0\}, \end{align*} and with $$\Lambda$$ denoting the scaled cumulant generating function of the increments process. The most likely path to a large swept area is found to be a simple rescaling of the path on $$[0,1]$$ given by \[ \psi^*(t) = -\Lambda(\lambda^*(1-t))/\lambda^*. In contrast to the piecewise linear most likely path leading the random walk to hit a high level, this is strictly concave in general. While these two most likely paths have distinctly different forms, their derivatives coincide at the start of their trajectories, and at their first return to zero. These results partially answer an open problem of Kulick and Palmowski [18] regarding the tail of the work done during a busy period at a single server queue. The paper concludes with applications of these results to the estimation of the busy period statistics $$(\lambda^*, K)$$ based on observations of the increments, offering the possibility of estimating the likelihood of a large busy period in advance of observing one. AMS 2000 subject classifications: Primary 60K25; secondary 60F10Keywords: Integrated random walks, busy periods, large deviations, sample paths
 Full Text: PDF
Duffy, Ken R., Meyn, Sean P., Large deviation asymptotics for busy periods, Stochastic Systems, 4, (2014), 300-319 (electronic). DOI: 10.1214/13-SSY098.

References

[1]     Anantharam, V. (1989). How large delays build up in a GI∕G∕1 queue. Queueing Systems Theory Appl. 5 345–367. MR1030475

[2]     Blanchet, J., Glynn, P. and Meyn, S. (2013). Large deviations for the empirical mean of an M∕M∕1 queue. Queueing Syst. 73 425–446. MR3036010

[3]     Borovkov, A. A., Boxma, O. J. and Palmowski, Z. (2003). On the integral of the workload process of the single server queue. J. Appl. Probab. 40 200–225. MR1953775

[4]     Borovkov, A. A. and Sahanenko, A. I. (1973). Remarks on the convergence of random processes in nonseparable metric spaces and on the nonexistence of a Borel measure for processes in C(0,). Teor. Verojatnost. i Primenen. 18 812–815. MR0328984

[5]     Dembo, A. and Zajic, T. (1995). Large deviations: from empirical mean and measure to partial sums. Stoch. Proc. Appl. 57 191–224. MR1334969

[6]     Dembo, A. and Zeitouni, O. (1998). Large Deviation Techniques and Applications. Springer. MR1619036

[7]     Deuschel, J. D. and Stroock, D. W. (1989). Large Deviations 137. Academic Press Inc. MR0997938

[8]     Duffield, N. G., Lewis, J. T., O’Connell, N., Russell, R. and Toomey, F. (1995). Entropy of ATM traffic streams: a tool for estimating QoS parameters. IEEE J. Sel. Area Comm. 13 981–990.

[9]     Duffy, K., Lewis, J. T. and Sullivan, W. G. (2003). Logarithmic asymptotics for the supremum of a stochastic process. Ann. Appl. Probab. 13 430–445. MR1970270

[10]     Duffy, K. and Metcalfe, A. P. (2005). The large deviations of estimating rate functions. J. Appl. Probab. 42 267–274. MR2144909

[11]     Duffy, K. R. and Malone, D. (2008). Logarithmic asymptotics for a single-server processing distinguishable sources. Math. Methods Oper. Res. 68 509–537. MR2457294

[12]     Duffy, K. R. and Meyn, S. P. (2010). Most likely paths to error when estimating the mean of a reflected random walk. Perform. Evaluation 67 1290–1303.

[13]     Duffy, K. R. and Meyn, S. P. (2010). Estimating Loynes’ exponent. Queueing Syst. 68 285–293. MR2834199

[14]     Ganesh, A., O’Connell, N. and Wischik, D. (2004). Big Queues. Lecture Notes in Mathematics 1838. Springer-Verlag, Berlin. MR2045489

[15]     Ganesh, A. J. and O’Connell, N. (2002). A large deviation principle with queueing applications. Stoch. Stoch. Rep. 73 25–35. MR1914976

[16]     Glynn, P. and Whitt, W. (1994). Logarithmic asymptotics for steady-state tail probabilities in a single-server queue. J. Appl. Probab. 31A 413–430. MR1274722

[17]     Kontoyiannis, I. and Meyn, S. P. (2005). Large deviations asymptotics and the spectral theory of multiplicatively regular Markov processes. Electron. J. Probab. 10 no. 3, 61–123 (electronic). MR2120240

[18]     Kulik, R. and Palmowski, Z. (2011). Tail behaviour of the area under a random process, with applications to queueing systems, insurance and percolations. Queueing Syst. 68 275–284. MR2834198

[19]     Lelarge, M. (2008). Tail asymptotics for discrete event systems. Discrete Event Dyn. Syst. 18 563–584. MR2443657

[20]     Majewski, K. (2000). Single class queueing networks with discrete and fluid customers on the time interval . Queueing Syst. 36 405–435. MR1823977

[21]     Meyn, S. P. (2008). Control Techniques for Complex Networks. Cambridge University Press. MR2372453

[22]     Müller, D. W. (1968). Verteilungs-Invarianzprinzipien für das starke Gesetz der grossen Zahl. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 10 173–192. MR0232428

[23]     Puhalskii, A. (1995). Large deviation analysis of the single server queue. Queueing Syst. 21 5–66. MR1372048

[24]     Riesz, F. and Nagy, B. S. (1955). Functional Analysis. Blackie and Son Limited.

[25]     Rockafellar, R. T. and Wets, R. J. B. (1998). Variational Analysis. Springer. MR1491362

[26]     Whitt, W. (1972). Stochastic Abelian and Tauberian theorems. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 22 251–267. MR0339326

[27]     Whitt, W. (2002). Stochastic-Process Limits. Springer-Verlag, New York. MR1876437

[28]     Wischik, D. J. (2001). Sample path large deviations for queues with many inputs. Ann. Appl. Probab. 11 379–404. MR1843050

Home | Articles | Past volumes | About | Login | Notify | Contact | Search

Stochastic Systems. ISSN: 1946-5238