Every chain has a random mapping representation

Let $P$ be a Markov chain on a finite state space $V$ (nonnegative entries, rows summing to one). A random mapping representation of $P$ is a probability distribution $\nu$ on update functions $f:V\to V$ that reproduces the transition probabilities in one step:

Drawing $f\sim\nu$ and applying it to the current state — whatever that state is — performs one step of the chain from every state simultaneously.

The theorem (Proposition 1.5 of Levin–Peres–Wilmer, used in Chapter 22) asserts: every finite Markov chain has a random mapping representation.

The construction slices a uniform random variable: partition $[0,1]$ into intervals of lengths $P(x,\cdot)$ for each $x$, and let the update map send each $x$ to the state whose interval contains the draw. Representations are far from unique, and the choice matters enormously in practice — monotone representations are what make monotone CFTP work — but existence is what the correctness theorem of this mission consumes: it guarantees that coupling from the past applies to any finite chain.