Quantitative bounds on convergence of time-inhomogeneous Markov chains

By Randal Douc, Eric Moulines, Jeffrey S. Rosenthal. 2004

111 citations recorded by the source corpus.

Convergence rates of Markov chains have been widely studied in recent years. In particular, quantitative bounds on convergence rates have been studied in various forms by Meyn and Tweedie [Ann. Appl. Probab. 4 (1994) 981-1101], Rosenthal [J. Amer. Statist. Assoc. 90 (1995) 558-566], Roberts and Tweedie [Stochastic Process. Appl. 80 (1999) 211-229], Jones and Hobert [Statist. Sci. 16 (2001) 312-334] and Fort [Ph.D. thesis (2001) Univ. Paris VI]. In this paper, we extend a result of Rosenthal [J. Amer. Statist. Assoc. 90 (1995) 558-566] that concerns quantitative convergence rates for time-homogeneous Markov chains. Our extension allows us to consider f-total variation distance (instead of total variation) and time-inhomogeneous Markov chains. We apply our results to simulated annealing.

Subfields: Mathematical Physics, Molecular Biology, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/f79de982a27e3f2134083ecb54dc77e52bbbf323

How researchers see this paper

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

In Mathematical Physics

In Molecular Biology

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].”
Near-Optimal Algorithms for Differentially-Private Principal Components (2012, background): “There has been much theoretical work on estimating convegence times (Jones and Hobart, 2004; Douc et al., 2004; Jones and Hobart, 2001; Roberts, 1999; Roberts and Sahu, 2001; Roberts, 1999; Roberts and Sahu, 2001; Rosenthal, 1995; Kolassa, 1999, 2000), but unfortunately, most theoretical guarantees…”
Statistical estimation of a growth-fragmentation model observed on a genealogical tree (2012, background): “It is possible to obtain bounds on c so that (20) holds, by using explicit (yet intricate) bounds on γ B, V following Fort et al. or [18], Douc et al. [11], see also Baxendale [6].”
General state space Markov chains and MCMC algorithms (2004, background): “And, how large is large enough?”
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): “For various developments and extensions of this method, see also [2, 4, 15].”