Coupling from the past

Summary

Coupling from the past is an algorithm due to Propp and Wilson. It produces an exact sample from the stationary distribution of an ergodic finite Markov chain. It runs copies of the chain from all states, starting further and further in the past with the same randomness. It stops when all copies agree at time $0$. Unlike ordinary Markov chain Monte Carlo, its output has exactly the stationary law, with no bias from stopping too early.