chapter  3
18 Pages

Coupling from the Past

Coupling from the past (CFTP) allowed the creation of perfect simulation algorithms for problems where only Markov chain methods existed before. The easiest way to use this approach is to take advantage of monotonicity in the update function for a Markov chain. However, even for nonmonotonic problems, the use of bounding chains can combine with CFTP to obtain perfect samples. Basic CFTP does have drawbacks, though, the two biggest being noninterruptibility and the fact that the random choices made by the algorithm must be used twice.