Read-Once-Modifikation des CFTP-Algorithmus

• Eine Problematik des ,,monotonen'' CFTP-Algorithmus, der in den Abschnitten 3.5.3 und 3.5.4 diskutiert worden ist, besteht darin, dass
  • sämtliche Innovationen $U_0,U_{-1},\ldots,U_{-\zeta}$ gespeichert werden müssen, wobei $\zeta$ die in (95) definierte ,,monotone'' CFTP-Kopplungszeit ist mit
    $$\zeta=\min\bigl\{-m\ge 1:\,{\mathbf{X}}_0^{(m,\min)}={\mathbf{X}}_0^{(m,\max)}\bigr\}\,.$$

  • Deshalb schlug David Wilson im Jahre 2000 die folgende Modifikation des CFTP-Algorithmus mit dem Ziel vor, den erforderlichen Speicherbedarf weiter zu verringern.
• Die Hauptidee der Modifikation besteht darin, die in den Abschnitten 3.5.2 - 3.5.4 betrachtete Rückwärtskopplung
  • mit Hilfe einer Folge von unabhängigen und identisch verteilten ,,Vorwärts-Simulationsblöcken'' darzustellen, wobei
  • die (potentiellen) ,,Startzeitpunkte'' $m\in\{-1,-2,\ldots\}$ der Markov-Kette ${\mathbf{X}}^{(m,i)}=\bigl({\mathbf{X}}_m^{(m,i)},{\mathbf{X}}_{m+1}^{(m,i)},\ldots\bigr)$ auch zufällig gewählt werden können.
• Dabei seien die Innovationen-Folgen ${\mathbf{U}}^{(1)},\ldots,{\mathbf{U}}^{(\ell)}$ mit Wahrscheinlichkeit $1$ identisch,
  • d.h., es wird lediglich eine Folge ${\mathbf{U}}=\bigl(\ldots,U_{-1},U_0,U_1,\ldots\bigr)$ von unabhängigen und gleichverteilten Zufallsvariablen betrachtet und ${\mathbf{U}}^{(1)}=\ldots={\mathbf{U}}^{(\ell)}={\mathbf{U}}$ gesetzt.
  • Außerdem wird vorausgesetzt, dass die in (87) und (90) definierten Markov-Ketten ${\mathbf{X}}^{(1)},\ldots,{\mathbf{X}}^{(\ell)}$ bzw. ${\mathbf{X}}^{(m,1)},\ldots,{\mathbf{X}}^{(m,\ell)}$ so beschaffen sind,
  • dass die (Vorwärts- bzw. Rückwärts-) Kopplungszeiten
    $$\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\}$$
    jeweils mit Wahrscheinlichkeit $1$ endlich sind.
• Wir betrachten nun Vorwärts-Simulationsblöcke mit der (zunächst deterministischen) Länge $T$ für ein $T \ge 1$:
  • Für beliebige $k\ge 0$ bzw. $i=1,...,\ell$ sei ${\mathbf{X}}_{kT}^{(kT,i)} = {\mathbf{x}}_i$ und
    $${\mathbf{X}}_{n}^{(kT,i)} = \varphi({\mathbf{X}}_{n-1}^{(kT,i)},U_n)\,,\qquad\forall\, n=kT+1,kT+2,...\,.$$

  • Außerdem betrachten wir für jedes $k\ge 0$ das Ereignis
    $$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\}\,,$$
    wobei die Blocklänge $T$ so gewählt sei, dass

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

    
    

• Bei Start mit $k=0$ ist die Read-Once-Modifikation des CFTP-Algorithmus dann gegeben durch:
  1. Simuliere ${\mathbf{X}}_{n}^{(kT,i)}$ über $\varphi$ und ${\mathbf{U}}$ für $n=kT+1,...,(k+1)T$.
  2. Setze $m=k$ und $k=k+1$. Falls das Ereignis $C_{mT}$ eingetreten ist, fahre fort in Schritt 3, anderenfalls kehre zu Schritt 1 zurück.
  3. Wiederhole die Schritte 1 und 2 bis das Ereignis $C_{m^{\prime}T}$ für ein $m^{\prime} > m$ eintritt und gib den Wert von ${\mathbf{X}}_{m^{\prime}T}^{(mT,i)}$ für ein beliebiges $i \in \{1,...,l\}$ als Realisierung gemäß ${\boldsymbol{\pi}}$ aus.

