Coupling from the past explained

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.

The basic idea

Consider a finite state irreducible aperiodic Markov chain

M with state space S and (unique) stationary distribution \pi (\pi is a probability vector). Suppose that we come up with a probability distribution \mu on the set of maps f:S\to S with the property that for every fixed s\in S , its image f(s) is distributed according to the transition probability of M from state s . An example of such a probability distribution is the one where f(s) is independent from f(s') whenever s\ne s' , but it is often worthwhile to consider other distributions. Now let f _{j} for j\in Z be independent samples from \mu .

Suppose that

x is chosen randomly according to \pi and is independent from the sequence f _{j} . (We do not worry for now where this x is coming from.) Then f _{-1} (x) is also distributed according to \pi , because \pi is M -stationary and our assumption on the law of f . Define F _{j:=} f _{-1} \circ f _{-2} \circ … \circ f _{-j} . Then it follows by induction that F _{j(x)} is also distributed according to \pi for every j\in N . However, it may happen that for some n\in N the image of the map F _{n} is a single element of S .In other words, F _{n(x)=F} _{n(y)} for each y\in S . Therefore, we do not need to have access to x in order to compute F _{n(x)} . The algorithm then involves finding some n\in N such that F _{n(S)} is a singleton, and outputting the element of that singleton. The design of a good distribution \mu for which the task of finding such an n and computing F _{n} is not too costly is not always obvious, but has been accomplished successfully in several important instances.^[1]

The monotone case

There is a special class of Markov chains in which there are particularly good choicesfor

\mu and a tool for determining if |F _{n(S)|=1} . (Here | ⋅ | denotes cardinality.) Suppose that S is a partially ordered set with order \le , which has a unique minimal element s _{0} and a unique maximal element s _{1} ; that is, every s\in S satisfies s _{0\le} s\le s _{1} . Also, suppose that \mu may be chosen to be supported on the set of monotone maps f:S\to S . Then it is easy to see that |F _{n(S)|=1} if and only if F _{n(s} _{0)=F} _{n(s} _{1)} , since F _{n} is monotone. Thus, checking this becomes rather easy. The algorithm can proceed by choosing n: = n _{0} for some constant n _{0} , sampling the maps f _{-1} , ... ,f _{-n} , and outputting F _{n(s} _{0)} if F _{n(s} _{0)=F} _{n(s} _{1)} . If F _{n(s} _{0)\ne} F _{n(s} _{1)} the algorithm proceeds by doubling n and repeating as necessary until an output is obtained. (But the algorithm does not resample the maps f _{-j} which were already sampled; it uses the previously sampled maps when needed.)

References

• cs2 . Propp . James Gary . Wilson . David Bruce . Proceedings of the Seventh International Conference on Random Structures and Algorithms (Atlanta, GA, 1995) . 1611693 . 1996 . Exact sampling with coupled Markov chains and applications to statistical mechanics . 223–252.

Notes and References

1. Web site: Web Site for Perfectly Random Sampling with Markov Chains.