by Eli Chertkov

Coupling from the Past

Coupling from the past is an algorithm to generate perfect samples from a Markov chain (MC). It provides a measure of the mixing time M of the MC and in general scales as O(4MN), where N is the total number of states.

Presentation Summary

In these slides, I present:

Basic idea behind the CFTP algorithm.
Implementation of CFTP on a toy monotonic Markov chain.

Examples

simple_cftp.py: simplest CFTP implementation.
CFTP.zip: more advanced examples.

References

All Markov Chain

by Eli Chertkov · Coupling from the Past

Yubo "Paul" Yang 2019-10-19 ALGORITHM
markov chain