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

Understand

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 $\mathbb{R}^{n}$ with diameter $D$, the mixing time of the Coordinate Hit-and-Run (CHAR) algorithm on $K$ is polynomial in $n$ and $D$.