Coupling from the past

From Wikipedia, the free encyclopedia

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.

[edit] The basic idea

Consider a finite state irreducible aperiodic Markov chain $M$ with state space $S$ and (unique) stationary distribution $π$ . Suppose that we come up with a probability distribution $μ$ 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\mathbb Z$ be independent samples from $μ$ .

Suppose that $x$ is chosen randomly according to $π$ and is independent from the sequence $f j$ . (We do now worry for now where this $x$ is comming from.) Then $f - 1 (x)$ is also distributed according to $π$ , because $π$ is $M$ -stationary and our assumption on the law of $f$ . Define

$F_j:= f_{-1}\circ f_{-2}\circ\cdots\circ f_{-j}.$

Then it follows by induction that $F j (x)$ is also distributed according to $π$ for every $j\in\mathbb N$ . Now here is the main point. It may happen that for some $n\in\mathbb 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 \mathbb N$ such that $F n (S)$ is a singleton, and outputing the element of that singleton. The design of a good distribution $μ$ 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^{[citation needed]}.

[edit] The monotone case

There is a special class of Markov chains in which there are particularly good choices for $μ$ and a tool for determining if $| F n (S) | = 1$ . (Here $|\cdot|$ 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 $μ$ 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},\dots,f_{-n}$ , and outputing $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.)

[edit] References

Propp, James Gary & Wilson, David Bruce (1996), Exact sampling with coupled Markov chains and applications to statistical mechanics, “Proceedings of the Seventh International Conference on Random Structures and Algorithms (Atlanta, GA, 1995)”, Random Structures & Algorithms 9 (1): 223–252, MR 1611693, ISSN 1042-9832
Propp, James & Wilson, David (1998), “Coupling from the past: a user's guide”, Microsurveys in discrete probability (Princeton, NJ, 1997), vol. 41, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Providence, R.I.: American Mathematical Society, pp. 181–192, MR 1630414