ABSTRACT
The amount of research done by the Markov chain Monte Carlo (MCMC) community has been very impressive in the last two decades, as testified by this very volume. The power of MCMC has been demonstrated in countless instances in which more traditional numerical algorithms are helpless. However, one ubiquitous problem remains: the detection of convergence or lack thereof.Among the large number of procedures designed for detecting lack of convergence or for establishing convergence bounds (see, e.g. Chapters 6 and 7 in this volume), there is one class of MCMC algorithms that stands apart simply because it avoids the problem altogether. Whereas examples of such algorithms can be traced back to at least 1989 (see [56]), it is Propp andWilson’s 1996 seminal paper [48] that introduced the general scheme of coupling from the past (CFTP). Since then, there has been an intense search for perfect sampling or exact sampling algorithms, so named because such algorithms useMarkov chains andyet obtaingenuine independent and identicallydistributed (i.i.d.) draws-hence perfect or exact-from their limiting distributions within a finite number of iterations. There is, of course, no free lunch.Whereas this is a class of very powerful algorithms, their
construction and implementation tend to require a gooddeal of labor andgreat care. Indeed, even the most basic general themes are not entirely trivial to understand, and subtleties and traps can be overwhelming for novices. Our central goal in this chapter is therefore to provide an intuitive overview of some of the most basic sampling schemes developed since [48]. We do not strive for completeness, nor for mathematical generality or rigorousness. Rather, we focus on a few basic schemes and try to explain them as intuitively as we can, via figures and simple examples. The chapter is therefore not intended for the residents but rather the visitors of the MCMC kingdom who want to tour the magic land of perfect sampling. There are of course a number of other tour packages-see, for example, the list provided at https://dimacs.rutgers.edu/∼dbwilson/exact.html, maintained by David Wilson. But we hope ours is one of the least expensive ones in terms of readers’ mental investment, though by no means are we offering a free ride.
