by Duncan Murdoch (University of Western Ontario)
Propp and Wilson (1996, 1998) described a protocol called coupling from the past (CFTP) for exact sampling from the steady-state distribution of a Markov chain Monte Carlo (MCMC) process. In it a past time is identified from which the paths of coupled Markov chains starting at every possible state would have coalesced into a single value by the present time; this value is then a sample from the steady-state distribution.
Foss and Tweedie (1998) pointed out that for CFTP to work, the underlying Markov chain must be uniformly ergodic. Unfortunately, most of the chains in common use in Bayesian inference are not, when the state space is unbounded. However, this does not mean that CFTP can't be used; in this paper we present three modifications.
The first is a simple change to the chain to induce uniform ergodicity. The second (more extensively discussed in Green and Murdoch, 1998) is a modification to CFTP due to Kendall (1998) that makes use of random bounds on particular realizations of the chain. Finally, the last method attempts to make use of Meng's (1998) multistage coupler to address the problem.
Back to Duncan Murdoch's home page.