# Convergence of Gibbs Sampling: Coordinate Hit-and-Run Mixes Fast

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Sep 2020.

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

- [Sampling with Riemannian Hamiltonian Monte Carlo in a Constrained Space](https://mlsanity.com/paper/2202.01908/) (2022)
- [On Sampling with Approximate Transport Maps](https://mlsanity.com/paper/2302.04763/) (2023)
- [Entropy contraction of the Gibbs sampler under log-concavity](https://mlsanity.com/paper/2410.00858/) (2024)
- [Sampling with Barriers: Faster Mixing via Lewis Weights](https://mlsanity.com/paper/2303.00480/) (2023)
- [Optimal Exploration is no harder than Thompson Sampling](https://mlsanity.com/paper/2310.06069/) (2023)
- [Oracle-based Uniform Sampling from Convex Bodies](https://mlsanity.com/paper/2510.02983/) (2025)
- [On the choice of the non-trainable internal weights in random feature maps](https://mlsanity.com/paper/2408.03626/) (2024)
- [Spectral Gaps of Hit-and-Run and Coordinate Hit-and-Run](https://mlsanity.com/paper/2608.16878/) (2026)
- [Truncated Log-concave Sampling with Reflective Hamiltonian Monte Carlo](https://mlsanity.com/paper/2102.13068/) (2021)

## Abstract (arXiv)

The Gibbs Sampler is a general method for sampling high-dimensional distributions, dating back to Turchin, 1971. In each step of the Gibbs Sampler, we pick a random coordinate and re-sample that coordinate from the distribution induced by fixing all other coordinates. While it has become widely used over the past half-century, guarantees of efficient convergence have been elusive. We show that for a convex body K in ℝn with diameter D, the mixing time of the Coordinate Hit-and-Run (CHAR) algorithm on K is polynomial in n and D. We also give a lower bound on the conductance of CHAR, showing that it is strictly worse than hit-and-run or the ball walk in the worst case.