Abstract: The problem of approximate uniform sampling from convex bodies is an important algorithmic primitive.  The method of choice is to run an appropriate Markov chain:  several Markov chains have been proposed and analyzed, with good "mixing time" results known for many of them.

We describe a new family of Markov chains that provide another efficient solution for this problem. These chains are based on running a random walk on a classical multiscale decomposition of the body (known as the Whitney

decomposition), and the proof of efficiency depends upon an isoperimetric inequality for a metric designed to capture the properties of the chain.

The analysis of these new chains also sheds light on older methods: in particular, we obtain the first result showing that one of the oldest

Markov chains proposed for the problem: the so-called coordinate hit-and-run random walk, mixes fast even when started from a point inside the body, as long as the starting point is not too close to the boundary of the body.

Joint work with Hariharan Narayanan (TIFR) and Amit Rajaraman (MIT).

(The talk will not assume any background in convex geometry or in Markov

chain theory.)