A New Approach to Polynomial-time Generation of Random Points in Convex Bodies

Russ Bubley, Martin Dyer and Mark Jerrum

Abstract: 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 conceptually simpler coupling argument can be used to give a similar result.

ECS-LFCS-96-343, April 1996.

This report is available in the following formats:

Previous | Index | Next