# zbMATH — the first resource for mathematics

The stationary tail asymptotics in the $$GI/G/1$$-type queue with countably many background states. (English) Zbl 1136.60366
Summary: We consider the asymptotic behaviour of the stationary tail probabilities in the discrete-time $$GI/G/1$$-type queue with countable background state space. These probabilities are presented in matrix form with respect to the background state space, and shown to be the solution of a Markov renewal equation. Using this fact, we consider their decay rates. Applying the Markov renewal theorem, it is shown that certain reasonable conditions lead to the geometric decay of the tail probabilities as the level goes to infinity. We exemplify this result using a discrete-time priority queue with a single server and two types of customer.

##### MSC:
 60K25 Queueing theory (aspects of probability theory) 60K15 Markov renewal processes, semi-Markov processes 68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
Full Text:
##### References:
  Abate, J. and Whitt, W. (1997). Asymptotics for M/G/1 low-priority waiting-time tail probabilities. Queueing Systems 25, 173–233. · Zbl 0894.60088 · doi:10.1023/A:1019104402024  Alsmeyer, G. (1994). On the Markov renewal theorem. Stoch. Process. Appl. 50, 37–56. · Zbl 0789.60066 · doi:10.1016/0304-4149(94)90146-5  Alsmeyer, G. (2000). The ladder variables of a Markov random walk. Prob. Math. Statist. 20, 151–168. · Zbl 0988.60069  Arjas, E. and Speed, T. P. (1973). Symmetric Wiener–Hopf factorizations in Markov additive processes. Z. Wahrscheinlichkeitsth. 26, 105–118. · Zbl 0244.60056 · doi:10.1007/BF00533480  Asmussen, S. (1987). Applied Probability and Queues , 2nd edn. Springer, New York. · Zbl 0624.60098  Asmussen, S. (2000). Ruin Probabilities . World Scientific, Singapore. · Zbl 0960.60003  Bertsimas, D., Paschalidis, I. C. and Tsitsiklis, J. N. (1999). Large deviations analysis of the generalized processor sharing policy. Queueing Systems 32, 319–349. · Zbl 0937.68011 · doi:10.1023/A:1019151423773  Chan, H. P. and Lai, T. L. (2003). Saddlepoint approximations and nonlinear boundary crossing probabilities of Markov random walks. Ann. Appl. Prob. 13, 395–429. · Zbl 1029.60058 · doi:10.1214/aoap/1050689586  Çinlar, E. (1975). Introduction to Stochastic Processes . Prentice-Hall, Englewood Cliffs, NJ.  Collamore, J. F. (2002). Importance sampling techniques for the multidimensional ruin problem for general Markov additive sequences of random vectors. Ann. Appl. Prob. 12, 382–421. · Zbl 1021.65003 · doi:10.1214/aoap/1015961169  Fayolle, G., Malyshev, V. A. and Menshikov, M. V. (1995). Topics in the Constructive Theory of Countable Markov Chains . Cambridge University Press. · Zbl 0823.60053 · doi:10.1017/CBO9780511984020  Foley, R. D. and McDonald, D. R. (2001). Join the shortest queue: stability and exact asymptotics. Ann. Appl. Prob. 11, 569–607. · Zbl 1016.60078  Grassmann, W. K. and Heyman, D. P. (1990). Equilibrium distribution of block-structured Markov chains with repeating rows. J. Appl. Prob. 27, 557–576. · Zbl 0716.60076 · doi:10.2307/3214541  Li, Q. and Zhao, Y. Q. (2002). Light-tailed asymptotics of stationary probability vector of Markov chains of GI/G/1-type. Submitted.  Loynes, R. M. (1962). The stability of a queue with non-independent inter-arrival and service times. Proc. Camb. Phil. Soc. 58, 497–520. · Zbl 0203.22303 · doi:10.1017/S0305004100036781  McDonald, D. R. (1999). Asymptotics of first passage times for random walk in an orthant. Ann. Appl. Prob. 9, 110–145. · Zbl 0937.60091 · doi:10.1214/aoap/1029962599  Miyazawa, M. (2002). A Markov renewal approach to the asymptotic decay of the tail probabilities in risk and queueing processes. Prob. Eng. Inf. Sci. 16, 139–150. · Zbl 1005.60094 · doi:10.1017/S0269964802162012  Miyazawa, M. (2002). A paradigm of Markov additive processes for queues and their networks. In Matrix-Analytic Methods , eds G. Latouche and P. G. Taylor, World Scientific, River Edge, NJ, pp. 265–289. · Zbl 1162.90403  Miyazawa, M. (2003). Conjectures on decay rates of tail probabilities in generalized Jackson and batch movement networks. J. Operat. Res. Soc. Japan 46, 74–98. · Zbl 1107.90320  Miyazawa, M. (2004). The Markov renewal approach to M/G/1-type queues with countably many background states. Queueing Systems 46, 177–196. · Zbl 1056.90035 · doi:10.1023/B:QUES.0000021148.33178.0f  Neuts, M. F. (1981). Matrix-Geometric Solutions in Stochastic Models. An Algorithmic Approach . Johns Hopkins University Press, Baltimore, MD. · Zbl 0469.60002  Neuts, M. F. (1989). Structured Stochastic Matrices of M/G/1 Type and Their Applications . Marcel Dekker, New York. · Zbl 0695.60088  Ney, P. and Nummelin, E. (1987). Markov additive processes. I. Eigenvalue properties and limit theorems. Ann. Prob. 15, 561–592. JSTOR: · Zbl 0625.60027 · doi:10.1214/aop/1176992159 · links.jstor.org  Seneta, E. (1981). Nonnegative Matrices and Markov Chains , 2nd edn. Springer, New York. · Zbl 0471.60001  Shurenkov, V. M. (1984). On the theory of Markov renewal. Theory Prob. Appl. 29, 247–265. · Zbl 0557.60078 · doi:10.1137/1129036  Takahashi, Y., Fujimoto, K. and Makimoto, N. (2001). 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. · Zbl 0985.60074 · doi:10.1081/STM-100001397  Zhang, Z. L. (1998). Large deviations and the generalized processor sharing schedule for a multiple-queue system. Queueing Systems 28, 349–376. · Zbl 0922.90070 · doi:10.1023/A:1019163509718  Zhao, Y. Q., Li, W. and Alfa, A. S. (1999). Duality results for block-structured transition matrices. J. Appl. Prob. 36, 1045–1057. · Zbl 0978.60082 · doi:10.1239/jap/1032374754  Zhao, Y. Q., Li, W. and Braun, W. J. (1998). Infinite block-structured transition matrices and their properties. Adv. Appl. Prob. 30, 365–384. · Zbl 0910.60052 · doi:10.1239/aap/1035228074  Zhao, Y. Q., Li, W. and Braun, W. J. (2003). Censoring, factorizations and spectral analysis for transition matrices with block-repeating entries. Methodology Comput. Appl. Prob. 5, 35–58. · Zbl 1022.60073 · doi:10.1023/A:1024125320911
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.