Coalescence is almost sure

Let $P$ be a Markov chain on a finite state space $V$, and let $\nu$ be a random mapping representation of $P$: a probability distribution on update functions $f:V\to V$ with $\nu\{f:f(x)=y\}=P(x,y)$ for all $x,y$. Coupling from the past composes i.i.d. maps drawn from $\nu$ at times $-1,-2,\dots$ forward to time zero, $F^0_{-t}=f_{-1}\circ\cdots\circ f_{-t}$, and the composition has coalesced when it is a constant map — all starting states have been funneled to one common value.

The theorem (§22.3 of Levin–Peres–Wilmer) asserts: if some finite block of updates collapses the state space with positive probability — there is a $t_0$ and a tuple of maps $(g_1,\dots,g_{t_0})$, each of positive $\nu$-probability, whose composition is constant — then coalescence is almost sure:

The proof is a geometric-trials argument: the past divides into disjoint blocks of length $t_0$, each an independent chance of at least $p=\prod_i\nu(g_i)>0$ to collapse everything, and one collapsed block anywhere inside the composition makes the whole composition constant. This is the standing hypothesis of the correctness theorem — and the reason CFTP terminates in practice: for an irreducible aperiodic chain a collapsing block always exists, so the algorithm halts with probability one.