Quantitative bounds on convergence of time-inhomogeneous Markov chains

Abstract

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.

Published at http://dx.doi.org/10.1214/105051604000000620 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Cited by in corpus (28)

• General state space Markov chains and MCMC algorithms
• Renewal theory and computable convergence rates for geometrically ergodic Markov chains
• Convergence of adaptive and interacting Markov chain Monte Carlo algorithms
• A Simulated Annealing Approach to Approximate Bayes Computations
• Subgeometric rates of convergence of Markov processes in the Wasserstein metric
• Convergence properties of pseudo-marginal Markov chain Monte Carlo algorithms
• Nonasymptotic bounds on the estimation error of MCMC algorithms
• A mixture representation of πwith applications in Markov chain Monte Carlo and perfect sampling
• Rigorous confidence bounds for MCMC under a geometric drift condition
• Ergodicity of Lévy-driven SDEs arising from multiclass many-server queues
• Non-asymptotic Error Bounds for Sequential MCMC and Stability of Feynman-Kac Propagators
• Merging for inhomogeneous finite Markov chains, part II: Nash and log-Sobolev inequalities
• On the Stability of Sequential Monte Carlo Methods in High Dimensions
• Bounding the error of discretized Langevin algorithms for non-strongly log-concave targets
• Error bounds for augmented truncations of discrete-time block-monotone Markov chains under subgeometric drift conditions
• Time inhomogeneous Markov chains with wave-like behavior
• Theoretical guarantees for approximate sampling from smooth and log-concave densities
• Adaptive parallel tempering algorithm
• Some remarks on MCMC estimation of spectra of integral operators
• Near-Optimal Algorithms for Differentially-Private Principal Components
• Nonasymptotic bounds on the estimation error for regenerative MCMC algorithms
• On estimation of expectation of simultaneous renewal time of time-inhomogeneous Markov chains using dominating sequence
• Numerical simulation of polynomial-speed convergence phenomenon
• An estimate for an expectation of the simultaneous renewal for time-inhomogeneous Markov chains
• Exponential speed up in Monte Carlo sampling through Radial Updates
• Ergodic properties of some Markov chains models in random environments
• On Average Risk-sensitive Markov Control Processes
• Rademacher complexity for Markov chains : Applications to kernel smoothing and Metropolis-Hasting