The essence of the method called “coupling from the past” is to consider running an ergodic simulatiom of a Markov chain using a sequence of random numbers with known distribution. If the simulation had been running indefinitely, then the observation at time 0 would be distributed exactly according to the stationary distribution \(\pi\) of the chain. The structure of algorithms based on this idea is as following:
One considers runs of length \(M\) ending at time 0, starting at every possible state of the chain at time \(t=-M.\) Using a sequence of random numbers, one follows the paths from each of these states forward in time and eventually all of the paths will have coalesced into one. If this has happened when one reached time 0, then we are done. If there are still multiple possible states, one chooses a larger value of \(M\) and starts again. The result is an unbiased sample.
The present paper addresses the question of extending coupling from the past to deal with continuous target distributions. The authors show that many common “coupled Markov chain Monte Carlo” algorithms can be recast in a form in which large collections of states are all updated to a single new state. This provides the necessary discretization of the state space, and the “coupling from the past” algorithm may then be used to obtain exact samples from the limiting distribution. The authors apply some of these algorithms to an example of a hierarchical Bayes model.