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.

[Oops, your browser will not display java applets.]

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.)

• Use 'f' and 's' to make the chain run faster or slower;
• Use 'r' to restart the simulation;
• Use '+' and '-' to modify the value N (and restart);
• Use 'j' to jump to the end of a particular run;
• Use 'p' to pause or unpause the run;
• Use 'l' to redraw the screen, or 'L' to toggle the forced continuous redrawing of the screen (marked as *).

Coupling from the past is an interesting new way to simulate exactly from a distribution, using only a Markov chain for which that distribution is stationary.

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.

Applet by Jeffrey S. Rosenthal (contact me).