Comment by simonbyrne

A couple of problems with the authors definition:

> Let D be a distribution over a finite set X.

In statistics, the space is almost always continuous (i.e. non-finite), typically some moderate-to-high-dimensional Euclidean space (or subset thereof).

> You are given black-box access to the probability distribution function f(x) which outputs the probability of drawing x \in X according to D.

If you know the distribution function, you can do inverse transform sampling. MCMC is typically used when the density function is only known up to proportionality (which seems to be what he actually means).

> Design an efficient randomized algorithm A which outputs an element of X so that the probability of outputting x is approximately f(x).

Now, here's the problem: MCMC doesn't actually give you this. What you get instead is a sequence of random elements, which (given some minor conditions) will converge to the target distribution.