Quantitative bounds for Markov chain convergence: Wasserstein and total variation distances

Abstract

We present a framework for obtaining explicit bounds on the rate of convergence to equilibrium of a Markov chain on a general state space, with respect to both total variation and Wasserstein distances. For Wasserstein bounds, our main tool is Steinsaltz's convergence theorem for locally contractive random dynamical systems. We describe practical methods for finding Steinsaltz's "drift functions" that prove local contractivity. We then use the idea of "one-shot coupling" to derive criteria that give bounds for total variation distances in terms of Wasserstein distances. Our methods are applied to two examples: a two-component Gibbs sampler for the Normal distribution and a random logistic dynamical system.

Published in at http://dx.doi.org/10.3150/09-BEJ238 the Bernoulli (http://isi.cbs.nl/bernoulli/) by the International Statistical Institute/Bernoulli Society (http://isi.cbs.nl/BS/bshome.htm)

References in corpus (1)

• General state space Markov chains and MCMC algorithms

Cited by in corpus (15)

• Mixing Time Guarantees for Unadjusted Hamiltonian Monte Carlo
• Practical bounds on the error of Bayesian posterior approximations: A nonasymptotic approach
• Validated Variational Inference via Practical Posterior Error Bounds
• Mixing of Metropolis-Adjusted Markov Chains via Couplings: The High Acceptance Regime
• On the limitations of single-step drift and minorization in Markov chain convergence analysis
• Convergence Rates for Hierarchical Gibbs Samplers
• Central Limit Theorems for Markov Chains from Wasserstein Convergence Rates
• Limit behavior of the invariant measure for Langevin dynamics
• Perturbation theory and uniform ergodicity for discrete-time Markov chains
• On the Capacity of Multilevel NAND Flash Memory Channels
• On the convergence of the Metropolis-Hastings Markov chains
• Convergence bound in total variation for an image restoration model
• Estimating MCMC convergence rates using common random number simulation
• Lack of phase transitions in staggered magnetic systems. A comparison of uniqueness criteria
• Ballistic Convergence in Hit-and-Run Monte Carlo and a Coordinate-free Randomized Kaczmarz Algorithm