Comment by mturmon

Yes, what you just wrote is evident. I'm saying, in response to your assertion above, that it is not trivial to derive a useful result about approximating the volume of convex sets with MCMC, and not at all obvious that anything smarter than independent probes will be useful. I happened to read the original 1991 paper on this topic during my PhD, so I'm still vaguely familiar with it.

To clarify: It's clear than you can approximate a convex volume with exponentially-many independent (random or deterministic) probes. That's therefore not an interesting problem.

Surprisingly: there is NO deterministic algorithm that can solve this problem in polynomial time. But, surprise #2: a randomized algorithm using MCMC can. Pretty cool.

So, this is the relevance of MCMC to the convex volume problem. Used cleverly, it can take you from exponentially-many probes to polynomial.

And in particular: You talk about "creating a bounding box" for the reference Lebesgue measure -- saying that this first step is easy is basically assuming the whole problem is solved. Because: How do you create a bounding box around a convex set in R^d, with polynomially-many probes, so that the error is bounded? You can do it with exponentially-many probes (just go out along each orthogonal axis). But that's not interesting -- if you have that many probes, forget about MCMC, just use a deterministic algorithm.

Here's a short summary: http://www.cs.berkeley.edu/~sinclair/cs294/n16.pdf