Deviation matrix and asymptotic variance for GI/M/1-type Markov chains

Abstract

We investigate deviation matrix for discrete-time GI/M/1-type Markov chains in terms of the matrix-analytic method, and revisit the link between deviation matrix and the asymptotic variance. Parallel results are obtained for continuous-time GI/M/1-type Markov chains based on the technique of uniformization. We conclude with A. B. Clarke’s tandem queue as an illustrative example, and compute the asymptotic variance for the queue length for this model.

Keywords

GI/M/1-type Markov chains / deviation matrix / asymptotic variance / matrix-analytic method

References

[1] Asmussen S, Bladt M. Poisson’s equation for queues driven by a Markovian marked point process. Queueing Syst, 1994, 17: 235−274

[2] Bini D A, Latouche G, Meini B. Numerical Methods for Structured Markov Chains. Oxford: Oxford University Press, 2005

[3] Coolen-Schrijner P, Van Doorn E A. The deviation matrix of a continuous-time Markov chain. Probab Engrg Inform Sci, 2002, 16: 351−366

[4] Dendievel S, Latouche G, Liu Y. Poisson’s equation for discrete-time quasi-birth-anddeath processes. Performance Evaluation, 2013, 70: 564−577

[5] Glynn P W. Poisson’s equation for the recurrent M/G/1 queue. Adv Appl Probab, 1994, 26(4): 1044−1062

[6] Glynn P W, Meyn S P. A Liapounov bound for solutions of the Poisson equation. Ann Probab, 1996, 24(2): 916−931

[7] Grassmann W K. The asymptotic variance of a time average in a birth-death process. Ann Oper Res, 1987, 8: 165−174

[8] Jiang S, Liu Y, Yao S. Poisson’s equation for discrete-time single-birth processes. Statist Probab Lett, 2014, 85: 78−83

[9] Latouche G, Ramaswami V. A logarithmic reduction algorithm for quasi-birth-anddeath processes. J Appl Probab, 1993, 30(3): 650−674

[10] Latouche G, Ramaswami V. Introduction to Matrix Analytic Methods in Stochastic Modeling. ASA-SIAM Series on Statistics and Applied Probability. Philadelphia: SIAM, 1999

[11] Liu Y. Additive functionals for discrete-time Markov chains with applications to birthdeath processes. J Appl Probab, 2011, 48(4): 925−937

[12] Liu Y, Hou Z. Several types of ergodicity for M/G/1-type Markov chains and Markov processes. J Appl Probab, 2006, 43(1): 141−158

[13] Liu Y, Zhang Y H. Central limit theorems for Markov processes with applications to single birth processes. Preprint, 2013

[14] Mao Y, Tai Y, Zhao Y Q, Zou J. Ergodicity for the GI/G/1-type Markov chain. 2012

[15] Meyer C D. The role of the group generalized inverse in the theory of finite Markov chains. SIAM Rev, 1975, 17(3): 443−464

[16] Meyn S P, Tweedie R L. Markov Chains and Stochastic Stability. 2nd ed. New York: Cambridge University Press, 2009

[17] Neuts M F. Moment formulas for the Markov renewal branching process. Adv Appl Probab, 1976, 8(4): 690−711

[18] Neuts M F. Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach. Baltimore: The Johns Hopkins University Press, 1981

[19] Neuts M F. Structured Stochastic Matrices of M/G/1 Type and Their Applications. New York: Marcel Dekker, 1989

[20] Pérez J F, Telek M, Houdt B V. A fast Newton’s iteration for M/G/1-type and GI/M/1-type Markov chains. Stoch Models, 2012, 28: 557−583

[21] Whitt W. Asymptotic formulas for Markov processes with applications to simulation. Oper Res, 1992, 40: 279−291

[22] Zhao Y Q. Censoring technique in studying block-structured Markov chains. In: Latouche G, Taylor P G, eds. Advances in Algorithmic Methods for Stochastic Models: Proceedings of the 3rd International Conference on Matrix Analytic Methods. NJ: Notable Publications, 2000, 417−433

[23] Zhao Y Q, Li W, Braun W J. Censoring, factorizations, and spectral analysis for transition matrices with block-repeating entries. Methodol Comput Appl Probab, 2003, 5: 35−58

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg