Definition
Perfect sampling (exact sampling) is a class of Markov chain Monte Carlo methods that produce draws distributed exactly according to the target (stationary) distribution, rather than only approximately as the chain length grows. The canonical construction is coupling from the past (Propp-Wilson 1996): rather than running a chain forward and hoping it has converged, one runs chains from the infinite past forward to time zero and reports a value only once all starting states have coalesced, guaranteeing the output is a draw from the stationary law (Casella-Mengersen-Robert-Titterington 2002).
Key Ideas
- Eliminates the burn-in problem. Ordinary MCMC converges to its target only asymptotically, so one never knows whether burn-in was long enough; perfect sampling replaces convergence diagnostics with a convergence guarantee.
- Coupling from the past (CFTP). Couple many chains (ideally all possible starting states) using common random numbers and run them from progressively earlier start times until they coalesce by time 0; the common value at time 0 is an exact draw.
- Monotonicity is the enabler. CFTP is dramatically cheaper when the state space carries an ordering "⪯" preserved by the Markov transition, because then only the maximal and minimal states need to be tracked — if they coalesce, all states have. Models without such monotone structure are much harder.
- Marginalization / Rao-Blackwellization. Integrating out awkward latent variables (e.g., the discrete allocation labels in a mixture) shrinks the effective state space and can restore enough structure to make a perfect scheme feasible — the same variance-reducing move used in ordinary Gibbs samplers.
- Perfect slice samplers and backward chains. A slice sampler can be made perfect by bounding and coupling its uniform "slice" variables; alternatively a single backward chain can deliver exact draws and often scales to larger problems than a slice construction.
How It Works
- Choose an MCMC transition that leaves the target invariant, and a coupling (common random numbers) so different starting states can be run in lockstep.
- If available, exploit a monotone ordering so only extreme (max/min) chains must be tracked.
- Start at time −T from all (or the extreme) states; run forward to time 0. If the chains have coalesced, output the common state; otherwise restart from −2T (reusing the same randomness) and repeat.
- For latent-variable models, marginalize the latents first to reduce the state space; use a slice or single-backward-chain construction as the coupled transition.
Why It Matters
- Certainty of exactness. For problems where the cost of an undiagnosed convergence failure is high, an exact draw is worth the extra construction effort.
- Sharpens understanding of mixing. The difficulty of building perfect samplers for a model exposes exactly where ordinary MCMC is fragile — mixtures, for instance, resist perfect sampling for the same reasons (label symmetry, weak monotonicity) that make their Gibbs samplers mix poorly.
- A methodological benchmark. Perfect samples provide a gold standard against which approximate-MCMC output and convergence diagnostics can be validated.
Open Questions
- Scalability. Coalescence times can be prohibitive; without monotonicity, tracking enough chains is expensive, and continuous-embedding shortcuts can badly distort a discrete target.
- Applicability. Many realistic models (finite mixtures, high-dimensional posteriors) lack the structure that makes CFTP efficient, which is why diagnostic-based MCMC remains the practical default.
- Design of couplings. Constructing couplings that coalesce quickly — the crux of an efficient perfect sampler — is problem-specific and something of an art.
Related