CFTP histories

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

References

All Markov Chain