Coupling from the past

Remarks

If $\tau = \min\set{t : F_{-t} \text{ is constant}}$ is finite almost surely, the output has law exactly $\pi$. Indeed, $F_{-t} = F_{-\tau} \circ (\phi_{-\tau-1} \circ \cdots \circ \phi_{-t})$ has the same constant value for all $t \ge \tau$, while $F_{-t}(x)$ has law $P^t(x, \cdot)$, which tends to $\pi$. Example: take a chain that jumps to a fresh sample of $\pi$ at each step, with an update $\phi(x, u)$ that does not depend on $x$. Then $F_{-1}$ is constant, and the output $\phi(x, U_{-1})$ has law $\pi$. Non-example: running the coupled copies forward from time $0$ and outputting their value at the first meeting time is biased. Take $S = \set{0, 1}$, $\phi(0, u) = 0$ for $u < 1/2$, $\phi(0, u) = 1$ otherwise, and $\phi(1, u) = 0$. Then the forward copies always meet at $0$, while $\pi = (2/3, 1/3)$. If $S$ has a partial order with a top and a bottom element and $\phi(\cdot, u)$ is monotone, it suffices to follow the top and the bottom states.