Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-24T13:47:55.271Z Has data issue: false hasContentIssue false
  • English
  • Français

Error bounds for augmented truncation approximations of Markov chains via the perturbation method

Part of: Markov processes Distribution theory

Published online by Cambridge University Press:  26 July 2018

Yuanyuan Liu  and
Wendi Li
Yuanyuan Liu*
Affiliation:
Central South University
Wendi Li*
Affiliation:
Central South University
*
* Postal address: School of Mathematics and Statistics, Central South University, Changsha, Hunan, 410075, China.
* Postal address: School of Mathematics and Statistics, Central South University, Changsha, Hunan, 410075, China.
Get access Rights & Permissions [Opens in a new window]

Abstract

Let P be the transition matrix of a positive recurrent Markov chain on the integers with invariant probability vector πT, and let (n)P̃ be a stochastic matrix, formed by augmenting the entries of the (n + 1) x (n + 1) northwest corner truncation of P arbitrarily, with invariant probability vector (n)πT. We derive computable V-norm bounds on the error between πT and (n)πT in terms of the perturbation method from three different aspects: the Poisson equation, the residual matrix, and the norm ergodicity coefficient, which we prove to be effective by showing that they converge to 0 as n tends to ∞ under suitable conditions. We illustrate our results through several examples. Comparing our error bounds with the ones of Tweedie (1998), we see that our bounds are more applicable and accurate. Moreover, we also consider possible extensions of our results to continuous-time Markov chains.

Keywords

Markov chainapproximationinvariant probability vectorPoisson equationergodicity

MSC classification

