MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

3 Added another reference, a bit more useful.

I believe the primary method to generate uniform samples , at least in convex polytopes , is via a Markov-chain random walk. For example, the paper by Ravi Kannan and Hariharan Narayanan, "Random walks on polytopes and an affine interior point method for linear programming," STOC 2009, (ACM link) achieves a strongly polynomial mixing time. The basic idea is explained in these older notes by H.E. Romeijn and R.L Smith, "Sampling through Random Walks," (PDF), or, perhaps better, Santosh Vempala's 2008 notes on Algorithmic Convex Geometry (PDF).

The Kannan-Narayanan paper gives a condensed history of algorithms to find (approximately) the volume of a convex polytope, starting from the Dyer, Frieze, and Kannan paper from 1991 whose mixing time was $O(n^{23})$ for a polytope in $\mathbb{R}^n$, through a series of steady improvements reducing the dependency on $n$ down to closer to $n^2$. I am not certain this is the latest word on this topic.

2 Added a bit more detail.

I believe the primary method to generate uniform samples, at least in convex polytopes, is via a Markov-chain random walk. For example, the paper by Ravi Kannan and Hariharan Narayanan, "Random walks on polytopes and an affine interior point method for linear programming," STOC 2009, (ACM link) achieves a strongly polynomial mixing time. The basic idea is explained in these older notes by H.E. Romeijn and R.L Smith, "Sampling through Random Walks," (PDF). The Kannan-Narayanan paper gives a condensed history of algorithms to find (approximately) the volume of a convex polytope, starting from the Dyer, Frieze, and Kannan paper from 1991 whose mixing time was $O(n^{23})$ for a polytope in $\mathbb{R}^n$, through a series of steady improvements reducing the dependency on $n$ down to closer to $n^2$. I am not certain this is the latest word on this topic.

1

I believe the primary method to generate uniform samples, at least in convex polytopes, is via a Markov-chain random walk. For example, the paper by Ravi Kannan and Hariharan Narayanan, "Random walks on polytopes and an affine interior point method for linear programming," STOC 2009, (ACM link) achieves a strongly polynomial mixing time. The basic idea is explained in these older notes by H.E. Romeijn, "Sampling through Random Walks," (PDF).