×

Sensitivity and convergence of uniformly ergodic Markov chains. (English) Zbl 1092.60027

Summary: For uniformly ergodic Markov chains, we obtain new perturbation bounds which relate the sensitivity of the chain under perturbation to its rate of convergence to stationarity. In particular, we derive sensitivity bounds in terms of the ergodicity coefficient of the iterated transition kernel, which improve upon the bounds obtained by other authors. We discuss convergence bounds that hold in the case of finite state space, and consider numerical examples to compare the accuracy of different perturbation bounds.

MSC:

60J05 Discrete-time Markov processes on general state spaces
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
60J35 Transition functions, generators and resolvents
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anisimov, V. V. (1988). Estimates for the deviations of the transition characteristics of nonhomogeneous Markov processes. Ukrainian Math. J. 40 , 588–592. · Zbl 0711.60065 · doi:10.1007/BF01057174
[2] 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. · Zbl 0983.60062 · doi:10.1016/S0024-3795(01)00320-2
[3] Diaconis, P. and Strook, D. (1991). Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Prob. 1 , 36–61. · Zbl 0731.60061 · doi:10.1214/aoap/1177005980
[4] Dobrushin, R. (1956). Central limit theorem for non-stationary Markov chains. I. Theory Prob. Appl. 1 , 63–80. · Zbl 0093.15001
[5] Dobrushin, R. (1956). Central limit theorem for non-stationary Markov chains. II. Theory Prob. Appl. 1 ,329–383. · Zbl 0093.15001
[6] Fill, J. A. (1991). Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process. Ann. Appl. Prob. 1 , 62–87. · Zbl 0726.60069 · doi:10.1214/aoap/1177005981
[7] Horn, R. A. and Johnson, C. R. (1985). Matrix Analysis . Cambridge University Press. · Zbl 0576.15001
[8] Ingrassia, S. (1994). On the rate of convergence of the Metropolis algorithm and Gibbs sampler by geometric bounds. Ann. Appl. Prob. 4 , 347–389. · Zbl 0802.60061 · doi:10.1214/aoap/1177005064
[9] Kartashov, N. V. (1986). Inequalities in theorems of ergodicity and stability for Markov chains with common state space. I. Theory Prob. Appl. 30 , 247–259. · Zbl 0657.60088 · doi:10.1137/1130034
[10] Kartashov, N. V. (1986). Inequalities in theorems of ergodicity and stability for Markov chains with common state space. II. Theory Prob. Appl. 30 , 507–515. · Zbl 0619.60066 · doi:10.1137/1130063
[11] Kartashov, N. V. (1996). Strong Stable Markov Chains. VSP, Utrecht. · Zbl 0874.60082
[12] Kirkland, S. (2002). On a question concerning condition numbers for Markov chains. SIAM J. Matrix Anal. Appl. 23 , 1109–1119. · Zbl 1013.15005 · doi:10.1137/S0895479801390947
[13] Kirkland, S. (2003). Conditioning properties of the stationary distribution for a Markov chain. Electron. J. Linear Algebra 10 , 1–15. · Zbl 1022.15027
[14] Kirkland, S. (2004). Digraph-based conditioning for Markov chains. Linear Algebra Appl. 385 , 81–93. · Zbl 1056.15022 · doi:10.1016/S0024-3795(03)00495-6
[15] Kirkland, S. J. and Neumann, M. (2000). Regular Markov chains for which the transition matrix has large exponent. Linear Algebra Appl. 316 , 45–65. · Zbl 0965.15026 · doi:10.1016/S0024-3795(99)00265-7
[16] Mengersen, K. L. and Tweedie, R. L. (1996). Rates of convergence of the Hastings and Metropolis algorithms. Ann. Statist. 24 , 101–121. · Zbl 0854.60065 · doi:10.1214/aos/1033066201
[17] Meyer, C. D. (2000). Matrix Analysis and Applied Linear Algebra. SIAM, Philadelphia, PA. · Zbl 0962.15001
[18] Meyn, S. P. and Tweedie, R. L. (1994). Computable bounds for convergence rates of Markov chains. Ann. Appl. Prob. 4 , 981–1011. · Zbl 0812.60059 · doi:10.1214/aoap/1177004900
[19] Meyn, S. P. and Tweedie, R. L. (1996). Markov Chains and Stochastic Stability , 2nd edn. Springer, London. · Zbl 0925.60001
[20] Mitrophanov, A. Yu. (2003). Stability and exponential convergence of continuous-time Markov chains. J. Appl. Prob. 40 , 970–979. · Zbl 1049.60069 · doi:10.1239/jap/1067436094
[21] Neumann, M. and Xu, J. (2004). Improved bounds for a condition number of Markov chains. Linear Algebra Appl. 386 , 225–241. · Zbl 1052.65004 · doi:10.1016/j.laa.2003.12.029
[22] Pulford, G. W. \et (1995). Evaluation and estimation of various Markov models with applications to membrane channel kinetics. Biom. J. 37 , 39–63. · Zbl 0838.62100 · doi:10.1002/bimj.4710370104
[23] Roberts, G. O. and Polson, N. G. (1994). On the geometric convergence of the Gibbs sampler. J. R. Statist. Soc. B 56 , 377–384. JSTOR: · Zbl 0796.62029
[24] Roberts, G. O. and Rosenthal, J. S. (1998). On convergence rates of Gibbs samplers for uniform distributions. Ann. Appl. Prob. 8 , 1291–1302. · Zbl 0935.60054 · doi:10.1214/aoap/1028903381
[25] Roberts, G. O., Rosenthal, J. S. and Schwartz, P. O. (1998). Convergence properties of perturbed Markov chains. J. Appl. Prob. 35 , 1–11. · Zbl 0909.60049 · doi:10.1239/jap/1032192546
[26] Seneta, E. (1984). Explicit forms for ergodicity coefficients and spectrum localization. Linear Algebra Appl. 60 , 187–197. · Zbl 0594.15007 · doi:10.1016/0024-3795(84)90079-X
[27] Shmulevich, I., Dougherty, E. R. and Zhang, W. (2002). Gene perturbation and intervention in probabilistic Boolean networks. Bioinf. 18 , 1319–1331.
[28] Sinclair, A. (1992). Improved bounds for mixing rates of Markov chains and multicommodity flow. Comb. Prob. Comput. 1 , 351–370. · Zbl 0801.90039 · doi:10.1017/S0963548300000390
[29] Solan, E. and Vieille, N. (2003). Perturbed Markov chains. J. Appl. Prob. 40 , 107–122. · Zbl 1026.60090 · doi:10.1239/jap/1044476830
[30] Tierney, L. (1994). Markov chains for exploring posterior distributions. Ann. Statist. 22 , 1701–1728. · Zbl 0829.62080 · doi:10.1214/aos/1176325750
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.