Among Markov chain Monte Carlo (MCMC) algorithms, coupling from the past is a method for sampling from the stationary distribution of a Markov chain.
Contrary to many MCMC algorithms, coupling from the past gives in principle a perfect sample from the stationary distribution.
It was invented by James Propp and David Wilson in 1996.
Consider a finite state irreducible aperiodic Markov chain
with state space
and (unique) stationary distribution
Suppose that we come up with a probability distribution
on the set of maps
with the property that for every fixed
is distributed according to the transition probability of
be independent samples from
is chosen randomly according to
and is independent from the sequence
-stationary and our assumption on the law of
Define Then it follows by induction that
The algorithm then involves finding some
The design of a good distribution
is not too costly is not always obvious, but has been accomplished successfully in several important instances.
[1] There is a special class of Markov chains in which there are particularly good choices for
and a tool for determining if
denotes cardinality.)
, which has a unique minimal element
and a unique maximal element
may be chosen to be supported on the set of monotone maps
The algorithm can proceed by choosing
, sampling the maps
the algorithm proceeds by doubling
and repeating as necessary until an output is obtained.
(But the algorithm does not resample the maps
which were already sampled; it uses the previously sampled maps when needed.)