The arrival of Propp and Wilson's (1996, Random Structures and
Algorithms) coupling from the past (CFTP) algorithm caused a big stir
in the Markov chain Monte Carlo community, because it did the
seemingly impossible task of using a finite run of a Markov chain to
obtain samples from the steady-state distribution of the chain. At
around the same time Fill (1998, Annals of Applied Probability)
developed quite a different algorithm that accomplished the same thing
using rejection sampling.
In this talk (which is loosely based on Fill, Machida, Murdoch and
Rosenthal, 2000, Random Structures and Algorithms) I will summarize
both algorithms, and show how Wilson's (2000, Random Structures and
Algorithms) ``read-once'' variation on CFTP is in some sense also a
variation on Fill's algorithm.