Premium
An elementary analysis of a procedure for sampling points in a convex body
Author(s) -
Bubley Russ,
Dyer Martin,
Jerrum Mark
Publication year - 1998
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/(sici)1098-2418(199805)12:3<213::aid-rsa1>3.0.co;2-y
Subject(s) - isoperimetric inequality , mathematics , convex body , dimension (graph theory) , elementary proof , convergence (economics) , regular polygon , sampling (signal processing) , polynomial , pure mathematics , combinatorics , calculus (dental) , discrete mathematics , mathematical analysis , convex hull , computer science , geometry , filter (signal processing) , economics , computer vision , economic growth , medicine , dentistry
In this paper we describe a new method for proving the polynomial‐time convergence of an algorithm for sampling (almost) uniformly at random from a convex body in high dimension. Previous approaches have been based on estimating conductance via isoperimetric inequalities. We show that a more elementary coupling argument can be used to give a similar result. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12, 213–235, 1998