Premium
Random walks in a convex body and an improved volume algorithm
Author(s) -
Lovász L.,
Simonovits M.
Publication year - 1993
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240040402
Subject(s) - volume (thermodynamics) , regular polygon , convex body , random walk , algorithm , computer science , mathematics , convex optimization , geometry , physics , statistics , quantum mechanics
We give a randomized algorithm using O ( n 7 log 2 n ) separation calls to approximate the volume of a convex body with a fixed relative error. The bound is O ( n 6 log 4 n ) for centrally symmpetric bodies and for polytopes with a polynomial number of facets, and O ( n 5 log 4 n ) for centrally symmetric polytopes with a polynomial number of facets. We also give an O ( n 6 log n ) algorithm to sample a point from the uniform distribution over a convex body. Several tools are developed that may be interesting on their own. We extend results of Sinclair–Jerrum [43] and the authors [34] on the mixing rate of Markov chains from finite to arbitrary Markov chains. We also analyze the mixing rate of various random walks on convex bodies, in particular the random walk with steps from the uniform distribution over a unit ball. © 1993 John Wiley & Sons, Inc.