    Next: Monotone Coupling Algorithms Up: Coupling Algorithms; Perfect MCMC Previous: Coupling to the Future;   Contents

### Propp-Wilson Algorithm; Coupling from the Past

• Recall that
• the procedure of coupling to the future discussed in Section 3.5.1 starts at a deterministic time 0 whereas the final state, i.e. the coupling time of the simulation is random.
• Moreover, the state distribution of the Markov chain at the coupling time is in general not equal to the stationary limit distribution .
• Therefore, we will now consider a different coupling method,
• which is called Coupling from the Past (CFTP).
• It was developed in the mid 90s by Propp and Wilson at the Massachusetts Institute of Technology (MIT).
• The procedure is similar to coupling to the future (see Section 3.5.1) but now the initial ,,time'' of the simulation will be chosen randomly whereas the final ,,time'' is deterministic.
• In other words, the Markov chains are not started at ,,time'' 0,
• but sufficiently far away in the ,,past'' such that by time 0 at the latest all paths will have merged.

For the precise mathematical modeling of this procedure we need the following notation.

• For each potential ,,initial time'' and for all let • be a homogenous Markov chain with finite state space ,
• with the (deterministic) initial state and with the irreducible and aperiodic transition matrix ,
• such that is the ergodic limit distribution of .
• For every we consider
• a sequence of independent and -uniformly distributed random variables.
• Like in Section 3.5.1 we call an innovation in step if the current state is .
• We consider two cases:
• The innovation sequences are either independent
• or .
• Let the Markov chain be defined recursively via the update function , i.e.  (90)

Definition The random variable is called CFTP coupling time where we define if there is no integer such that .

Theorem 3.23 Let . Then, for all , Moreover, for arbitrary and , Proof

• Directly by the recursive definition (90) of the Markov chains , we get that and for arbitrary and .
• As by hypothesis , we obtain for arbitrary that           where the last but one equality is a consequence of the homogeneity of the Markov chain . Remarks

• If the number of elements in the state space is large,
• the MCMC simulation of based on the CFTP algorithm by Propp and Wilson can be computationally inefficient
• as for every initial state a complete path needs to be generated.
• However, in some cases the computational complexity can be reduced. Examples will be discussed in Sections 3.5.3 and 3.5.4.
• In these special situations the state space and the update function possess certain monotonicity properties.
• As a consequence it suffices to consider a single sequence of independent and -uniformly distributed innovations.
• Moreover, only two different paths need to be generated.    Next: Monotone Coupling Algorithms Up: Coupling Algorithms; Perfect MCMC Previous: Coupling to the Future;   Contents
Ursa Pantle 2006-07-20