Abstract
This paper presents a novel technique for deriving asymptotic expressions for the occurrence of rare events for a random walk in the quarter plane. In particular, we study a tandem queue with Poisson arrivals, exponential service times and coupled processors. The service rate for one queue is only a fraction of the global service rate when the other queue is non-empty; when one queue is empty, the other queue has full service rate. The bivariate generating function of the queue lengths gives rise to a functional equation. In order to derive asymptotic expressions for large queue lengths, we combine the kernel method for functional equations with boundary value problems and singularity analysis.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Adan, I.J.B.F., Foley, R.D., McDonald, D.R.: Exact asymptotics for the stationary distribution of a Markov chain: a production model. Queueing Syst. 62, 311–344 (2009)
Borovkov, A.A., Mogul’skii, A.A.: Large deviations for Markov chains in the positive quadrant. Russ. Math. Surv. 56, 803–916 (2001)
Borst, S.C., Boxma, O.J., van Uitert, M.J.G.: Two coupled queues with heterogeneous traffic. In: Proceedings of ITC 17, pp. 1003–1014. North-Holland, Amsterdam (2001)
Bousquet-Mélou, M.: Walks in the quarter plane: Kreweras’ algebraic model. Ann. Appl. Probab. 15, 1451–1491 (2005)
Cohen, J.W., Boxma, O.J.: Boundary Value Problems in Queueing System Analysis. North-Holland, Amsterdam (1983)
De Bruijn, N.G.: Asymptotic Methods in Analysis. Dover, New York (1981)
Denteneer, D., van Leeuwaarden, J.S.H.: Multi-Access, Reservations and Queues. Springer, New York (2008)
Dieudonne, J.: Calcul Infinitésimal. Hermann, Paris (1980)
Drmota, M.: Systems of functional equations. Random Struct. Algorithms 10, 103–124 (1997)
Fayolle, G., Iasnogorodski, R.: Two coupled processors: The reduction to a Riemann–Hilbert problem. Z. Wahrscheinlichkeitstheor. Verw. Geb. 47, 325–351 (1979)
Fayolle, G., Iasnogorodski, R., Malyshev, V.: Random Walks in the Quarter Plane. Springer, New York (1999)
Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009)
Flajolet, P., Gourdon, X., Martinez, C.: Patterns in random binary search trees. Random Struct. Algorithms 11, 223–244 (1988)
Flatto, L.: The longer queue model. Probab. Eng. Inf. Sci. 3, 537–559 (1989)
Flatto, L., Hahn, S.: Two parallel queues created by arrivals with two demands. I. SIAM J. Appl. Math. 44, 1041–1053 (1984)
Foley, R.D., McDonald, D.R.: Join the shortest queue: Stability and exact asymptotics. Ann. Appl. Probab. 11, 569–607 (2001)
Foley, R.D., McDonald, D.R.: Large deviations of a modified Jackson network: Stability and rough asymptotics. Ann. Appl. Probab. 15, 519–541 (2005)
Foley, R.D., McDonald, D.R.: Bridges and networks: exact asymptotics. Ann. Appl. Probab. 15, 542–586 (2005)
Guillemin, F., Pinchon, D.: Analysis of generalized processor-sharing systems with two classes of customers and exponential services. J. Appl. Probab. 41, 832–858 (2004)
Haque, L., Liu, L., Zhao, Y.Q.: Sufficient conditions for a geometric tail in a QBD process with countably many levels and phases. Stoch. Models 21, 77–99 (2005)
Ignatyuk, I.A., Malyshev, V.A., Scherbakov, V.V.: Boundary effects in a large deviation problem. Russ. Math. Surv. 49, 41–99 (1994)
Kroese, D.P., Scheinhardt, W.R.W., Taylor, P.G.: Spectral properties of the tandem Jackson network, seen as a quasi-birth-and-death process. Ann. Appl. Probab. 14, 2057–2089 (2004)
Li, H., Zhao, Y.Q.: A retrial queue with a constant retrial rate, server downs and impatient customers. Stoch. Models 21, 531–550 (2005)
Miyazawa, M.: Tail decay rates in double QBD processes and related reflected random walks. Math. Oper. Res. 34, 547–575 (2009)
Miyazawa, M., Zhao, Y.Q.: The stationary tail asymptotics in the GI/G/1-type queue with countably many background states. Adv. Appl. Probab. 36, 1231–1251 (2004)
Neuts, M.F.: Matrix-Geometric Solutions in Stochastic Models, an Algorithmic Approach. Johns Hopkins University Press, Baltimore (1981)
Pemantle, R., Wilson, M.C.: Twenty combinatorial examples of asymptotics derived from multivariate generating functions. SIAM Rev. 50, 199–272 (2008)
Resing, J.A.C., Örmeci, L.: A tandem queueing model with coupled processors. Oper. Res. Lett. 31, 383–389 (2003)
Sakuma, Y., Miyazawa, M.: On the effect of finite buffer truncation in a two-node Jackson network. J. Appl. Probab. 42, 199–222 (2005)
Shwartz, A., Weiss, A.: Large Deviations for Performance Analysis, Queues, Communications and Computing. Chapman & Hall, London (1995)
Takahashi, Y., Fujimoto, K., Makimoto, N.: Geometric decay of the steady-state probabilities in a quasi-birth-and-death process with a countable number of phases. Stoch. Models 17, 1–24 (2001)
van Leeuwaarden, J.S.H., Resing, J.A.C.: A tandem queue with coupled processors: computational issues. Queueing Syst. 51, 29–52 (2005)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Guillemin, F., van Leeuwaarden, J.S.H. Rare event asymptotics for a random walk in the quarter plane. Queueing Syst 67, 1–32 (2011). https://doi.org/10.1007/s11134-010-9197-7
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11134-010-9197-7
Keywords
- Boundary value problems
- Random walks in the quarter plane
- Rare events
- Queueing theory
- Singularity analysis
- Tail decay rate
- Large deviations