Matrix-analytic methods for solving Poisson’s equation with applications to Markov chains of GI/G/1-type. (English) Zbl 1523.60126
Let \(P=(P(i,j))_{i,j\in E}\) be the transition matrix of a discrete-time Markov chain \(\mathbf{\Phi}=\{\Phi_k,k\geq 0\}\) on a finite or infinitely countable state space \(E\). Assume that \(P\) is irreducible and positive recurrent with the unique invariant probability distribution \(\boldsymbol{\pi}\). Let \(\boldsymbol{g}: E\to \mathbb{R}\) be a function satisfying \(\int_E|\boldsymbol{g}|d\boldsymbol{\pi}<\infty\). For the transition matrix \(P\) and a function \(\boldsymbol{g}\), Poisson’s equation is as follows:
\[
(I-P)\boldsymbol{f}=\bar{\boldsymbol{g}},
\]
where \(I\) is the identity matrix and \(\bar{\boldsymbol{g}}=\boldsymbol{g}-(\int_E \boldsymbol{g}d\boldsymbol{\pi})\boldsymbol{e}\), and \(\boldsymbol{e}\) is a column vector of ones.
Poisson’s equation has an essential influence on the development of Markov chain theory, and has a lot of applications in many fields including machine learning.
In this interesting paper, the authors develop matrix-analytic methods for solving Poisson’s equation for irreducible and positive recurrent discrete-time Markov chains, consider two special solutions, including the deviation matrix \(D\) and the expected additive-type functional matrix \(K\), apply the results to Markov chains of \(GI/G/1\)-type and \(MAP/G/1\) queues with negative customers, and investigate some extensions to continuous-time Markov chains.
Poisson’s equation has an essential influence on the development of Markov chain theory, and has a lot of applications in many fields including machine learning.
In this interesting paper, the authors develop matrix-analytic methods for solving Poisson’s equation for irreducible and positive recurrent discrete-time Markov chains, consider two special solutions, including the deviation matrix \(D\) and the expected additive-type functional matrix \(K\), apply the results to Markov chains of \(GI/G/1\)-type and \(MAP/G/1\) queues with negative customers, and investigate some extensions to continuous-time Markov chains.
Reviewer: Ze-Chun Hu (Chengdu)
MSC:
| 60J10 | Markov chains (discrete-time Markov processes on discrete state spaces) |
| 60J22 | Computational methods in Markov chains |
| 60J27 | Continuous-time Markov processes on discrete state spaces |
Keywords:
Markov chains; Poisson’s equation; matrix-analytic methods; Markov chains of \(GI/G/1\) -type; deviation matrix; expected additive-type functional matrix; \(MAP/G/1\) queuesReferences:
| [1] | Asmussen, S., Applied Probability and Queues, 2nd ed., Springer, New York, 2003. · Zbl 1029.60001 |
| [2] | Barlow, J. L., Stable computation with the fundamental matrix of a Markov chain, SIAM J. Matrix Anal. Appl., 22 (2000), pp. 230-241. · Zbl 1049.65031 |
| [3] | Bertsekas, D. P., Dynamic Programming and Optimal Control, 3rd ed., Athena Scientific, Cambridge, 2007. · Zbl 1209.90343 |
| [4] | Bini, D., Dendievel, S., Latouche, G., and Meini, B., General solution of the Poisson equation for Quasi-Birth-and-Death processes, SIAM J. Appl. Math., 76 (2016), pp. 2397-2417. · Zbl 1352.65124 |
| [5] | Bini, D. A., Latouche, G., and Meini, B., Numerical Methods for Structured Markov Chains, Oxford University Press, Oxford, 2005. · Zbl 1076.60002 |
| [6] | Bladt, M., The variance constant for the actual waiting time of the PH/PH/1 queue, Ann. Appl. Prob., 6 (1996), pp. 766-777. · Zbl 0881.60079 |
| [7] | Boucher, T. R., A Hoeffding inequality for Markov chains using a generalized inverse, Statist. Probab. Lett., 79 (2009), pp. 1105-1107. · Zbl 1170.60025 |
| [8] | Campbell, S. L. and Meyer, C. D., Generalized Inverses of Linear Transformations, Dover Publications, New York, 1991. · Zbl 0732.15003 |
| [9] | Chen, M. and Zhang, Y., Unified representation of formulas for single birth processes, Front. Math. China, 9 (2014), pp. 761-796. · Zbl 1318.60085 |
| [10] | Coolen-Schrijner, P. and Van Doorn, E. A., The deviation matrix of a continuous-time Markov chain, Probab. Engrg. Inform. Sci., 16 (2002), pp. 351-366. · Zbl 1011.60057 |
| [11] | da Silva Soares, A. and Latouche, G., Matrix-analytic methods for fluid queues with finite buffers, Perform. Eval., 63 (2006), pp. 295-314. |
| [12] | Dendievel, S., Latouche, G., and Liu, Y., Poisson’s equation for discrete-time quasi-birth-and-death processes, Perform. Eval., 70 (2013), pp. 564-577. |
| [13] | Glynn, P. W., Poisson’s equation for the recurrent M/G/1 queue, Adv. Appl. Probab., 26 (1994), pp. 1044-1062. · Zbl 0820.60073 |
| [14] | Glynn, P. W. and Infanger, A., Solutions of Poisson’s Equation for Stochastically Monotone Markov Chains, preprint, https://arxiv.org/abs/2202.10578, 2022. |
| [15] | Glynn, P. W. and Infanger, A., Solving Poisson’s Equation: Existence, Uniqueness, Martingale Structure, and CLT, preprint, https://arxiv.org/abs/2202.10404, 2022. |
| [16] | Glynn, P. W. and Meyn, S. P., A Liapounov bound for solutions of the Poisson equation, Ann. Probab., 24 (1996), pp. 916-931. · Zbl 0863.60063 |
| [17] | Glynn, P. W. and Ormoneit, D., Hoeffding’s inequality for uniformly ergodic Markov chains, Statist. Probab. Lett., 56 (2002), pp. 143-146. · Zbl 0999.60019 |
| [18] | Grassmann, W. K. and Heyman, D. P., Equilibrium distribution of block-structured Markov chains with repeating rows, J. Appl. Probab., 27 (1990), pp. 557-576. · Zbl 0716.60076 |
| [19] | Harrison, P. G. and Pitel, E., The M/G/1 queue with negative customers, Adv. Appl. Probab., 28 (1996), pp. 540-566. · Zbl 0861.60088 |
| [20] | He, Q., Fundamentals of Matrix-Analytic Methods, Springer, New York, 2014. · Zbl 1278.68013 |
| [21] | Jiang, S., Liu, Y., and Tang, Y., A unified perturbation analysis framework for countable Markov chains, Linear Algebra Appl., 529 (2017), pp. 413-440. · Zbl 1370.60118 |
| [22] | Jiang, S., Liu, Y., and Yao, S., Poisson’s equation for discrete-time single-birth processes, Statist. Probab. Lett., 85 (2014), pp. 78-83. · Zbl 1326.60122 |
| [23] | Kemeny, J. G., Snell, J. L., and Knapp, A. K., Denumerable Markov Chains, Van Nostrand, New York, 1966. · Zbl 0149.13301 |
| [24] | Latouche, G. and Ramaswami, V., Introduction to Matrix Analytic Methods in Stochastic Modeling, , SIAM, Philadelphia, 1999. · Zbl 0922.60001 |
| [25] | Li, Q. and Zhao, Y. Q., A MAP/G/1 queue with negative customers, Queueing Syst., 47 (2004), pp. 5-43. · Zbl 1048.60073 |
| [26] | Liu, J., Liu, Y., and Zhao, Y. Q., Augmented truncation approximations to the solution of Poisson’s equation for Markov chains, Appl. Math. Comput., 414 (2022), 126610. · Zbl 1510.60069 |
| [27] | Liu, Y., Additive functionals for discrete-time Markov chains with applications to birth-death processes, J. Appl. Probab., 48 (2011), pp. 925-937. · Zbl 1231.60080 |
| [28] | Liu, Y., Perturbation bounds for the stationary distributions of Markov chains, SIAM J. Matrix Anal. Appl., 33 (2012), pp. 1057-1074. · Zbl 1264.60052 |
| [29] | Liu, Y. and Li, W., Error bounds for augmented truncation approximations of Markov chains via the perturbation method, Adv. Appl. Probab., 50 (2018), pp. 645-669. · Zbl 1431.60076 |
| [30] | Liu, Y. and Liu, J., Hoeffding’s inequality for Markov processes via solution of Poisson’s equation, Front. Math. China, 16 (2021), pp. 543-558. · Zbl 1482.60094 |
| [31] | Liu, Y., Wang, P., and Xie, Y., Deviation matrix and asymptotic variance for GI/M/1-type Markov chains, Front. Math. China, 9 (2014), pp. 863-880. · Zbl 1308.60090 |
| [32] | Makowski, A. M. and Shwartz, A., The Poisson equation for countable Markov chains: Probabilistic methods and interpretations, in Handbook of Markov Decision Processes, Feinberg, E. A. and Shwartz, A., eds., Kluwer Academic, Norwell, MA, 2002, pp. 269-303. · Zbl 1014.90111 |
| [33] | Mao, Y., Tai, Y., Zhao, Y. Q., and Zou, J., Ergodicity for the GI/G/1-type Markov chain, J. Appl. Probab. Stat., 9 (2014), pp. 31-44. · Zbl 1315.60084 |
| [34] | Masuyama, H., Error bounds for last-column-block-augmented truncations of block-structured Markov chains, J. Oper. Res. Soc. Jpn., 60 (2017), pp. 271-320. · Zbl 1387.90069 |
| [35] | Masuyama, H., Katsumata, Y., and Kimura, T., A Subgeometric Convergence Formula for Finite-Level M/G/1-Type Markov Chains via the Poisson Equation of the Deviation Matrix, preprint, https://arxiv.org/abs/1809.03179, 2018. |
| [36] | Meyer, C. D., The role of the group generalized inverse in the theory of finite Markov chains, SIAM Rev., 17 (1975), pp. 443-464. · Zbl 0313.60044 |
| [37] | Meyn, S. and Tweedie, R. L., Markov Chains and Stochastic Stability, 2nd ed., Cambridge University Press, Cambridge, 2009. · Zbl 1165.60001 |
| [38] | Mijatović, A. and Vogrinc, J., On the Poisson equation for Metropolis-Hastings chains, Bernoulli, 24 (2018), pp. 2401-2428. · Zbl 1429.65010 |
| [39] | Mijatović, A. and Vogrinc, J., Asymptotic variance for random walk Metropolis chains in high dimensions: Logarithmic growth via the Poisson equation, Adv. Appl. Probab., 51 (2019), pp. 994-1026. · Zbl 1427.60146 |
| [40] | Neuts, M. F., Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach, The Johns Hopkins University Press, Baltimore, MD, 1981. · Zbl 0469.60002 |
| [41] | Neuts, M. F., Structured Stochastic Matrices of M/G/1 Type and Their Applications, Marcel Dekker, New York, 1989. · Zbl 0695.60088 |
| [42] | Niño-Mora, J., Solving Poisson’s equation for birth-death chains: Structure, instability, and accurate approximation, Perform. Eval., 145 (2021), 102163. |
| [43] | Shen, Y., Stannat, W., and Obermayer, K., Risk-sensitive Markov control processes, SIAM J. Control Optim., 51 (2013), pp. 3652-3672. · Zbl 1287.60085 |
| [44] | Wang, J. and Zhang, Y., Moments of integral-type downward functionals for single death processes, Front. Math. China, 15 (2020), pp. 749-768. · Zbl 1450.60048 |
| [45] | Zhao, Y. Q., Censoring technique in studying block-structured Markov chains, in Advances in Algorithmic Methods for Stochastic Models, Notable Publications, Neshani Station, NJ, 2000, pp. 417-433. |
| [46] | Zhao, Y. Q., Li, W., and Braun, W. J., Factorization, spectral analysis and fundamental matrix for transition matrices with block-repeating entries, Methodol. Comput. Appl., 5 (2003), pp. 35-58. · Zbl 1022.60073 |
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.
