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.

Key words： 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. http://arxiv.org/abs/1208.5225, 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