Read-Once Modification of the CFTP Algorithm

• A problem of the ,,monotone'' CFTP algorithm discussed in Sections 3.5.3 and 3.5.4 is
  • the necessity to save all innovations $U_0,U_{-1},\ldots,U_{-\zeta}$ where $\zeta$ denotes the coupling time defined in (95), i.e.
    $$\zeta=\min\bigl\{-m\ge 1:\,{\mathbf{X}}_0^{(m,\min)}={\mathbf{X}}_0^{(m,\max)}\bigr\}\,.$$

  • Therefore, in the year 2000, David Wilson suggested the following modifications of the CFTP algorithm aiming at a reduction of the necessary memory allocation.
• The main idea of the modification is to realize coupling to the past (see Sections 3.5.2 - 3.5.4)
  • based on a sequence of independent and identically distributed blocks of ,,forward simulation'', where
  • the (potential) ,,initial times'' $m\in\{-1,-2,\ldots\}$ of the Markov chain ${\mathbf{X}}^{(m,i)}=\bigl({\mathbf{X}}_m^{(m,i)},{\mathbf{X}}_{m+1}^{(m,i)},\ldots\bigr)$ can be picked at random.
• The innovation sequences ${\mathbf{U}}^{(1)},\ldots,{\mathbf{U}}^{(\ell)}$ are chosen identical with probability $1$,
  • i.e., we merely consider a single sequence ${\mathbf{U}}=\bigl(\ldots,U_{-1},U_0,U_1,\ldots\bigr)$ of independent and uniformly distributed random variables and define ${\mathbf{U}}^{(1)}=\ldots={\mathbf{U}}^{(\ell)}={\mathbf{U}}$.
  • Furthermore, we assume that the Markov chains ${\mathbf{X}}^{(1)},\ldots,{\mathbf{X}}^{(\ell)}$ and ${\mathbf{X}}^{(m,1)},\ldots,{\mathbf{X}}^{(m,\ell)}$ defined by (87) and (90) have finite forward and backward coupling times
    $$\tau=\min\bigl\{n\ge 1:\,{\mathbf{X}}_n^{(1)}=\ldots={\mathbf{X}}_n^{(\ell)}\bigr\}$$   bzw.$$\quad \zeta=\min\bigl\{-m\ge 1:\,{\mathbf{X}}_0^{(m,1)}=\ldots={\mathbf{X}}_0^{(m,\ell)}\bigr\}$$
    with probability $1$.
• Now we consider blocks of forward simulation of (at first deterministic) length $T$ for some $T \ge 1$.
  • For arbitrary $k\ge 0$ and $i=1,...,\ell$, let ${\mathbf{X}}_{kT}^{(kT,i)} = {\mathbf{x}}_i$ and
    $${\mathbf{X}}_{n}^{(kT,i)} = \varphi({\mathbf{X}}_{n-1}^{(kT,i)},U_n)\,,\qquad\forall\, n=kT+1,kT+2,...\,.$$

  • Furthermore, for each $k\ge 0$ we consider the event
    $$C_{kT} = \left\{{\mathbf{X}}_{(k+1)T}^{(kT,i)} = {\mathbf{X}}_{(k+1)T}^{(kT,j)}\,,\qquad\forall\, i\neq j \in \{1,...,l\}\right\}\,,$$
    where the length $T$ of the blocks is chosen such that

    $$0<P(C_T)\qquad \Bigl(=P(C_{kT})\,,\quad\forall\, k\ge 0\Bigr)\,.$$ (105)

    
    

• Starting at $k=0$ the read-once modification of the CFTP algorithm is given as follows.
  1. Simulate ${\mathbf{X}}_{n}^{(kT,i)}$ via $\varphi$ and ${\mathbf{U}}$ for $n=kT+1,...,(k+1)T$.
  2. Set $m=k$ and $k=k+1$. If the event $C_{mT}$ has occurred proceed with step 3, otherwise return to step 1.
  3. Repeat steps 1 and 2 until the event $C_{m^{\prime}T}$ occurs for some $m^{\prime} > m$ and return the value of ${\mathbf{X}}_{m^{\prime}T}^{(mT,i)}$ for an arbitrary $i \in \{1,...,l\}$ as a realization of ${\boldsymbol{\pi}}$.

Example

 

• For $\ell=3$ states we consider the irreducible and aperiodic transition matrix
  $${\mathbf{P}}= \left(\begin{array}{ccc} 1/2 & 0 & 1/2\\ 1/3 & 1/3 & 1/3\\ 0 & 1 & 0 \end{array}\right)\,.$$

