# Estimating Convergence of Markov chains with L-Lag Couplings

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 May 2019.

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

- [Mixing Time Guarantees for Unadjusted Hamiltonian Monte Carlo](https://mlsanity.com/paper/2105.00887/) (2021)
- [Sliced Wasserstein Variational Inference](https://mlsanity.com/paper/2207.13177/) (2022)
- [Stochastic Reweighted Gradient Descent](https://mlsanity.com/paper/2103.12293/) (2021)
- [Bounding Wasserstein distance with couplings](https://mlsanity.com/paper/2112.03152/) (2021)
- [Scalable Spike-and-Slab](https://mlsanity.com/paper/2204.01668/) (2022)
- [Optimal randomized multilevel Monte Carlo for repeatedly nested expectations](https://mlsanity.com/paper/2301.04095/) (2023)
- [Scalability of Metropolis-within-Gibbs schemes for high-dimensional Bayesian models](https://mlsanity.com/paper/2403.09416/) (2024)
- [A fast asynchronous MCMC sampler for sparse Bayesian inference](https://mlsanity.com/paper/2108.06446/) (2021)
- [Single-seed generation of Brownian paths and integrals for adaptive and high order SDE solvers](https://mlsanity.com/paper/2405.06464/) (2024)
- [Centered plug-in estimation of Wasserstein distances](https://mlsanity.com/paper/2203.11627/) (2022)
- [Linear-cost unbiased posterior estimates for crossed effects and matrix factorization models via couplings](https://mlsanity.com/paper/2410.08939/) (2024)
- [Mixing times of data-augmentation Gibbs samplers for high-dimensional probit regression](https://mlsanity.com/paper/2505.14343/) (2025)
- [Couple to Control: Joint Initial Noise Design in Diffusion Models](https://mlsanity.com/paper/2605.11311/) (2026)

## Abstract (arXiv)

Markov chain Monte Carlo (MCMC) methods generate samples that are asymptotically distributed from a target distribution of interest as the number of iterations goes to infinity. Various theoretical results provide upper bounds on the distance between the target and marginal distribution after a fixed number of iterations. These upper bounds are on a case by case basis and typically involve intractable quantities, which limits their use for practitioners. We introduce L-lag couplings to generate computable, non-asymptotic upper bound estimates for the total variation or the Wasserstein distance of general Markov chains. We apply L-lag couplings to the tasks of (i) determining MCMC burn-in, (ii) comparing different MCMC algorithms with the same target, and (iii) comparing exact and approximate MCMC. Lastly, we (iv) assess the bias of sequential Monte Carlo and self-normalized importance samplers.