Gibbs sampling, also known as Coordinate Hit-and-Run (CHAR), is a Markov chain for sampling from high-dimensional distributions. In each step, the algorithm selects a random coordinate and resamples 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 CHAR for sampling from a convex body K in R^n mixes in poly(n, R/r) 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 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.
This is joint work with Aditi Laddha.
Copyright. All Rights Reserved.