Beispiel

 

• Für $\ell=3$ Zustände betrachten wir die (irreduzible und aperiodische) Übergangsmatrix
  $${\mathbf{P}}= \left(\begin{array}{ccc} 1/2 & 0 & 1/2\\ 1/3 & 1/3 & 1/3\\ 0 & 1 & 0 \end{array}\right)$$

• Für die Blocklänge $T=2$ und für die $(0,1]$-gleichverteilten Pseudozufallszahlen
  $${\mathbf{u}}= (0.01, 0.60, 0.82, 0.47, 0.36, 0.59, 0.34, 0.89, ...)$$
  ergibt sich dabei der folgende Simulationslauf:

  
  

  Abbildung 7: Read-Once-Algorithmus

  

Beachte

 

• Weil die Simulationsblöcke und damit auch die Ereignisse $C_{T},\,C_{2T},\,\ldots$ unabhängig sind und weil $P(C_T)=P(C_{2T})=\ldots$ gilt,
  • liefern die ersten $m^\prime$ Vorwärts-Simulationsblöcke des oben beschriebenen Algorithmus, wenn sie in umgekehrter Reihenfolge betrachtet werden, insbesondere das in Abschnitt 3.5.2 diskutierte Coupling-from-the-Past.
  • Hieraus ergibt sich, dass ${\mathbf{X}}_{m^{\prime}T}^{(mT,i)}\sim{\boldsymbol{\pi}}$ für jedes $i \in \{1,...,l\}$.
  • Der letzte, d.h. der $(m^\prime+1)$-te Vorwärts-Simulationsblock dient lediglich zur Definition einer Stoppregel.

  
  

• Die Read-Once-Modifikation des CFTP-Algorithmus terminiert mit Wahrscheinlichkeit $1$,
  • wenn die Bedingung (105) erfüllt ist, d.h., wenn $P(C_T)>0$.
  • Für isotone Update-Funktionen gilt dies, falls $T\ge n_0$, wobei $n_0\ge 1$ eine natürliche Zahl mit
    $$\min\limits_{{\mathbf{x}},{\mathbf{x}}^\prime\in E} p_{{\mathbf{x}}{\mathbf{x}}^\prime}^{(n_0)}=c>0\,,$$
    vgl. den Beweis von Theorem 3.24.

  
  

• Wenn $T$ eine Zufallsvariable ist,
  • die so wie die Vorwärtskopplungszeit $\tau$ verteilt ist und unabhängig von der Innovationen-Folge ${\mathbf{U}}=\bigl(U_0,U_{-1},\ldots\bigr)$ ist,
  • dann ergibt sich aus den folgenden elementaren, jedoch nützlichen Eigenschaften der Kopplungszeiten $\tau$ und $\zeta$, dass $P(C_T)\ge 1/2$.

Theorem 3.25   $\;$ Es gilt $\tau\stackrel{{\rm d}}{=}\zeta$. Wenn die Kopplungszeiten $\tau$ und $\zeta$ darüber hinaus unabhängig sind, dann gilt

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

Beweis

 

• Aus der Homogenität der Markov-Ketten ${\mathbf{X}}^{(1)},\ldots,{\mathbf{X}}^{(\ell)}$ bzw. ${\mathbf{X}}^{(m,1)},\ldots,{\mathbf{X}}^{(m,\ell)}$ ergibt sich für jede natürliche Zahl $k\ge 1$, dass
  

  $$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)\,.$$

  
  

• Die Kopplungszeiten $\tau$ und $\zeta$ seien nun unabhängig und mit Wahrscheinlichkeit $1$ endlich.
  • Hieraus ergibt sich, dass
    

    $$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)\,,$$

    
    

  • wobei sich die vorletzte Gleichheit aus der identischen Verteiltheit $\tau\stackrel{{\rm d}}{=}\zeta$ von $\tau$ und $\zeta$ ergibt, die im ersten Teil des Beweises gezeigt wurde.
• Somit gilt
  

  $$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$