• For block length $T=2$ and the $(0,1]$-uniformly distributes pseudo-random numbers
  $${\mathbf{u}}= (0.01, 0.60, 0.82, 0.47, 0.36, 0.59, 0.34, 0.89, ...)$$
  we obtain the simulation run shown in Fig. 9.

  
  

  Figure 9: Read once algorithm

  [width=11cm, angle=1800]bild8.eps

Remarks

 

• As the simulation blocks and hence the events $C_{T},\,C_{2T},\,\ldots$ are independent and as $P(C_T)=P(C_{2T})=\ldots$,
  • the first $m^\prime$ blocks of forward simulation of the algorithm described above in particular yield the coupling from the past discussed in Section 3.5.2 if they are considered in reversed order.

  • Therefore, ${\mathbf{X}}_{m^{\prime}T}^{(mT,i)}\sim{\boldsymbol{\pi}}$ for all $i \in \{1,...,l\}$.
  • The last, i.e. the $(m^\prime+1)$st block of forward simulation serves only to define a stopping rule.

  
  

• The read-once modification of the CFTP algorithm terminates with probability $1$
  • if condition (105) is satisfied, i.e. if $P(C_T)>0$.
  • For monotonously nondecreasing update functions this holds if $T\ge n_0$ where $n_0\ge 1$ is a natural number such that
    $$\min\limits_{{\mathbf{x}},{\mathbf{x}}^\prime\in E} p_{{\mathbf{x}}{\mathbf{x}}^\prime}^{(n_0)}=c>0\,,$$
    see the proof of Theorem 3.24.

  
  

• If $T$ is a random variable
  • having the same distribution as the forward coupling time $\tau$ and which is independent of the innovation sequence ${\mathbf{U}}=\bigl(U_0,U_{-1},\ldots\bigr)$,
  • then by the following elementary but useful properties of the coupling times $\tau$ and $\zeta$ we obtain $P(C_T)\ge 1/2$.

Theorem 3.25   $\;$ The random variables $\tau$ and $\zeta$ have the same distribution, i.e. $\tau\stackrel{{\rm d}}{=}\zeta$. Moreover, if the coupling times $\tau$ and $\zeta$ are independent and almost surely finite, then

$$P(\zeta\le\tau)\;\ge\; \frac{1}{2}\;.$$ (106)

Proof

 

• By the homogeneity of the Markov chains ${\mathbf{X}}^{(1)},\ldots,{\mathbf{X}}^{(\ell)}$ and ${\mathbf{X}}^{(m,1)},\ldots,{\mathbf{X}}^{(m,\ell)}$, for any natural number $k\ge 1$ we have
  

  $$P(\tau=k) = P\Bigl(\min\bigl\{n\ge 1:\,{\mathbf{X}}_n^{(1)}=\ldots={\mathbf{X}}_n^{(\ell)}\bigr\}=k\Bigr)$$

  $$= P\Bigl(\min\bigl\{-m\ge 1:\,{\mathbf{X}}_0^{(m,1)}=\ldots={\mathbf{X}}_0^{(m,\ell)}\bigr\}=k\Bigr)$$

  $$= P(\zeta=k)\,.$$

  
  

• Let now the coupling times $\tau$ and $\zeta$ be independent and finite with probability $1$.
  • This implies
    

    $$P(\zeta\le\tau) = \sum\limits_{k=1}^\infty P(\zeta\le\tau\mid\tau=k)P(\tau=k) = \sum\limits_{k=1}^\infty P(\zeta\le k\mid\tau=k)P(\tau=k)$$

    $$= \sum\limits_{k=1}^\infty P(\zeta\le k)P(\tau=k) = \sum\limits_{k=1}^\infty P(\tau\le k)P(\zeta=k)$$

    $$\vdots$$

    $$= P(\zeta\ge\tau)\,,$$

    
    

  • where the last equality follows from $\tau\stackrel{{\rm d}}{=}\zeta$ which has been shown in the first part of the proof.
• Thus,
  

  $$2\,P(\zeta\le\tau) = P(\zeta\le\tau)+P(\zeta\ge\tau)$$

  $$= 1- P(\zeta>\tau)+1-P(\zeta<\tau)$$

  $$= 2- P(\zeta\not=\tau)$$

  $$\ge 2-1 = 1\,.$$

  
  
  
   
    $\Box$