Hit-and-Run from a Corner

Abstract

We show that the hit-and-run random walk mixes rapidly starting from any interior point of a convex body. This is the first random walk known to have this property. In contrast, the ball walk can take exponentially many steps from some starting points. The proof extends to sampling an exponential density over a convex body.