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 $\tau$ of the simulation is random.
  • Moreover, the state distribution of the Markov chain ${\mathbf{X}}^{(i)}$ at the coupling time $\tau$ is in general not equal to the stationary limit distribution ${\boldsymbol{\pi}}$.
• 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 ${\mathbf{X}}^{(1)},\ldots,{\mathbf{X}}^{(\ell)}$ 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'' $m\in\{-1,-2,\ldots\}$ and for all $i\in\{1,\ldots,\ell\}$ let
  $${\mathbf{X}}^{(m,i)}=\bigl({\mathbf{X}}_m^{(m,i)},{\mathbf{X}}_{m+1}^{(m,i)},\ldots\Bigr)$$
  • be a homogenous Markov chain with finite state space $E=\{{\mathbf{x}}_1,\ldots,{\mathbf{x}}_\ell\}$,
  • with the (deterministic) initial state ${\mathbf{X}}_m^{(m,i)}={\mathbf{x}}_i$ and with the irreducible and aperiodic transition matrix ${\mathbf{P}}=(p_{{\mathbf{x}}{\mathbf{x}}^\prime})$,
  • such that ${\boldsymbol{\pi}}=(\pi_{\mathbf{x}},\,{\mathbf{x}}\in E)$ is the ergodic limit distribution of ${\mathbf{X}}^{(m,i)}$.
• For every $k\in\{1,\ldots,\ell\}$ we consider
  • a sequence ${\mathbf{U}}^{(k)}=\bigl(U_{0}^{(k)},U_{-1}^{(k)},\ldots\bigr)$ of independent and $(0,1]$-uniformly distributed random variables.
  • Like in Section 3.5.1 we call $U_{-n}^{(k)}$ an innovation in step $-n$ if the current state is ${\mathbf{x}}_k\in E$.
• We consider two cases:
  • The innovation sequences ${\mathbf{U}}^{(1)},\ldots,{\mathbf{U}}^{(\ell)}$ are either independent
  • or ${\mathbf{U}}^{(1)}=\ldots={\mathbf{U}}^{(\ell)}={\mathbf{U}}$.
• Let the Markov chain ${\mathbf{X}}^{(m,i)}$ be defined recursively via the update function $\varphi:E\times(0,1]\to E$, i.e.

  $${\mathbf{X}}_n^{(m,i)}=\varphi\bigl({\mathbf{x}}_k,U^{(k)}_n\bigr) \mbox{if $X^{(m,i)}_{n-1}={\mathbf{x}}_k$.}$$ (90)

  
  

Definition

$\;$ The random variable $\zeta=\min\bigl\{-m\ge 1:\,{\mathbf{X}}_0^{(m,1)}=\ldots={\mathbf{X}}_0^{(m,\ell)}\bigr\}$ is called CFTP coupling time where we define $\zeta=\infty$ if there is no integer $-m$ such that ${\mathbf{X}}_0^{(m,1)}=\ldots={\mathbf{X}}_0^{(m,\ell)}$.

Theorem 3.23   $\;$ Let $P(\zeta<\infty)=1$. Then, for all $m\le-\zeta$,

$${\mathbf{X}}_0^{(m,1)}=\ldots={\mathbf{X}}_0^{(m,\ell)}\,.$$

Moreover, for arbitrary $m\le-\zeta$ and $i,j\in\{1,\ldots,\ell\}$,

$${\mathbf{X}}_0^{(m,i)}={\mathbf{X}}_0^{(-\zeta,j)}\sim{\boldsymbol{\pi}}\,.$$

Proof

 

• Directly by the recursive definition (90) of the Markov chains ${\mathbf{X}}^{(m,1)},\ldots,{\mathbf{X}}^{(m,\ell)}$, we get that ${\mathbf{X}}_0^{(m,1)}=\ldots={\mathbf{X}}_0^{(m,\ell)}$ and ${\mathbf{X}}_0^{(m,i)}={\mathbf{X}}_0^{(-\zeta,j)}$ for arbitrary $m\le-\zeta$ and $i,j\in\{1,\ldots,\ell\}$.
• As by hypothesis $P(\zeta<\infty)=1$, we obtain for arbitrary $k\in\{1,\ldots,\ell\}$ that
  

  $$P\Bigl({\mathbf{X}}_0^{(-\zeta,i)}={\mathbf{x}}_k\Bigr) = \lim\limits_{m\to-\infty} P\Bigl({\mathbf{X}}_0^{(-\zeta,i)}={\mathbf{x}}_k,\,\zeta\le -m\Bigr)$$

  $$= \lim\limits_{m\to-\infty} P\Bigl({\mathbf{X}}_0^{(m,i)}={\mathbf{x}}_k,\,\zeta\le -m\Bigr)$$

  $$= \lim\limits_{m\to-\infty} P\Bigl({\mathbf{X}}_0^{(m,i)}={\mathbf{... ...to-\infty} P\Bigl({\mathbf{X}}_0^{(m,i)}={\mathbf{x}}_k,\,\zeta> -m\Bigr)}_{=0}$$

  $$= \lim\limits_{m\to-\infty} P\Bigl({\mathbf{X}}_0^{(m,i)}={\mathbf{x}}_k\Bigr)$$

  $$= \lim\limits_{m\to-\infty} P\Bigl({\mathbf{X}}_{-m}^{(0,i)}={\mathbf{x}}_k\Bigr)={\boldsymbol{\pi}}_{{\mathbf{x}}_k}\,,$$

  
  
  where the last but one equality is a consequence of the homogeneity of the Markov chain ${\mathbf{X}}^{(m,i)}$.
  
  $\Box$

Remarks

 

• If the number $\ell$ of elements in the state space $E=\{{\mathbf{x}}_1,\ldots,{\mathbf{x}}_\ell\}$ is large,
  • the MCMC simulation of ${\boldsymbol{\pi}}$ based on the CFTP algorithm by Propp and Wilson can be computationally inefficient
  • as for every initial state ${\mathbf{x}}_1,\ldots,{\mathbf{x}}_\ell$ 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 $E=\{{\mathbf{x}}_1,\ldots,{\mathbf{x}}_\ell\}$ and the update function $\varphi:E\times(0,1]\to E$ possess certain monotonicity properties.
  • As a consequence it suffices to consider a single sequence ${\mathbf{U}}=\bigl(U_0,U_{-1},\ldots\bigr)$ of independent and $(0,1]$-uniformly distributed innovations.
  • Moreover, only two different paths need to be generated.