Explaining the Perfect Sampler
George Casella, Michael Lavine and Christian Robert
Abstract In 1996, Propp and Wilson introduced Coupling from
the Past, an algorithm for generating a sample from the exact stationary
distribution of a Markov chain. In 1998, Fill proposed another so-called
perfect sampling algorithm. These algorithms have enormous potential
in Markov Chain Monte Carlo problems because they eliminate the need to
monitor convergence and mixing of the chain. This article provides a brief
introduction to the algorithms, with an emphasis on understanding rather
than technical detail.
The manuscript is available in postscript format.