Primary: 60J10: Markov chains (discrete-time Markov processes on discrete state spaces)
Secondary: 62E17: Approximations to distributions (nonasymptotic)
Type
Original Article
Information
Advances in Applied Probability , Volume 50 , Issue 2 , June 2018 , pp. 645 - 669
Copyright
Copyright © Applied Probability Trust 2018 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Abbas, K., Berkhout, J. and Heidergott, B. (2016). A critical account of perturbation analysis of Markov chains. Markov Process. Relat. Fields 22, 227–265. Google Scholar
[2]Altman, E., Avrachenkov, K. E. and Núñez-Queija, R. (2004). Perturbation analysis for denumerable Markov chains with application to queueing models. Adv. Appl. Prob. 36, 839–853. Google Scholar
[3]Asmussen, S. (2003). Applied Probability and Queues, 2nd edn. Springer, New York. Google Scholar
[4]Cao, X.-R. (2007). Stochastic Learning and Optimization: A Sensitivity-Based Approach. Springer, New York. Google Scholar
[5]Chen, M. (1999). Single birth processes. Chinese Ann. Math. B 20, 77–82. Google Scholar
[6]Cho, G. E. and Meyer, C. D. (2001). Comparison of perturbation bounds for the stationary distribution of a Markov chain. Linear Algebra Appl. 335, 137–150. Google Scholar
[7]Gibson, D. and Seneta, E. (1987). Augmented truncations of infinite stochastic matrices. J. Appl. Prob. 24, 600–608. Google Scholar
[8]Glynn, P. W. and Meyn, S. P. (1996). A Liapounov bound for solutions of the Poisson equation. Ann. Prob. 24, 916–931. Google Scholar
[9]Heidergott, B., Hordijk, A. and Leder, N. (2010). Series expansions for continuous-time Markov processes. Operat. Res. 58, 756–767. Google Scholar
[10]Ho, Y.-C. and Cao, X.-R. (1991). Perturbation Analysis of Discrete Event Dynamic Systems. Kluwer, Boston, MA. Google Scholar
[11]Hunter, J. J. (2005). Stationary distributions and mean first passage times of perturbed Markov chains. Linear Algebra Appl. 410, 217–243. Google Scholar
[12]Jiang, S., Liu, Y. and Tang, Y. (2017). A unified perturbation analysis framework for countable Markov chains. Linear Algebra Appl. 529, 413–440. Google Scholar
[13]Kartashov, N. V. (1985). Criteria for uniform ergodicity and strong stability of Markov chains with a common phase space. Theory Prob. Math. Statist. 30, 71–89. Google Scholar
[14]Kartashov, N. V. (1986). Strongly stable Markov chains. J. Soviet Math. 34, 1493–1498. Google Scholar
[15]Kartashov, N. V. (1996). Strong Stable Markov Chains. VSP, Utrecht. Google Scholar
[16]Kirkland, S. J., Neumann, M. and Sze, N.-S. (2008). On optimal condition numbers for Markov chains. Numer. Math. 110, 521–537. Google Scholar
[17]Li, H. and Zhao, Y. (2000). Stochastic block-monotonicity in the approximation of the stationary distribution of infinite Markov chains. Commun. Statist. Stoch. Models 16, 313–333. Google Scholar
[18]Liu, Y. (2010). Augmented truncation approximations of discrete-time Markov chains. Operat. Res. Lett. 38, 218–222. Google Scholar
[19]Liu, Y. (2012). Perturbation bounds for the stationary distributions of Markov chains. SIAM J. Matrix Anal. Appl. 33, 1057–1074. Google Scholar
[20]Liu, Y. (2015). Perturbation analysis for continuous-time Markov chains. Sci. China Math. 58, 2633–2642. Google Scholar
[21]Liu, Y. and Zhang, Y. (2015). Central limit theorems for ergodic continuous-time Markov chains with applications to single birth processes. Front. Math. China 10, 933–947. Google Scholar
[22]Liu, Y., Tang, Y. and Zhao, Y. (2015). Censoring technique and numerical computations of invariant distribution for continuous-time Markov chains. Scientia Sinica Math. 45, 671–682 (in Chinese). Google Scholar
[23]Mao, Y., Zhang, M. and Zhang, Y. (2013). A generalization of Dobrushin coefficient. Chinese J. Appl. Prob. Statist. 29, 489–494. Google Scholar
[24]Masuyama, H. (2015). Error bounds for augmented truncations of discrete-time block-monotone Markov chains under geometric drift conditions. Adv. Appl. Prob. 47, 83–105. Google Scholar
[25]Masuyama, H. (2016). Error bounds for augmented truncations of discrete-time block-monotone Markov chains under subgeometric drift conditions. SIAM J. Matrix Anal. Appl. 37, 877–910. Google Scholar
[26]Masuyama, H. (2017). Continuous-time block-monotone Markov chains and their block-augmented truncations. Linear Algebra Appl. 514, 105–150. Google Scholar
[27]Masuyama, H. (2017). Error bounds for last-column-block-augmented truncations of block-structured Markov chains. J. Operat. Res. Soc. Japan 60, 271–320. Google Scholar
[28]Meyer, C. D. (1994). Sensitivity of the stationary distribution of a Markov chain. SIAM J. Matrix Anal. Appl. 15, 715–728. Google Scholar
[29]Meyn, S. and Tweedie, R. L. (2009). Markov Chains and Stochastic Stability, 2nd edn. Cambridge University Press. Google Scholar
[30]Mitrophanov, A. Y. (2005). Sensitivity and convergence of uniformly ergodic Markov chains. J. Appl. Prob. 42, 1003–1014. Google Scholar
[31]Mouhoubi, Z. and Aïssani, D. (2010). New perturbation bounds for denumerable Markov chains. Linear Algebra Appl. 432, 1627–1649. Google Scholar
[32]Neuts, M. F. (1989). Structured Stochastic Matrices of M/G/1 Type and Their Aapplications. Marcel Dekker, New York. Google Scholar
[33]Seneta, E. (1979). Coefficients of ergodicity: structure and applications. Adv. Appl. Prob. 11, 576–590. Google Scholar
[34]Seneta, E. (1980). Computing the stationary distribution for infinite Markov chains. Linear Algebra Appl. 34, 259–267. Google Scholar
[35]Tweedie, R. L. (1998). Truncation approximations of invariant measures for Markov chains. J. Appl. Prob. 35, 517–536. Google Scholar
[36]Van Dijk, N. M. (2011). Error bounds and comparison results: the Markov reward approach for queueing networks. In Queueing Networks (Internat. Ser. Operat. Res. Manag. Sci. 154), Springer, New York, pp. 397–459. Google Scholar