Fast MCMC sampling algorithms on polytopes

Sampling from distributions is a core problem in statistics, probability, operations research, and other areas involving stochastic models [Gem84; Bré91; Rip87; Has70]. Sampling algorithms are a prerequisite for applying Monte Carlo methods to order to approximate expectations and other integrals. Recent decades have witnessed great success of Markov Chain Monte Carlo (MCMC) algorithms; for instance, see the handbook [Bro11] and references therein. These methods are based on constructing a Markov chain whose stationary distribution is equal to the target distribution, and then drawing samples by simulating the chain for a certain number of steps. An advantage of MCMC algorithms is that they only require knowledge of the target density up to a proportionality constant. However, the theoretical understanding of MCMC algorithms used in practice is far from complete. In particular, a general challenge is to bound the mixing time of a given MCMC algorithm, meaning the number of iterations--as a function of the error tolerance δ, problem dimension d and other parameters--for the chain to arrive at a distribution within distance δ of the target. In this paper, we study a certain class of MCMC algorithms designed for the problem of drawing samples from the uniform distribution over a polytope.