Propp-Wilson-Algorithmus; Coupling-from-the-Past

• Zur Erinnerung
  • Bei der in Abschnitt 3.5.1 diskutierten Vorwärtskopplung ist der Anfangspunkt 0 der Simulation deterministisch, wogegen der Endpunkt, d.h. der Kopplungszeitpunkt $\tau$ zufällig ist.
  • Dabei stimmt die Zustandsverteilung der Markov-Kette ${\mathbf{X}}^{(i)}$ zum Kopplungszeitpunkt $\tau$ im allgemeinen nicht mit der stationären Grenzverteilung ${\boldsymbol{\pi}}$ überein.
• Deshalb betrachten wir nun ein anderes Kopplungsverfahren,
  • das in der Literatur Coupling-from-the-Past (CFTP) bzw. Rückwärtskopplung genannt wird und
  • das in der Mitte der 90-er Jahre von Propp und Wilson am Massachusetts Institute of Technology (MIT) entwickelt worden ist.
• Dabei gehen wir zwar auf ähnliche Weise wie in Abschnitt 3.5.1 vor, wählen jedoch jetzt den Anfangspunkt der Simulation zufällig, wogegen der Endpunkt deterministisch ist.
  • Mit anderen Worten: Wir ,,starten'' die Markov-Ketten ${\mathbf{X}}^{(1)},\ldots,{\mathbf{X}}^{(\ell)}$ nicht zum ,,Zeitpunkt'' 0,
  • sondern hinreichend weit in der ,,Vergangenheit'', so dass spätestens bis zum ,,Zeitpunkt'' 0 sämtliche Pfade miteinander verschmolzen sind.

Um diese Vorgehensweise mathematisch präzise formulieren zu können, führen wir die folgenden Bezeichnungen ein.

• Für jeden potentiellen ,,Startzeitpunkt'' $m\in\{-1,-2,\ldots\}$ und für jedes $i\in\{1,\ldots,\ell\}$ sei
  $${\mathbf{X}}^{(m,i)}=\bigl({\mathbf{X}}_m^{(m,i)},{\mathbf{X}}_{m+1}^{(m,i)},\ldots\Bigr)$$
  • eine homogene Markov-Kette mit dem endlichen Zustandsraum $E=\{{\mathbf{x}}_1,\ldots,{\mathbf{x}}_\ell\}$
  • mit dem (deterministischen) Anfangszustand ${\mathbf{X}}_m^{(m,i)}={\mathbf{x}}_i$ und mit der irreduziblen und aperiodischen Übergangsmatrix ${\mathbf{P}}=(p_{{\mathbf{x}}{\mathbf{x}}^\prime})$,
  • so dass ${\boldsymbol{\pi}}=(\pi_{\mathbf{x}},\,{\mathbf{x}}\in E)$ die ergodische (Grenz-) Verteilung der Markov-Kette ${\mathbf{X}}^{(m,i)}$ ist.
• Für jedes $k\in\{1,\ldots,\ell\}$ betrachten wir
  • eine Folge ${\mathbf{U}}^{(k)}=\bigl(U_{0}^{(k)},U_{-1}^{(k)},\ldots\bigr)$ von unabhängigen und $(0,1]$-gleichverteilten Zufallsvariablen,
  • wobei wir $U_{-n}^{(k)}$ (ähnlich wie in Abschnitt 3.5.1) Innovation im $(-n)$-ten Schritt bei Vorliegen des Zustandes ${\mathbf{x}}_k\in E$ nennen.
• Dabei betrachten wir erneut die beiden Fälle,
  • dass die Innovationen-Folgen ${\mathbf{U}}^{(1)},\ldots,{\mathbf{U}}^{(\ell)}$ entweder unabhängig sind oder
  • dass ${\mathbf{U}}^{(1)}=\ldots={\mathbf{U}}^{(\ell)}={\mathbf{U}}$ gilt.
• Die Markov-Kette ${\mathbf{X}}^{(m,i)}$ sei rekursiv durch eine gültige Update-Funktion $\varphi:E\times(0,1]\to E$ gegeben, d.h., es gelte

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

  
  

Definition

$\;$ Die Zufallsvariable $\zeta=\min\bigl\{-m\ge 1:\,{\mathbf{X}}_0^{(m,1)}=\ldots={\mathbf{X}}_0^{(m,\ell)}\bigr\}$ heißt CFTP-Kopplungszeit, wobei $\zeta=\infty$ gesetzt wird, falls es keine natürliche Zahl $-m$ gibt mit ${\mathbf{X}}_0^{(m,1)}=\ldots={\mathbf{X}}_0^{(m,\ell)}$.

Theorem 3.23   $\;$ Sei $P(\zeta<\infty)=1$. Für jedes $m\le-\zeta$ gilt dann

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

Außerdem gilt für beliebige $m\le-\zeta$ und $i,j\in\{1,\ldots,\ell\}$, dass

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

Beweis

 

• Unmittelbar aus der rekursiven Definitionsgleichung (90) der Markov-Ketten ${\mathbf{X}}^{(m,1)},\ldots,{\mathbf{X}}^{(m,\ell)}$ ergibt sich, dass ${\mathbf{X}}_0^{(m,1)}=\ldots={\mathbf{X}}_0^{(m,\ell)}$ und ${\mathbf{X}}_0^{(m,i)}={\mathbf{X}}_0^{(-\zeta,j)}$ für beliebige $m\le-\zeta$ und $i,j\in\{1,\ldots,\ell\}$.
• Weil $P(\zeta<\infty)=1$ vorausgesetzt wird, gilt außerdem für jedes $k\in\{1,\ldots,\ell\}$, dass
  

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

  
  
  wobei sich die vorletzte Gleichheit aus der Homogenität der Markov-Kette ${\mathbf{X}}^{(m,i)}$ ergibt.
  
  $\Box$

Beachte

 

• Wenn die Anzahl $\ell$ der Elemente des Zustandsraumes $E=\{{\mathbf{x}}_1,\ldots,{\mathbf{x}}_\ell\}$ groß ist,
  • dann kann die MCMC-Simulation von ${\boldsymbol{\pi}}$ auf der Grundlage des CFTP-Algorithmus von Propp und Wilson mit großem Rechenaufwand verbunden sein,
  • der zur Erzeugung sämtlicher ,,Pfade'' mit den Anfangszuständen ${\mathbf{x}}_1,\ldots,{\mathbf{x}}_\ell$ erforderlich ist.
• Dieser Aufwand lässt sich jedoch in manchen Fällen verringern. Beispiele hierfür werden in den folgenden Abschnitten 3.5.3 und 3.5.4 diskutiert,
  • wobei der Zustandsraum $E=\{{\mathbf{x}}_1,\ldots,{\mathbf{x}}_\ell\}$ und die Update-Funktion $\varphi:E\times(0,1]\to E$ gewisse Monotonie-Eigenschaften besitzen
  • und dann lediglich eine Folge ${\mathbf{U}}=\bigl(U_0,U_{-1},\ldots\bigr)$ von unabhängigen und $(0,1]$-gleichverteilten Innovationen betrachtet wird
  • sowie nur zwei verschiedene Pfade generiert werden müssen.