Deviation matrix and asymptotic variance for \(\mathrm{GI}/\mathrm{M}/1\)-type Markov chains. (English) Zbl 1308.60090
Summary: We investigate the deviation matrix for discrete-time \(\mathrm{GI}/\mathrm{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 \(\mathrm{GI}/\mathrm{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.
MSC:
| 60J10 | Markov chains (discrete-time Markov processes on discrete state spaces) |
| 60K25 | Queueing theory (aspects of probability theory) |
| 60J27 | Continuous-time Markov processes on discrete state spaces |
Keywords:
\(\mathrm{GI}/\mathrm{M}/1\)-type Markov chains; deviation matrix; asymptotic variance; matrix-analytic method; tandem queueReferences:
| [1] | Asmussen S, Bladt M. Poisson’s equation for queues driven by a Markovian marked point process. Queueing Syst, 1994, 17: 235-274 · Zbl 0809.60093 · doi:10.1007/BF01158696 |
| [2] | Bini D A, Latouche G, Meini B. Numerical Methods for Structured Markov Chains. Oxford: Oxford University Press, 2005 · Zbl 1076.60002 · doi:10.1093/acprof:oso/9780198527688.001.0001 |
| [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 · Zbl 1011.60057 · doi:10.1017/S0269964802163066 |
| [4] | Dendievel S, Latouche G, Liu Y. Poisson’s equation for discrete-time quasi-birth-anddeath processes. Performance Evaluation, 2013, 70: 564-577 · doi:10.1016/j.peva.2013.05.008 |
| [5] | Glynn P W. Poisson’s equation for the recurrent M/G/1 queue. Adv Appl Probab, 1994, 26(4): 1044-1062 · Zbl 0820.60073 · doi:10.2307/1427904 |
| [6] | Glynn P W, Meyn S P. A Liapounov bound for solutions of the Poisson equation. Ann Probab, 1996, 24(2): 916-931 · Zbl 0863.60063 · doi:10.1214/aop/1039639370 |
| [7] | Grassmann W K. The asymptotic variance of a time average in a birth-death process. Ann Oper Res, 1987, 8: 165-174 · doi:10.1007/BF02187089 |
| [8] | Jiang S, Liu Y, Yao S. Poisson’s equation for discrete-time single-birth processes. Statist Probab Lett, 2014, 85: 78-83 · Zbl 1326.60122 · doi:10.1016/j.spl.2013.11.008 |
| [9] | Latouche G, Ramaswami V. A logarithmic reduction algorithm for quasi-birth-anddeath processes. J Appl Probab, 1993, 30(3): 650-674 · Zbl 0789.60055 · doi:10.2307/3214773 |
| [10] | Latouche G, Ramaswami V. Introduction to Matrix Analytic Methods in Stochastic Modeling. ASA-SIAM Series on Statistics and Applied Probability. Philadelphia: SIAM, 1999 · Zbl 0922.60001 · doi:10.1137/1.9780898719734 |
| [11] | Liu Y. Additive functionals for discrete-time Markov chains with applications to birthdeath processes. J Appl Probab, 2011, 48(4): 925-937 · Zbl 1231.60080 · doi:10.1239/jap/1324046010 |
| [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 · Zbl 1101.60052 · doi:10.1239/jap/1143936249 |
| [13] | Liu, Y.; Zhang, Y. H., Central limit theorems for Markov processes with applications to single birth processes (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 · Zbl 0313.60044 · doi:10.1137/1017044 |
| [16] | Meyn S P, Tweedie R L. Markov Chains and Stochastic Stability. 2nd ed. New York: Cambridge University Press, 2009 · Zbl 1165.60001 · doi:10.1017/CBO9780511626630 |
| [17] | Neuts M F. Moment formulas for the Markov renewal branching process. Adv Appl Probab, 1976, 8(4): 690-711 · Zbl 0379.60081 · doi:10.2307/1425930 |
| [18] | Neuts M F. Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach. Baltimore: The Johns Hopkins University Press, 1981 · Zbl 0469.60002 |
| [19] | Neuts M F. Structured Stochastic Matrices of M/G/1 Type and Their Applications. New York: Marcel Dekker, 1989 · Zbl 0695.60088 |
| [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 · Zbl 1259.60083 · doi:10.1080/15326349.2012.726038 |
| [21] | Whitt W. Asymptotic formulas for Markov processes with applications to simulation. Oper Res, 1992, 40: 279-291 · Zbl 0748.60062 · doi:10.1287/opre.40.2.279 |
| [22] | Zhao, Y. Q.; Latouche, G. (ed.); Taylor, P. G (ed.), Censoring technique in studying block-structured Markov chains, 417-433 (2000), NJ |
| [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 · 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
