# Perturbation theory for Markov chains via Wasserstein distance

arXiv: https://arxiv.org/abs/1503.04123 · HTML: https://mlsanity.com/paper/1503.04123/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Mar 2015.

## Built on by (most cited first, 18 of 18)

- [Bayesian Imaging With Data-Driven Priors Encoded by Neural Networks: Theory, Methods, and Algorithms](https://mlsanity.com/paper/2103.10182/) (2021)
- [On the Regularity of Attention](https://mlsanity.com/paper/2102.05628/) (2021)
- [On the generalization of learning algorithms that do not converge](https://mlsanity.com/paper/2208.07951/) (2022)
- [Uniform-in-Time Wasserstein Stability Bounds for (Noisy) Stochastic Gradient Descent](https://mlsanity.com/paper/2305.12056/) (2023)
- [Geometric convergence of elliptical slice sampling](https://mlsanity.com/paper/2105.03308/) (2021)
- [Error Bounds of the Invariant Statistics in Machine Learning of Ergodic Ito Diffusions](https://mlsanity.com/paper/2105.10102/) (2021)
- [Convergence and Optimality of Policy Gradient Methods in Weakly Smooth Settings](https://mlsanity.com/paper/2111.00185/) (2021)
- [Bounding Wasserstein distance with couplings](https://mlsanity.com/paper/2112.03152/) (2021)
- [A fast asynchronous MCMC sampler for sparse Bayesian inference](https://mlsanity.com/paper/2108.06446/) (2021)
- [Reversibility of elliptical slice sampling revisited](https://mlsanity.com/paper/2301.02426/) (2023)
- [Data-driven abstractions via adaptive refinements and a Kantorovich metric [extended version]](https://mlsanity.com/paper/2303.17618/) (2023)
- [Hoeffding's Inequality for Markov Chains under Generalized Concentrability Condition](https://mlsanity.com/paper/2310.02941/) (2023)
- [Privacy of SGD under Gaussian or Heavy-Tailed Noise: Guarantees without Gradient Clipping](https://mlsanity.com/paper/2403.02051/) (2024)
- [Generalization Bounds for Markov Algorithms through Entropy Flow Computations](https://mlsanity.com/paper/2502.07584/) (2025)
- [Bayesian Signal Component Decomposition via Diffusion-within-Gibbs Sampling](https://mlsanity.com/paper/2602.10792/) (2026)
- [Deterministic Denominator Design for Localized Tamed Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/2606.10559/) (2026)
- [Conditional Flow Matching for Transport Between Markov Processes](https://mlsanity.com/paper/2610.07229/) (2026)
- [Semi-Amortized Bayesian Inference with Reusable Local Posteriors](https://mlsanity.com/paper/2610.18945/) (2026)

## Abstract (arXiv)

Perturbation theory for Markov chains addresses the question how small differences in the transitions of Markov chains are reflected in differences between their distributions. We prove powerful and flexible bounds on the distance of the nth step distributions of two Markov chains when one of them satisfies a Wasserstein ergodicity condition. Our work is motivated by the recent interest in approximate Markov chain Monte Carlo (MCMC) methods in the analysis of big data sets. By using an approach based on Lyapunov functions, we provide estimates for geometrically ergodic Markov chains under weak assumptions. In an autoregressive model, our bounds cannot be improved in general. We illustrate our theory by showing quantitative estimates for approximate versions of two prominent MCMC algorithms, the Metropolis-Hastings and stochastic Langevin algorithms.