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.)
-
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).
[Return to my Applets Page / Home
Page]