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

DOI10.3150/09-BEJ238zbMATH Open1284.60143arXiv1102.5245WikidataQ29030176 ScholiaQ29030176MaRDI QIDQ637086FDOQ637086

Authors: Neal Madras, A. Deniz Sezer 

Publication date: 2 September 2011

Published in: Bernoulli (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (33)

• 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
• Mixing time guarantees for unadjusted Hamiltonian Monte Carlo
• Title not available (Why is that?)
• 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 ergodicity of a Metropolis-Hastings algorithm for Bayesian inference of phylogenetic branch lengths
• Optimal transportation and stationary measures for iterated function systems
• Subexponential upper and lower bounds in Wasserstein distance for Markov processes
• Convergence bound in total variation for an image restoration model
• 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
• Ergodicity of Markov Processes via Nonstandard Analysis
• 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
• Stochastic Gradient MCMC for State Space Models
• 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
• Qualitative Robustness in Bayesian Inference
• 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
• Approximation of Markov Processes by Lower Dimensional Processes via Total Variation Metrics
• Subgeometric rates of convergence in Wasserstein distance for Markov chains
• Convergence rate bounds for iterative random functions using one-shot coupling
• Computable upper bounds on the distance to stationarity for Jovanovski and Madras's Gibbs sampler
• Wasserstein-based methods for convergence complexity analysis of MCMC with applications
• Limit behavior of the invariant measure for Langevin dynamics
• Spectral telescope: convergence rate bounds for random-scan Gibbs samplers based on a hierarchical structure

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)