Gibbs/Metropolis algorithms on a convex polytope
Authors:
Preprint
Abstract
This paper gives sharp rates of convergence for natural versions of the Metropolis algorithm for sampling from the uniform distribution on a convex polytope. The singular proposal distribution, based on a walk moving locally in one of a fixed, finite set of directions, needs some new tools. We get useful bounds on the spectrum and eigenfunctions using Nash and Weyl-type inequalities. The top eigenvalues of the Markov chain are closely related to the Neuman eigenvalues of the polytope for a novel Laplacian.Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Random doubly stochastic tridiagonal matricesRandom Structures & Algorithms, 2012
- Geometric analysis for the metropolis algorithm on Lipschitz domainsInventiones Mathematicae, 2010
- Semi-classical analysis of a random walk on a manifoldThe Annals of Probability, 2010
- Micro-local analysis for the Metropolis algorithmMathematische Zeitschrift, 2008
- The geometry of logconcave functions and sampling algorithmsRandom Structures & Algorithms, 2006
- Applications of geometric bounds to the convergence rate of Markov chains on RnStochastic Processes and their Applications, 2000
- Markov Chains and Stochastic StabilityJournal of the American Statistical Association, 1997
- Random walks in a convex body and an improved volume algorithmRandom Structures & Algorithms, 1993
- Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed over Bounded RegionsOperations Research, 1984