Coupling, renewal and perfect simulation of chains of infinite order

Roberto Fernández, Pablo A. Ferrari, Antonio Galves
September 2001

Notes for a minicourse given at the V Brazilian School of Probability, Ubatuba, July 30--August 4, 2001

pdf file, gzipped postscript file


This 95-page booklet presents an explicit regenerative construction of chains with infinite memory under the Harris regime. The construction yields existence and uniqueness results, as well as a perfect simulation scheme. In the last chapter, coupling techniques are exploited to estimate degreees of proximity of Markovian approximations.

Partial list of topics:

Transition probabilities
Simulation algorithms and transition probabilities
Coupling and coupling algorithms
Types of chains of infinite order
Countable mixtures of Markov chains (CMMC)
Variable-length Markov chains (VLMC)
Sparse VLMC
Hidden Markov models (HMM)
Binary autoregressions
Random systems with complete connections
A regeneration scheme for CMMC
Existence, uniqueness and loss of memory of CMMC
Mixing properties and perfect simulations for CMMC
Every chain of infinite order is a CMMC and a VLMC
Markov approximations for chains of infinite order

pdf file, gzipped postscript file