×

zbMATH — the first resource for mathematics

Rare event asymptotics for a random walk in the quarter plane. (English) Zbl 1210.60100
Random walks in a quarter plane have been studied by several authors [see e.g. G. Fayolle and R. Iasnogorodski, Z. Wahrscheinlichkeitstheor. Verw. Geb. 47, 325–351 (1979; Zbl 0395.68032); G. Fayolle, R. Iasnogorodski and V. Malyshev, Random walks in the quarter-plane. Algebraic methods, boundary value problems and applications. Berlin: Springer (1999; Zbl 0932.60002); J. W. Cohen and O. J. Boxma, Boundary value problems in queueing system analysis. Amsterdam - New York - Oxford: North-Holland Publishing Company (1983; Zbl 0515.60092)].
This paper presents new analytic techniques for deriving asymptotic expressions for the occurrence of rare events for a random walk in the quarter plane. The results are applied for tandem queues with Poisson arrivals, exponential service times and coupled processors. The authors derive the functional equation for the bivariate generating function of the queue-lengths and investigate it. For the asymptotic analysis of large queue-lengths they combine the kernel method for functional equations with boundary value problems and singularity analysis.

MSC:
60K25 Queueing theory (aspects of probability theory)
60F10 Large deviations
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 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) · Zbl 1188.60046 · doi:10.1007/s11134-009-9140-y
[2] Borovkov, A.A., Mogul’skii, A.A.: Large deviations for Markov chains in the positive quadrant. Russ. Math. Surv. 56, 803–916 (2001) · Zbl 1068.60034 · doi:10.1070/RM2001v056n05ABEH000398
[3] 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)
[4] Bousquet-Mélou, M.: Walks in the quarter plane: Kreweras’ algebraic model. Ann. Appl. Probab. 15, 1451–1491 (2005) · Zbl 1064.05010 · doi:10.1214/105051605000000052
[5] Cohen, J.W., Boxma, O.J.: Boundary Value Problems in Queueing System Analysis. North-Holland, Amsterdam (1983) · Zbl 0515.60092
[6] De Bruijn, N.G.: Asymptotic Methods in Analysis. Dover, New York (1981) · Zbl 0556.41021
[7] Denteneer, D., van Leeuwaarden, J.S.H.: Multi-Access, Reservations and Queues. Springer, New York (2008) · Zbl 1167.68331
[8] Dieudonne, J.: Calcul Infinitésimal. Hermann, Paris (1980)
[9] Drmota, M.: Systems of functional equations. Random Struct. Algorithms 10, 103–124 (1997) · Zbl 0869.39010 · doi:10.1002/(SICI)1098-2418(199701/03)10:1/2<103::AID-RSA5>3.3.CO;2-0
[10] Fayolle, G., Iasnogorodski, R.: Two coupled processors: The reduction to a Riemann–Hilbert problem. Z. Wahrscheinlichkeitstheor. Verw. Geb. 47, 325–351 (1979) · Zbl 0395.68032 · doi:10.1007/BF00535168
[11] Fayolle, G., Iasnogorodski, R., Malyshev, V.: Random Walks in the Quarter Plane. Springer, New York (1999) · Zbl 0932.60002
[12] Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009) · Zbl 1165.05001
[13] Flajolet, P., Gourdon, X., Martinez, C.: Patterns in random binary search trees. Random Struct. Algorithms 11, 223–244 (1988) · Zbl 0895.60010 · doi:10.1002/(SICI)1098-2418(199710)11:3<223::AID-RSA2>3.0.CO;2-2
[14] Flatto, L.: The longer queue model. Probab. Eng. Inf. Sci. 3, 537–559 (1989) · Zbl 1134.60395 · doi:10.1017/S0269964800001376
[15] Flatto, L., Hahn, S.: Two parallel queues created by arrivals with two demands. I. SIAM J. Appl. Math. 44, 1041–1053 (1984) · Zbl 0554.90041 · doi:10.1137/0144074
[16] Foley, R.D., McDonald, D.R.: Join the shortest queue: Stability and exact asymptotics. Ann. Appl. Probab. 11, 569–607 (2001) · Zbl 1016.60078
[17] Foley, R.D., McDonald, D.R.: Large deviations of a modified Jackson network: Stability and rough asymptotics. Ann. Appl. Probab. 15, 519–541 (2005) · Zbl 1063.60134 · doi:10.1214/105051604000000666
[18] Foley, R.D., McDonald, D.R.: Bridges and networks: exact asymptotics. Ann. Appl. Probab. 15, 542–586 (2005) · Zbl 1085.60068 · doi:10.1214/105051604000000675
[19] 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) · Zbl 1065.60132 · doi:10.1239/jap/1091543429
[20] 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) · Zbl 1065.60133 · doi:10.1081/STM-200046489
[21] Ignatyuk, I.A., Malyshev, V.A., Scherbakov, V.V.: Boundary effects in a large deviation problem. Russ. Math. Surv. 49, 41–99 (1994) · doi:10.1070/RM1994v049n02ABEH002204
[22] 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) · Zbl 1078.60078 · doi:10.1214/105051604000000477
[23] Li, H., Zhao, Y.Q.: A retrial queue with a constant retrial rate, server downs and impatient customers. Stoch. Models 21, 531–550 (2005) · Zbl 1069.60076 · doi:10.1081/STM-200056021
[24] Miyazawa, M.: Tail decay rates in double QBD processes and related reflected random walks. Math. Oper. Res. 34, 547–575 (2009) · Zbl 1213.60151 · doi:10.1287/moor.1090.0375
[25] 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) · Zbl 1136.60366 · doi:10.1239/aap/1103662965
[26] Neuts, M.F.: Matrix-Geometric Solutions in Stochastic Models, an Algorithmic Approach. Johns Hopkins University Press, Baltimore (1981) · Zbl 0469.60002
[27] Pemantle, R., Wilson, M.C.: Twenty combinatorial examples of asymptotics derived from multivariate generating functions. SIAM Rev. 50, 199–272 (2008) · Zbl 1149.05003 · doi:10.1137/050643866
[28] Resing, J.A.C., Örmeci, L.: A tandem queueing model with coupled processors. Oper. Res. Lett. 31, 383–389 (2003) · Zbl 1033.90017 · doi:10.1016/S0167-6377(03)00046-4
[29] Sakuma, Y., Miyazawa, M.: On the effect of finite buffer truncation in a two-node Jackson network. J. Appl. Probab. 42, 199–222 (2005) · Zbl 1077.60070 · doi:10.1239/jap/1110381381
[30] Shwartz, A., Weiss, A.: Large Deviations for Performance Analysis, Queues, Communications and Computing. Chapman & Hall, London (1995) · Zbl 0871.60021
[31] 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) · Zbl 0985.60074 · doi:10.1081/STM-100001397
[32] van Leeuwaarden, J.S.H., Resing, J.A.C.: A tandem queue with coupled processors: computational issues. Queueing Syst. 51, 29–52 (2005) · Zbl 1094.60065 · doi:10.1007/s11134-005-1683-y
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.