Hit-and-Run from a Corner
- 1 January 2006
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 35 (4) , 985-1005
- https://doi.org/10.1137/s009753970544727x
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.Keywords
This publication has 8 references indexed in Scilit:
- Hit-and-run mixes fastMathematical Programming, 1999
- An elementary analysis of a procedure for sampling points in a convex bodyRandom Structures & Algorithms, 1998
- Random walks and anO*(n5) volume algorithm for convex bodiesRandom Structures & Algorithms, 1997
- Isoperimetric problems for convex bodies and a localization lemmaDiscrete & Computational Geometry, 1995
- Random walks in a convex body and an improved volume algorithmRandom Structures & Algorithms, 1993
- A random polynomial-time algorithm for approximating the volume of convex bodiesJournal of the ACM, 1991
- Approximating the PermanentSIAM Journal on Computing, 1989
- Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed over Bounded RegionsOperations Research, 1984