Monotone CFTP: two trajectories certify coalescence

Let $V$ be a finite state space carrying a partial order with a smallest element $\hat 0$ and a largest element $\hat 1$, and let $g_1,\dots,g_t:V\to V$ be monotone maps: $u\le v$ implies $g_i(u)\le g_i(v)$. Write $\Phi=g_1\circ g_2\circ\cdots\circ g_t$ for their composition (as in coupling from the past, where the $g_i$ are the update maps drawn at times $-1,\dots,-t$ and the deepest map applies first).

The theorem (§22.2 of Levin–Peres–Wilmer, the principle behind monotone CFTP) asserts: if the composition merely identifies the two extremes,

then $\Phi$ is constant on all of $V$: $\Phi(x)=\Phi(y)$ for every pair of states.

A composition of monotone maps is monotone, so $\Phi(\hat 0)\le\Phi(x)\le\Phi(\hat 1)$ for every $x$; when the two ends meet, everything between is squeezed to the same value. This is what makes CFTP practical on exponentially large ordered state spaces: instead of tracking all $|V|$ trajectories, the algorithm runs just two — from the top state and the bottom state — and their meeting certifies global coalescence. For the Ising model of Mission IX, whose heat-bath updates are monotone for the coordinatewise spin order, this reduces $2^n$ trajectories to $2$.