QUANTITATIVE CONVERGENCE RATES OF MARKOV CHAINS: A SIMPLE ACCOUNT

By Jeffrey S. Rosenthal. 2002

98 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/49682de7eedda10c5454373a009d21572a6756b8

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

Yet Another Look at Harris’ Ergodic Theorem for Markov Chains (2008, background): “There have been other variations which have made use of Poisson equations or worked at getting explicit constants [1, 3, 4, 8, 11, 13].”
General state space Markov chains and MCMC algorithms (2004, background): “The main MCMC convergence questions are, is Pn(x,A) “close” to π(A) for large enough n?”
An analysis of reinforcement learning with function approximation (2008, background): “-Coste, 1996; Rosenthal, 2002).”
Quantitative bounds on convergence of time-inhomogeneous Markov chains (2004, methodology): “The problem of getting explicit bounds on ‖Pn(x, ·)− π‖f has received much attention in recent years, motivated by control of convergence for Markov chain Monte Carlo and operation research problems [see, e.g., Jones and Hobert (2001)].”
Theoretical guarantees for approximate sampling from smooth and log‐concave densities (2014, background): “To the best of our knowledge, first computable bounds on the constants involved in the geometric convergence of Markov chains were derived in (Meyn and Tweedie, 1994), see also subsequent work (Douc et al., 2004; Rosenthal, 2002) and the survey paper (Roberts and Rosenthal, 2004).”
Renewal theory and computable convergence rates for geometrically ergodic Markov chains (2005, methodology): “0 is a direct consequence of [ 19 ], Theorem 1. For various developments and extensions of this method, see also [2, 4, 15].”
On adaptive Markov chain Monte Carlo algorithms (2005, methodology): “For an interactive version of a related example, see Rosenthal (2004).”
Optimal Proposal Distributions and Adaptive MCMC (2008, background): “This definition concerns distributional convergence (in total variation distance) as studied theoretically in e.g. Rosenthal (1995, 2002) and Roberts and Tweedie (1999).”
Gibbs sampling, exponential families and orthogonal polynomials (2008, background): “His paper [97] is a nice expository account.”
Variance bounding Markov chains. (2008, background): “[34], [35], [14], [15]), qualitative convergence rates such as geometric ergodicity (e.”
Coupling and Ergodicity of Adaptive Markov Chain Monte Carlo Algorithms (2007, methodology): “We shall construct a coupling which depends on the target time K (cf Roberts and Rosenthal (2002)), to prove that L(XK) ≈ π(·).”