Light-tailed asymptotics of GI/G/1-type Markov chains

Tatsuaki Kimura; Hiroyuki Masuyama; Yutaka Takahashi

doi:10.3934/jimo.2017033

Article Contents

2017, Volume 13, Issue 4: 2093-2146. Doi: 10.3934/jimo.2017033

This issue Previous Article Comparison of GA and PSO approaches for the direct and LQR tuning of a multirotor PD controller Next Article

Light-tailed asymptotics of GI/G/1-type Markov chains

1.
NTT Network Technology Laboratories, NTT Corporation, Tokyo 180–8585, Japan
2.
Department of Systems Science, Graduate School of Informatics, Kyoto University, Kyoto 606–8501, Japan

Received: September 30, 2015

Revised: August 31, 2016

Published: November 2017

Abstract Full Text(HTML) Related Papers Cited by

Abstract

This paper studies the light-tailed asymptotics of the stationary distribution of the GI/G/1-type Markov chain. We consider three cases:(ⅰ) the tail decay rate is determined by a certain parameter $\theta$ associated with the transition block matrices $\{\boldsymbol{A}(k);k=0,\pm1,\pm2,\dots\}$ in the non-boundary levels; (ⅱ) by the convergence radius of the generating function of the transition block matrices $\{\boldsymbol{B}(k);k=1,2,\dots\}$ in the boundary level; and (ⅲ) by the convergence radius of $\sum_{k=1}^{\infty}z^k \boldsymbol{A}(k)$. In the case (ⅰ), we extend the existing asymptotic formula for the M/G/1-type Markov chain to the GI/G/1-type one. In the case (ⅱ), we present general asymptotic formulas that include, as special cases, the existing results in the literature. In the case (ⅲ), we derive new asymptotic formulas. As far as we know, such formulas have not been reported in the literature.

Keywords:

Mathematics Subject Classification: Primary: 60K25; Secondary: 60J10.

Citation:

Full Text(HTML)

Related Papers

Cited by

References

