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

DOI10.3150/09-BEJ238MaRDI QIDQ637086zbMATH OpenWikidataFDO

Authors Neal Madras, A. Deniz Sezer

Publication date 2 September 2011

Published in Bernoulli (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1102.5245

zbMATH Keywords

Markov chainGibbs samplerWasserstein distanceconvergence ratecouplingrandom dynamical systemtotal variation distancelogistic maplocal contractivityiterated random functions

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Discrete-time Markov processes on general state spaces (60J05) Dynamical systems and their relations with probability theory and stochastic processes (37A50)

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.

Recommendations

• Convergence rates for empirical measures of Markov chains in dual and Wasserstein distances
• Subgeometric rates of convergence in Wasserstein distance for Markov chains
• Quantitative bounds of convergence for geometrically ergodic Markov chain in the Wasserstein distance with application to the Metropolis adjusted Langevin algorithm
• Geometric convergence bounds for Markov chains in Wasserstein distance based on generalized drift and contraction conditions
• Wasserstein convergence rates for random bit approximations of continuous Markov processes
• Convergence in total variation distance for (in)homogeneous Markov processes
• Subexponential upper and lower bounds in Wasserstein distance for Markov processes
• Perturbation theory for Markov chains via Wasserstein distance
• Convergence rates for discrete-time Markov chains in total variation distance
• Subgeometric rates of convergence of Markov processes in the Wasserstein metric

Cites work

• scientific article; zbMATH DE number 44579 (Why is no real title available?)
• scientific article; zbMATH DE number 53531 (Why is no real title available?)
• scientific article; zbMATH DE number 1246228 (Why is no real title available?)
• scientific article; zbMATH DE number 1069282 (Why is no real title available?)
• scientific article; zbMATH DE number 840151 (Why is no real title available?)
• A new class of markov processes for image encoding
• Convergence in the Wasserstein Metric for Markov Chain Monte Carlo Algorithms with Applications to Image Restoration
• Explicit stationary distributions for compositions of random functions and products of random matrices
• General state space Markov chains and MCMC algorithms
• Geometric ergodicity and hybrid Markov chains
• Geometric ergodicity of Gibbs and block Gibbs samplers for a hierarchical random effects model
• Honest exploration of intractable probability distributions via Markov chain Monte Carlo.
• Iterated Random Functions
• Lectures on Monte Carlo methods
• Locally contractive iterated function systems
• Markov chains and stochastic stability
• Minorization Conditions and Convergence Rates for Markov Chain Monte Carlo
• On Choosing and Bounding Probability Metrics
• One-shot CFTP; application to a class of truncated Gaussian densities
• One-shot coupling for certain stochastic recursive sequences.
• Perfect Simulation for Image Restoration
• Random logistic maps and Lyapunov exponents
• Topics in the Constructive Theory of Countable Markov Chains

Cited in

(36)

• Quantitative contraction rates for Markov chains on general state spaces
• Spectral telescope: convergence rate bounds for random-scan Gibbs samplers based on a hierarchical structure
• Lack of phase transitions in staggered magnetic systems. A comparison of uniqueness criteria
• Convergence rates of the blocked Gibbs sampler with random scan in the Wasserstein metric
• Stochastic gradient MCMC for state space models
• Mixing time guarantees for unadjusted Hamiltonian Monte Carlo
• scientific article; zbMATH DE number 653184 (Why is no real title available?)
• On the convergence complexity of Gibbs samplers for a family of simple Bayesian random effects models
• High-dimensional MCMC with a standard splitting scheme for the underdamped Langevin diffusion
• Dimension free convergence rates for Gibbs samplers for Bayesian linear mixed models
• Geometric convergence bounds for Markov chains in Wasserstein distance based on generalized drift and contraction conditions
• Geometric ergodicity of a Metropolis-Hastings algorithm for Bayesian inference of phylogenetic branch lengths
• Qualitative robustness in Bayesian inference
• Subexponential upper and lower bounds in Wasserstein distance for Markov processes
• Convergence bound in total variation for an image restoration model
• Optimal transportation and stationary measures for iterated function systems
• Mixing of Metropolis-adjusted Markov chains via couplings: the high acceptance regime
• Perturbation theory for Markov chains via Wasserstein distance
• Convergence in the Wasserstein Metric for Markov Chain Monte Carlo Algorithms with Applications to Image Restoration
• Strict Kantorovich contractions for Markov chains and Euler schemes with general noise
• Geometric ergodicity of a hybrid sampler for Bayesian inference of phylogenetic branch lengths
• Exact convergence analysis for metropolis–hastings independence samplers in Wasserstein distances
• The transport map computed by iterated function system
• Convergence rates of symmetric scan Gibbs sampler
• Convergence rates of Metropolis-Hastings algorithms
• Minimum entropy production, detailed balance and Wasserstein distance for continuous-time Markov processes
• Quantitative bounds of convergence for geometrically ergodic Markov chain in the Wasserstein distance with application to the Metropolis adjusted Langevin algorithm
• Ergodicity of Markov processes via nonstandard analysis
• A computational procedure for estimation of the mixing time of the random-scan Metropolis algorithm
• On the limitations of single-step drift and minorization in Markov chain convergence analysis
• Subgeometric rates of convergence in Wasserstein distance for Markov chains
• Approximation of Markov Processes by Lower Dimensional Processes via Total Variation Metrics
• Convergence rate bounds for iterative random functions using one-shot coupling
• Wasserstein-based methods for convergence complexity analysis of MCMC with applications
• Computable upper bounds on the distance to stationarity for Jovanovski and Madras's Gibbs sampler
• Limit behavior of the invariant measure for Langevin dynamics

This page was built for publication: Quantitative bounds for Markov chain convergence: Wasserstein and total variation distances

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q637086)