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 .

- 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
- 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).

- which is called
- 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.

- In other words, the Markov chains
are

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.

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

**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.

- If the number of elements in the state space
is large,