[1]	J. Abate, G. L. Choudhury and W. Whitt, Asymptotics for steady-state tail probabilities in structured Markov queueing models, Stochastic Models, 10 (1994), 99-143. doi: 10.1080/15326349408807290.
[2]	L. A. Andrew, K. E. Chu and P. Lancaster, Derivatives of eigenvalues and eigenvectors of matrix functions, SIAM Journal on Matrix Analysis and Applications, 14 (1993), 903-926. doi: 10.1137/0614061.
[3]	S. Asmussen, L. F. Henriksen and C. Klüppelberg, Large claims approximations for risk processes in a Markovian environment, Stochastic Processes and their Applications, 54 (1994), 29-43. doi: 10.1016/0304-4149(93)00003-X.
[4]	S. Asmussen and J. R. Møller, Tail asymptotics for M/G/1 type queueing processes with subexponential increments, Queueing Systems, 33 (1999), 153-176. doi: 10.1023/A:1019172028316.
[5]	S. Asmussen, Applied Probability and Queues, 2^nd edition, Springer, New York, 2003.
[6]	R. B. Bapat and T. E. S. Raghavan, Nonnegative Matrices and Applications, Cambridge University Press, Cambridge, UK, 1997. doi: 10.1017/CBO9780511529979.
[7]	P. Embrechts, C. Klüppelberg and T. Mikosch, Modelling Extremal Events for Insurance and Finance, Springer, Berlin, 1997. doi: 10.1007/978-3-642-33483-2.
[8]	E. Falkenberg, On the asymptotic behaviour of the stationary distribution of Markov chains of M/G/1-type, Stochastic Models, 10 (1994), 75-97. doi: 10.1080/15326349408807289.
[9]	S. Foss, D. Korshunov and S. Zachary, An Introduction to Heavy-Tailed and Subexponential Distributions, Springer, New York, 2011. doi: 10.1007/978-1-4419-9473-8.
[10]	H. Gail, S. L. Hantler and B. A. Taylor, Matrix-geometric invariant measures for G/M/1 type Markov chains, Stochastic Models, 14 (1997), 537-569. doi: 10.1080/15326349808807487.
[11]	H. Gail, S. L. Hantler and B. A. Taylor, Use of characteristic roots for solving infinite state Markov chains, Computational Probability, 24 (2000), 205-255. doi: 10.1007/978-1-4757-4828-4_7.
[12]	W. K. Grassmann and D. P. Heyman, Equilibrium distribution of block-structured Markov chains with repeating rows, Journal of Applied Probability, 27 (1990), 557-576. doi: 10.1017/S0021900200039115.
[13]	R. A. Horn and C. R. Johnson, Matrix Analysis, Paperback edition, Cambridge University Press, New York, 1990.
[14]	R. A. Horn and C. R. Johnson, Topics in Matrix Analysis, Paperback edition, Cambridge University Press, New York, 1994.
[15]	P. R. Jelenković and A. A. Lazar, Subexponential asymptotics of a Markov-modulated random walk with queueing applications, Journal of Applied Probability, 35 (1998), 325-347. doi: 10.1017/S0021900200014984.
[16]	B. Kim and J. Kim, A note on the subexponential asymptotics of the stationary distribution of M/G/1 type Markov chains, European Journal of Operational Research, 220 (2012), 132-134. doi: 10.1016/j.ejor.2012.01.016.
[17]	T. Kimura, K. Daikoku, H. Masuyama and Y. Takahashi, Light-tailed asymptotics of stationary tail probability vectors of Markov chains of M/G/1 type, Stochastic Models, 26 (2010), 505-548. doi: 10.1080/15326349.2010.519661.
[18]	T. Kimura, H. Masuyama and Y. Takahashi, Subexponential asymptotics of the stationary distributions of GI/G/1-type Markov chains, Stochastic Models, 29 (2013), 190-239. doi: 10.1080/15326349.2013.783286.
[19]	T. Kimura, H. Masuyama and Y. Takahashi, Corrigendum to "Subexponential asymptotics of the stationary distributions of GI/G/1-type Markov chains", Stochastic Models, 31 (2015), 673-677. doi: 10.1080/15326349.2015.1075891.
[20]	J. F. C. Kingman, A convexity property of positive matrices, Quarterly Journal of Mathematics, 12 (1961), 283-284. doi: 10.1093/qmath/12.1.283.
[21]	C. Klüppelberg, Subexponential distributions and integrated tails, Journal of Applied Probability, 25 (1988), 132-141. doi: 10.1017/S0021900200040705.
[22]	G. Latouche and V. Ramaswami, Introduction to Matrix Analytic Methods in Stochastic Modeling, ASA-SIAM Series on Statistics and Applied Probability, SIAM, Philadelphia, PA, 1999. doi: 10.1137/1.9780898719734.
[23]	H. Li, M. Miyazawa and Y. Q. Zhao, Geometric decay in a QBD process with countable background states with applications to a join-the-shortest-queue model, Stochastic Models, 23 (2007), 413-438. doi: 10.1080/15326340701471042.
[24]	Q.-L. Li and Y. Q. Zhao, Heavy-tailed asymptotics of stationary probability vectors of Markov chains of GI/G/1 type, Advances in Applied Probability, 37 (2005), 482-509. doi: 10.1017/S0001867800000276.
[25]	Q.-L. Li and Y. Q. Zhao, Light-tailed asymptotics of stationary probability vectors of Markov chains of GI/G/1 type, Advances in Applied Probability, 37 (2005), 1075-1093. doi: 10.1017/S0001867800000677.
[26]	H. Masuyama, Subexponential asymptotics of the stationary distributions of M/G/1-Type Markov chains, European Journal of Operational Research, 213 (2011), 509-516. doi: 10.1016/j.ejor.2011.03.038.
[27]	H. Masuyama, A sufficient condition for subexponential asymptotics of GI/G/1-type Markov chains with queueing applications, Ann. Oper. Res., 247 (2016), 65-95, arXiv: 1310.4590. doi: 10.1007/s10479-015-1893-6.
[28]	H. Masuyama, Tail asymptotics for cumulative processes sampled at heavy-tailed random times with applications to queueing models in Markovian environments, Journal of the Operations Research Society of Japan, 56 (2013), 257-308.
[29]	H. Masuyama, B. Liu and T. Takine, Subexponential asymptotics of the BMAP/GI/1 queue, Journal of the Operations Research Society of Japan, 52 (2009), 377-401.
[30]	M. Miyazawa, A Markov renewal approach to M/G/1 type queues with countably many background states, Queueing Systems, 46 (2004), 177-196. doi: 10.1023/B:QUES.0000021148.33178.0f.
[31]	M. Miyazawa, Tail decay rates in double QBD processes and related reflected random walks, Stochastic Models, 34 (2009), 547-575. doi: 10.1287/moor.1090.0375.
[32]	M. Miyazawa and Y. Q. Zhao, The stationary tail asymptotics in the GI/G/1-type queue with countably many background states, Advances in Applied Probability, 36 (2004), 1231-1251. doi: 10.1017/S0001867800013380.
[33]	J. R. Møller, Tail asymptotics for M/G/1-type queueing processes with light-tailed increments, Operations Research Letters, 28 (2001), 181-185. doi: 10.1016/S0167-6377(01)00061-X.
[34]	M. F. Neuts, Structured Stochastic Matrices of M/G/1 Type and Their Applications, Marcel Dekker, New York, 1989.
[35]	T. Ozawa, Asymptotics for the stationary distribution in a discrete-time two-dimensional quasi-birth-and-death process, Queueing Systems, 74 (2013), 109-149. doi: 10.1007/s11134-012-9323-9.
[36]	E. J. G. Pitman, Subexponential distribution functions, Journal of the Australian Mathematical Society, A29 (1980), 337-347. doi: 10.1017/S1446788700021340.
[37]	E. Seneta, Nonnegative Matrices and Markov Chains, 2^nd edition, Springer, New York, 1981. doi: 10.1007/0-387-32792-4.
[38]	Y. Tai, Tail Asymptotics and Ergodicity for the GI/G/1-type Markov Chains, Dissertation, Carleton University, Ottawa, Canada, 2009.
[39]	T. Takine, Geometric and subexponential asymptotics of Markov chains of M/G/1 type, Mathematics of Operations Research, 29 (2004), 624-648. doi: 10.1287/moor.1030.0083.
[40]	Y. Q. Zhao, W. Li and W. J. Braun, Infinite block-structured transition matrices and their properties, Advances in Applied Probability, 30 (1998), 365-384. doi: 10.1017/S0001867800047339.
[41]	Y. Q. Zhao, W. Li and A. S. Alfa, Duality results for block-structured transition matrices, Journal of Applied Probability, 36 (1999), 1045-1057. doi: 10.1017/S002190020001785X.
[42]	Y. Q. Zhao, W. Li and W. J. Braun, Censoring, factorizations, and spectral analysis for transition matrices with block-repeating entries, Methodology and Computing in Applied Probability, 5 (2003), 35-58. doi: 10.1023/A:1024125320911.