Here is a simulation of a "coupling from the past" (CFTP) algorithm. Here the target distribution is uniform on the integers 0, 1, 2, ..., N. (Initially N=20.) The Markov chain used is a simple symmetric random walk Metropolis algorithm (i.e., it moves up or down with probability 1/2, and it rejects any move that would take it below 0 or above N). The algorithm proceeds by going far enough into the past that chain values started from all the different points of the state space, all coalesce at time 0.
See the chain run! When the upper (blue) and lower (green) processes finally coalesce, then all the chain values have coalesced, and the resulting time 0 value is a draw from the target distribution (recorded as a purple dot on the right). (Note that we have to use the same sequence of + and - for the different attempts at coalescence.) In the long run, the purple dots should be uniformly distributed over all the points. But note that it takes quite a while!
The applet accepts the following keyboard inputs. (You may need to "click" on the applet first.)
The example used in this applet was taken from the recent paper Efficient use of exact samples, by D.J. Murdoch and J.S. Rosenthal (Statistics and Computing 10:237-243, 2000), which discusses more efficient ways to make use of the exact samples generated. (See also Prof. Murdoch's available software.)
For further discussion of exact sampling techniques, see D.B. Wilson's annotated bibliography including some additional Java applets, and/or the MCMC Preprint Service.