Abstract
Loynes’ distribution, which characterizes the one dimensional marginal of the stationary solution to Lindley’s recursion, possesses an ultimately exponential tail for a large class of increment processes. If one can observe increments but does not know their probabilistic properties, what are the statistical limits of estimating the tail exponent of Loynes’ distribution? We conjecture that in broad generality a consistent sequence of non-parametric estimators can be constructed that satisfies a large deviation principle. We present rigorous support for this conjecture under restrictive assumptions and simulation evidence indicating why we believe it to be true in greater generality.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Attouch, H., Wets, R.J.-B.: A convergence theory for saddle functions. Trans. Am. Math. Soc. 280(1), 1–41 (1983)
Attouch, H., Wets, R.J.-B.: Isometries for the Legendre–Fenchel transform. Trans. Am. Math. Soc. 296(1), 33–60 (1986)
Baccelli, F., Kauffmann, B., Veitch, D.: Inverse problems in queueing theory and Internet probing. Queueing Syst. 63(1–4), 59–107 (2009)
Berger, A.W., Whitt, W.: Maximum values in queueing processes. Probab. Eng. Inf. Sci. 9(3), 375–409 (1995)
Courcoubetis, C., Kesidis, G., Ridder, A., Walrand, J., Weber, R.: Admission control and routing in ATM networks using inferences from measured buffer occupancy. IEEE Trans. Commun. 43(2–4), 1778–1784 (1994)
Dembo, A., Zeitouni, O.: Large Deviation Techniques and Applications. Springer, Berlin (1998)
Duffield, N.G., O’Connell, N.: Large deviations and overflow probabilities for the general single server queue, with applications. Math. Proc. Camb. Philos. Soc. 118(2), 363–374 (1995)
Duffield, N.G., Lewis, J.T., O’Connell, N., Russell, R., Toomey, F.: Entropy of ATM traffic streams: a tool for estimating QoS parameters. IEEE J. Sel. Areas Commun. 13(6), 981–990 (1995)
Duffy, K., Metcalfe, A.P.: The large deviations of estimating rate functions. J. Appl. Probab. 42(1), 267–274 (2005)
Duffy, K.R., Meyn, S.P.: Most likely paths to error when estimating the mean of a reflected random walk. Perform. Eval. 67(12), 1290–1303 (2010)
Duffy, K.R., Sapozhnikov, A.: The large deviation principle for the on–off Weibull sojourn process. J. Appl. Probab. 45(1), 107–117 (2008)
Duffy, K., Lewis, J.T., Sullivan, W.G.: Logarithmic asymptotics for the supremum of a stochastic process. Ann. Appl. Probab. 13(2), 430–445 (2003)
Ganesh, A.J.: Bias correction in effective bandwidth estimation. Perform. Eval. 27(8), 319–330 (1996)
Ganesh, A.J., O’Connell, N.: A large-deviation principle for Dirichlet posteriors. Bernoulli 6(6), 1021–1034 (2000)
Ganesh, A., Green, P., O’Connell, N., Pitts, S.: Bayesian network management. Queueing Syst. Theory Appl. 28(1–3), 267–282 (1998)
Glynn, P., Whitt, W.: Logarithmic asymptotics for steady-state tail probabilities in a single-server queue. J. Appl. Probab. 31A, 413–430 (1994)
Hall, P., Teugels, J.L., Vanmarcke, A.: The abscissa of convergence of the Laplace transform. J. Appl. Probab. 29(2), 353–362 (1992)
Horn, R.A., Johnson, C.R.: Topics in Matrix Analysis. Cambridge University Press, Cambridge (1991)
Kauffmann, B., Baccelli, F., Veitch, D.: Towards multihop available bandwidth estimation. ACM SIGCOMM Comput. Commun. Rev. 37(2), 83–84 (2009)
Lelarge, M.: Tail asymptotics for discrete event systems. Discrete Event Dyn. Syst. 18(4), 563–584 (2008)
Lindley, D.V.: The theory of queues with a single server. Proc. Camb. Philos. Soc. 48, 277–289 (1952)
Loynes, R.M.: The stability of a queue with non-independent inter-arrival and service times. Proc. Camb. Philol. Soc. 58, 497–520 (1962)
Mandjes, M., van de Meent, R.: Resource dimensioning through buffer sampling. IEEE/ACM Trans. Netw. 17(5), 1631–1644 (2009)
Meyn, S.P.: Control Techniques for Complex Networks. Cambridge University Press, Cambridge (2008)
Nagaev, S.V.: Large deviations of sums of independent random variables. Ann. Probab. 7(5), 745–789 (1979)
Paschalidis, I.Ch., Vassilaras, S.: On the estimation of buffer overflow probabilities from measurements. IEEE Trans. Inf. Theory 47(1), 178–191 (2001)
Pitts, S.M.: Nonparametric estimation of the stationary waiting time distribution function for the GI/G/1 queue. Ann. Stat. 22(3), 1428–1446 (1994)
Puhalskii, A.: Large deviation analysis of the single server queue. Queueing Syst. 21(1–2), 5–66 (1995)
Zeevi, A., Glynn, P.W.: Estimating tail decay for stationary sequences via extreme values. Adv. Appl. Probab. 36(1), 198–226 (2004)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Duffy, K.R., Meyn, S.P. Estimating Loynes’ exponent. Queueing Syst 68, 285–293 (2011). https://doi.org/10.1007/s11134-011-9245-y
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11134-011-9245-y