×
Olvera-Cravioto, Mariana; Blanchet, Jose; Glynn, Peter

On the transition from heavy traffic to heavy tails for the \(M/G/1\) queue: the regularly varying case. (English) Zbl 1216.41033

Ann. Appl. Probab. 21, No. 2, 645-668 (2011).
Summary: Two of the most popular approximations for the distribution of the steady-state waiting time \(W_\infty\) of the \(M/G/1\) queue are the so-called heavy-traffic approximation and heavy-tailed asymptotic, respectively. If the traffic intensity \(\rho\) is close to 1 and the processing times have finite variance, the heavy-traffic approximation states that the distribution of \(W_\infty\) is roughly exponential at scale \(O((1-\rho)^{-1})\), while the heavy tailed asymptotic describes the power law decay in the tail of the distribution of \(W_\infty\) for a fixed traffic intensity. In this paper, we assume a regularly varying processing time distribution and obtain a sharp threshold in terms of the tail value, or equivalently, in terms of \((1-\rho)\), that describes the point at which the tail behavior transitions from the heavy-traffic regime to the heavy-tailed asymptotic. We also provide new approximations that are either uniform in the traffic intensity, or uniform on the positive axis, that avoid the need to use different expressions on the two regions defined by the threshold.

Cited in 10 Documents

MSC:

41A60 Asymptotic approximations, asymptotic expansions (steepest descent, etc.)
60F10 Large deviations
60F05 Central limit and other weak theorems
60G10 Stationary stochastic processes
60G50 Sums of independent random variables; random walks

Keywords:

\(M/G/1\) queue; heavy traffic; heavy tails; uniform approximations; large deviations
PDF BibTeX XML Cite
\textit{M. Olvera-Cravioto} et al., Ann. Appl. Probab. 21, No. 2, 645--668 (2011; Zbl 1216.41033)
Full Text: DOI arXiv

References:

[1] Abate, J., Choudhury, G. L. and Whitt, W. (1995). Exponential approximations for tail probabilities in queues. I. Waiting times. Oper. Res. 43 885-901. JSTOR: · Zbl 0841.60076
[2] Asmussen, S. (2003). Applied Probability and Queues , 2nd ed. Applications of Mathematics ( New York ) 51 . Springer, New York. · Zbl 1029.60001
[3] Asmussen, S. and Kroese, D. P. (2006). Improved algorithms for rare event simulation with heavy tails. Adv. in Appl. Probab. 38 545-558. · Zbl 1097.65017
[4] Baccelli, F. and Foss, S. (2004). Moments and tails in monotone-separable stochastic networks. Ann. Appl. Probab. 14 612-650. · Zbl 1048.60067
[5] Baccelli, F., Schlegel, S. and Schmidt, V. (1999). Asymptotics of stochastic networks with subexponential service times. Queueing Systems Theory Appl. 33 205-232. · Zbl 0997.60112
[6] Bingham, N. H., Goldie, C. M. and Teugels, J. L. (1987). Regular Variation. Encyclopedia of Mathematics and Its Applications 27 . Cambridge Univ. Press, Cambridge. · Zbl 0617.26001
[7] Blanchet, J. and Glynn, P. (2007). Uniform renewal theory with applications to expansions of random geometric sums. Adv. in Appl. Probab. 39 1070-1097. · Zbl 1132.60060
[8] Blanchet, J., Glynn, P. and Lam, H. (2010). Cramer-Lundberg approximations in the absence of exponential moments: A heavy-traffic perspective.
[9] Borovkov, A. A. (2000). Estimates for the distribution of sums and maxima of sums of random variables when the Cramér condition is not satisfied. Sibirsk. Mat. Zh. 41 997-1038. · Zbl 0969.60047
[10] Borovkov, A. A. and Borovkov, K. A. (2008). Asymptotic Analysis of Random Walks. Encyclopedia of Mathematics and Its Applications 118 . Cambridge Univ. Press, Cambridge. · Zbl 1231.60001
[11] Denisov, D., Dieker, A. B. and Shneer, V. (2008). Large deviations for random walks under subexponentiality: The big-jump domain. Ann. Probab. 36 1946-1991. · Zbl 1155.60019
[12] Embrechts, P. and Veraverbeke, N. (1982). Estimates for the probability of ruin with special emphasis on the possibility of large claims. Insurance Math. Econom. 1 55-72. · Zbl 0518.62083
[13] Gamarnik, D. and Zeevi, A. (2006). Validity of heavy traffic steady-state approximation in generalized Jackson networks. Ann. Appl. Probab. 16 56-90. · Zbl 1094.60052
[14] Harrison, J. M. and Williams, R. J. (1987). Brownian models of open queueing networks with homogeneous customer populations. Stochastics 22 77-115. · Zbl 0632.60095
[15] Iglehart, D. L. and Whitt, W. (1970a). Multiple channel queues in heavy traffic. I. Adv. in Appl. Probab. 2 150-177. JSTOR: · Zbl 0218.60098
[16] Iglehart, D. L. and Whitt, W. (1970b). Multiple channel queues in heavy traffic. II. Sequences, networks, and batches. Adv. in Appl. Probab. 2 355-369. · Zbl 0206.22503
[17] Kalashnikov, V. (1997). Geometric Sums : Bounds for Rare Events with Applications. Mathematics and Its Applications 413 . Kluwer, Dordrecht. · Zbl 0881.60043
[18] Kingman, J. F. C. (1961). The single server queue in heavy traffic. Proc. Cambridge Philos. Soc. 57 902-904. · Zbl 0114.11703
[19] Kingman, J. F. C. (1962). On queues in heavy traffic. J. Roy. Statist. Soc. Ser. B 24 150-177. JSTOR: · Zbl 0127.10003
[20] Mikosch, T. and Nagaev, A. V. (1998). Large deviations of heavy-tailed sums with applications in insurance. Extremes 1 81-110. · Zbl 0927.60037
[21] Nagaev, S. V. (1982). On the asymptotic behavior of one-sided large deviations. Theory Probab. Appl. 26 362-366. · Zbl 0481.60036
[22] Olvera-Cravioto, M., Blanchet, J. and Glynn, P. W. (2010). On the transition from heavy traffic to heavy tails for the M/G/1 queue: The regularly varying case, internet supplement. Available at . · Zbl 1216.41033
[23] Olvera-Cravioto, M. and Glynn, P. W. (2010). Uniform approximations for the M/G/1 queue with subexponential processing times. To appear. Available at . · Zbl 1242.60095
[24] Reiman, M. I. (1984). Open queueing networks in heavy traffic. Math. Oper. Res. 9 441-458. JSTOR: · Zbl 0549.90043
[25] Rozovskiĭ, L. V. (1989). Probabilities of large deviations of sums of independent random variables with a common distribution function that belongs to the domain of attraction of a normal law. Theory Probab. Appl. 34 625-644. · Zbl 0703.60024
[26] Szczotka, W. (1990). Exponential approximation of waiting time and queue size for queues in heavy traffic. Adv. in Appl. Probab. 22 230-240. JSTOR: · Zbl 0697.60088
[27] Szczotka, W. (1999). Tightness of the stationary waiting time in heavy traffic. Adv. in Appl. Probab. 31 788-794. · Zbl 0954.60085
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.