Algorithms for Sampling Convex Bodies

We discuss two Markov chain Monte Carlo algorithms for uniformly sampling convex bodies. The first is Gibbs sampling, also known as Coordinate Hit-and-Run (CHAR). In each step, the algorithm selects a random coordinate and re-samples that coordinate from the distribution induced by fixing all the other coordinates. This is joint work with Santosh Vempala. The second, weighted Dikin Walk, uses a convex barrier function, via its Hessian, to define an ellipsoid centered at each interior point of a convex body. At each step, it picks a uniformly random point in the ellipsoid centered at the current point. This is joint work with Yin Tat Lee and Santosh Vempala.