Coupling from the past

Consider a finite state irreducible aperiodic Markov chain $M$ with state space $S$ and (unique) stationary distribution $\backslash pi$ ($\backslash pi$ is a probability vector). Suppose that we come up with a probability distribution $\backslash mu$ on the set of maps $f:S\backslash to\; S$ with the property that for every fixed $s\backslash 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\text{'})$ whenever $s\backslash ne\; s\text{'}$, but it is often worthwhile to consider other distributions. Now let $f\_j$ for $j\backslash in\backslash mathbb\; Z$ be independent samples from $\backslash mu$.

Suppose that $x$ is chosen randomly according to $\backslash 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 $\backslash pi$, because $\backslash pi$ is $M$-stationary and our assumption on the law of $f$. Define

:$F\_j:=\; f\_\{-1\}\backslash circ\; f\_\{-2\}\backslash circ\backslash cdots\backslash circ\; f\_\{-j\}.$

Then it follows by induction that $F\_j(x)$ is also distributed according to $\backslash pi$ for every $j\backslash in\backslash mathbb\{N\}$. However, it may happen that for some $n\backslash in\backslash 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\backslash 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\backslash in\; \backslash mathbb\; N$ such that $F\_n(S)$ is a singleton, and outputting the element of that singleton. The design of a good distribution $\backslash 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.{{Cite web|url=http://www.dbwilson.com/exact/|title=Web Site for Perfectly Random Sampling with Markov Chains}}

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

for $\backslash mu$ and a tool for determining if $|F\_n(S)|=1$. (Here $|\backslash cdot|$ denotes cardinality.) Suppose that $S$ is a partially ordered set with order $\backslash le$, which has a unique minimal element $s\_0$ and a unique maximal element $s\_1$; that is, every $s\backslash in\; S$ satisfies $s\_0\backslash le\; s\backslash le\; s\_1$. Also, suppose that $\backslash mu$ may be chosen to be supported on the set of monotone maps $f:S\backslash 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\},\backslash dots,f\_\{-n\}$, and outputting $F\_n(s\_0)$ if $F\_n(s\_0)=F\_n(s\_1)$. If $F\_n(s\_0)\backslash 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.)

{{Reflist}}

• {{cite conference |mode=cs2 |last1=Propp |first1=James Gary |last2=Wilson |first2=David Bruce |book-title=Proceedings of the Seventh International Conference on Random Structures and Algorithms (Atlanta, GA, 1995) |mr=1611693 |year=1996 |chapter=Exact sampling with coupled Markov chains and applications to statistical mechanics |pages=223–252}}
• {{Citation | last1=Propp | first1=James | last2=Wilson | first2=David | s2cid=2781385 | title=Microsurveys in discrete probability (Princeton, NJ, 1997) | publisher=American Mathematical Society | location=Providence, R.I. | series=DIMACS Ser. Discrete Math. Theoret. Comput. Sci. | mr=1630414 | year=1998 | volume=41 | chapter=Coupling from the past: a user's guide | pages=181–192 | doi=10.1090/dimacs/041/09 | isbn=9780821808276 }}

Category:Monte Carlo methods

Category:Markov chain Monte Carlo