Efficient Use of Exact Samples

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