Quantitative Convergence Rates of Markov Chains: A Simple Account

Jeffrey S. Rosenthal (University of Toronto)

Abstract


We state and prove a simple quantitative bound on the total variation distance after k iterations between two Markov chains with different initial distributions but identical transition probabilities. The result is a simplified and improved version of the result in Rosenthal (1995), which also takes into account the $epsilon$-improvement of Roberts and Tweedie (1999), and which follows as a special case of the more complicated time-inhomogeneous results of Douc et al. (2002). However, the proof we present is very short and simple; and we feel that it is worthwhile to boil the proof down to its essence. This paper is purely expository; no new results are presented.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 123-128

Publication Date: May 10, 2002

DOI: 10.1214/ECP.v7-1054

References

  1. D.J. Aldous and H. Thorisson (1993), Shift-coupling. Stoch. Proc. Appl. 44, 1-14. Math. Review 94f:60066
  2. K.B. Athreya and P. Ney (1978), A new approach to the limit theory of recurrent Markov chains. Trans. Amer. Math. Soc. 245, 493-501. Math. Review 80i:60092
  3. P.J. Bickel and Y. Ritov (2002), Ergodicity of the conditional chain of general state space HMM. Work in progress.
  4. M.K. Cowles (2001). MCMC Sampler Convergence Rates for Hierarchical Normal Linear Models: A Simulation Approach. Statistics and Computing, to appear.
  5. M.K. Cowles and J.S. Rosenthal (1998), A simulation approach to convergence rates for Markov chain Monte Carlo algorithms. Statistics and Computing 8, 115-124.
  6. R. Douc, E. Moulines, and J.S. Rosenthal (2002), Quantitative convergence rates for inhomogeneous Markov chains. Preprint.
  7. W.R. Gilks, S. Richardson, and D.J. Spiegelhalter, eds. (1996), Markov chain Monte Carlo in practice. Chapman and Hall, London. Math. Review 97d:62006
  8. G.L. Jones and J.P. Hobert (2001), Honest exploration of intractable probability distributions via Markov chain Monte Carlo. Statistical Science 16, 312-334.
  9. T. Lindvall (1992), Lectures on the Coupling Method. Wiley & Sons, New York. Math. Review 94c:60002
  10. R.B. Lund, S.P. Meyn, and R.L. Tweedie (1996), Computable exponential convergence rates for stochastically ordered Markov processes. Ann. Appl. Prob. 6, 218-237. Math. Review 97g:60130
  11. S.P. Meyn and R.L. Tweedie (1993), Markov chains and stochastic stability. Springer-Verlag, London. Math. Review 95j:60103
  12. S.P. Meyn and R.L. Tweedie (1994), Computable bounds for convergence rates of Markov chains. Ann. Appl. Prob. 4, 981-1011. Math. Review 95j:60106
  13. E. Nummelin (1984), General irreducible Markov chains and non-negative operators. Cambridge University Press. Math. Review 87a:60074
  14. J.W. Pitman (1976), On coupling of Markov chains. Z. Wahrsch. verw. Gebiete 35, 315-322. Math. Review 54 #3854
  15. G.O. Roberts and J.S. Rosenthal (1997), Shift-coupling and convergence rates of ergodic averages. Communications in Statistics - Stochastic Models, Vol. 13, No. 1, 147-165. Math. Review 97k:60181
  16. G.O. Roberts and J.S. Rosenthal (2000), Small and Pseudo-Small Sets for Markov Chains. Communications in Statistics - Stochastic Models, to appear.
  17. G.O. Roberts and R.L. Tweedie (1999), Bounds on regeneration times and convergence rates for Markov chains. Stoch. Proc. Appl. 80, 211-229. See also the corrigendum, Stoch. Proc. Appl. 91} (2001), 337-338. Math. Review 2000b:60171
  18. G.O. Roberts and R.L. Tweedie (2000), Rates of convergence of stochastically monotone and continuous time Markov models. J. Appl. Prob. 37, 359-373. Math. Review 97k:60181
  19. J.S. Rosenthal (1995), Minorization conditions and convergence rates for Markov chain Monte Carlo. J. Amer. Stat. Assoc. 90, 558-566. Math. Review 96e:62167a
  20. J.S. Rosenthal (1996), Analysis of the Gibbs sampler for a model related to James-Stein estimators. Stat. and Comput. 6, 269-275.
  21. J.S. Rosenthal (2001), Asymptotic Variance and Convergence Rates of Nearly-Periodic MCMC Algorithms. Preprint.
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.