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

Gibbs sampling, also known as Coordinate Hit-and-Run (CHAR), is a Markov chain Monte Carlo algorithm for sampling from high-dimensional distributions. In each step, the algorithm selects a random coordinate and re-samples that coordinate from the distribution induced by fixing all the other coordinates. While this algorithm has become widely used over the past half-century, guarantees of efficient convergence have been elusive. We show that the Coordinate Hit-and-Run algorithm for sampling from a convex body K in R n mixes in O ∗ (n 9 R 2 / r 2) steps, where K contains a ball of radius r and R is the average distance of a point of K from its centroid. We also give an upper bound on the conductance of Coordinate Hit-and-Run, showing that it is strictly worse than Hit-and-Run or the Ball Walk in the worst case. [ABSTRACT FROM AUTHOR]