October  2017, 13(4): 2093-2146. doi: 10.3934/jimo.2017033

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  October 2015 Revised  September 2016 Published  April 2017

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.

Citation: Tatsuaki Kimura, Hiroyuki Masuyama, Yutaka Takahashi. Light-tailed asymptotics of GI/G/1-type Markov chains. Journal of Industrial and Management Optimization, 2017, 13 (4) : 2093-2146. doi: 10.3934/jimo.2017033
References:
[1]

J. AbateG. 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. AndrewK. 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. AsmussenL. 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, 2nd 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. GailS. 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. GailS. 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. KimuraK. DaikokuH. 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. KimuraH. 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. KimuraH. 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. LiM. 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. MasuyamaB. 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, 2nd 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. ZhaoW. 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. ZhaoW. 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. ZhaoW. 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.

show all references

References:
[1]

J. AbateG. 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. AndrewK. 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. AsmussenL. 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, 2nd 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. GailS. 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. GailS. 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. KimuraK. DaikokuH. 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. KimuraH. 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. KimuraH. 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. LiM. 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. MasuyamaB. 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, 2nd 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. ZhaoW. 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. ZhaoW. 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. ZhaoW. 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.

[1]

Byeongchan Lee, Jonghun Yoon, Yang Woo Shin, Ganguk Hwang. Tail asymptotics of fluid queues in a distributed server system fed by a heavy-tailed ON-OFF flow. Journal of Industrial and Management Optimization, 2016, 12 (2) : 637-652. doi: 10.3934/jimo.2016.12.637

[2]

Simone Göttlich, Stephan Knapp. Semi-Markovian capacities in production network models. Discrete and Continuous Dynamical Systems - B, 2017, 22 (9) : 3235-3258. doi: 10.3934/dcdsb.2017090

[3]

Dan Li, Hui Wan. Coexistence and exclusion of competitive Kolmogorov systems with semi-Markovian switching. Discrete and Continuous Dynamical Systems, 2021, 41 (9) : 4145-4183. doi: 10.3934/dcds.2021032

[4]

Samuel N. Cohen, Lukasz Szpruch. On Markovian solutions to Markov Chain BSDEs. Numerical Algebra, Control and Optimization, 2012, 2 (2) : 257-269. doi: 10.3934/naco.2012.2.257

[5]

Jerim Kim, Bara Kim, Hwa-Sung Kim. G/M/1 type structure of a risk model with general claim sizes in a Markovian environment. Journal of Industrial and Management Optimization, 2012, 8 (4) : 909-924. doi: 10.3934/jimo.2012.8.909

[6]

Shan Gao, Jinting Wang. On a discrete-time GI$^X$/Geo/1/N-G queue with randomized working vacations and at most $J$ vacations. Journal of Industrial and Management Optimization, 2015, 11 (3) : 779-806. doi: 10.3934/jimo.2015.11.779

[7]

Jesus R. Artalejo, Tuan Phung-Duc. Markovian retrial queues with two way communication. Journal of Industrial and Management Optimization, 2012, 8 (4) : 781-806. doi: 10.3934/jimo.2012.8.781

[8]

Ralf Banisch, Carsten Hartmann. A sparse Markov chain approximation of LQ-type stochastic control problems. Mathematical Control and Related Fields, 2016, 6 (3) : 363-389. doi: 10.3934/mcrf.2016007

[9]

Sung-Seok Ko, Jangha Kang, E-Yeon Kwon. An $(s,S)$ inventory model with level-dependent $G/M/1$-Type structure. Journal of Industrial and Management Optimization, 2016, 12 (2) : 609-624. doi: 10.3934/jimo.2016.12.609

[10]

Ralf Banisch, Carsten Hartmann. Addendum to "A sparse Markov chain approximation of LQ-type stochastic control problems". Mathematical Control and Related Fields, 2017, 7 (4) : 623-623. doi: 10.3934/mcrf.2017023

[11]

Qingwu Gao, Zhongquan Huang, Houcai Shen, Juan Zheng. Asymptotics for random-time ruin probability in a time-dependent renewal risk model with subexponential claims. Journal of Industrial and Management Optimization, 2016, 12 (1) : 31-43. doi: 10.3934/jimo.2016.12.31

[12]

Yang Yang, Kam C. Yuen, Jun-Feng Liu. Asymptotics for ruin probabilities in Lévy-driven risk models with heavy-tailed claims. Journal of Industrial and Management Optimization, 2018, 14 (1) : 231-247. doi: 10.3934/jimo.2017044

[13]

Yutaka Sakuma, Atsushi Inoie, Ken’ichi Kawanishi, Masakiyo Miyazawa. Tail asymptotics for waiting time distribution of an M/M/s queue with general impatient time. Journal of Industrial and Management Optimization, 2011, 7 (3) : 593-606. doi: 10.3934/jimo.2011.7.593

[14]

María Jesús Carro, Carlos Domingo-Salazar. The return times property for the tail on logarithm-type spaces. Discrete and Continuous Dynamical Systems, 2018, 38 (4) : 2065-2078. doi: 10.3934/dcds.2018084

[15]

Angelica Pachon, Federico Polito, Costantino Ricciuti. On discrete-time semi-Markov processes. Discrete and Continuous Dynamical Systems - B, 2021, 26 (3) : 1499-1529. doi: 10.3934/dcdsb.2020170

[16]

Sujit Kumar Samanta, Rakesh Nandi. Analysis of $GI^{[X]}/D$-$MSP/1/\infty$ queue using $RG$-factorization. Journal of Industrial and Management Optimization, 2021, 17 (2) : 549-573. doi: 10.3934/jimo.2019123

[17]

Ajay Jasra, Kody J. H. Law, Yaxian Xu. Markov chain simulation for multilevel Monte Carlo. Foundations of Data Science, 2021, 3 (1) : 27-47. doi: 10.3934/fods.2021004

[18]

Sheng Zhu, Jinting Wang. Strategic behavior and optimal strategies in an M/G/1 queue with Bernoulli vacations. Journal of Industrial and Management Optimization, 2018, 14 (4) : 1297-1322. doi: 10.3934/jimo.2018008

[19]

Fadia Bekkal-Brikci, Giovanna Chiorino, Khalid Boushaba. G1/S transition and cell population dynamics. Networks and Heterogeneous Media, 2009, 4 (1) : 67-90. doi: 10.3934/nhm.2009.4.67

[20]

Jingzhi Tie, Qing Zhang. An optimal mean-reversion trading rule under a Markov chain model. Mathematical Control and Related Fields, 2016, 6 (3) : 467-488. doi: 10.3934/mcrf.2016012

2021 Impact Factor: 1.411

Metrics

  • PDF downloads (123)
  • HTML views (396)
  • Cited by (0)

[Back to Top]