by Duncan Murdoch (Queen's University, Canada) and Jeffrey Rosenthal (University of Toronto, Canada)

Propp and Wilson (1996a,b) 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.

Unfortunately, producing an exact sample typically requires a large computational
effort. We consider the question of how to make efficient use of the sample values that
are generated. In particular, we make use of *regeneration events* (cf. Mykland *et
al.*, 1995) to aid in the analysis of MCMC runs. In a regeneration event, the chain is
in a fixed reference distribution; this allows the chain to be broken up into a series of
tours which are independent, or nearly so (though they do *not* represent draws from
the true stationary distribution).

In this paper we consider using the CFTP and related algorithms to create tours. In some cases their elements are exactly in the stationary distribution; their length may be fixed or random. This allows us to combine the precision of exact sampling with the efficiency of using entire tours.

Several algorithms and estimators are proposed and analysed.

Keywords: coupling from the past; exact sampling; perfect sampling; regeneration; tours

Full paper (Postscript, about 785K)

Back to Duncan Murdoch's home page