Exact Sampling for Bayesian Inference: Towards General Purpose Algorithms
P. L. Green, Duncan J. Murdoch · 1999
Abstract There are now methods for organising a Markov chain Monte Carlo simulation sb that it can be guaranteed that the state of the process at a given time is exactly drawn from the target distribution. The question of assessing convergence totally vanishes. Such methods are known as exact or perfect sampling. The approach that has received most attention uses the protocol of coupling from the past devised by Propp and Wilson (Random Structures and Algorithms, 1996), in which multiple dependent paths of the chain are run from different initial states at a sequence of initial times going backwards into the past, until they satisfy the condition of coalescence by time 0. When this is achieved the state at time 0 is distributed according to the required target. This process must be implemented very carefully to assure its validity (including appropriate re-use of random number streams), and also requires use of various tricks to enable us to follow infinitely many sample paths with a finite amount of work.