Monotone Kopplungsalgorithmen

• Wir setzen nun zusätzlich voraus, dass auf dem Zustandsraum $E=\{{\mathbf{x}}_1,\ldots,{\mathbf{x}}_\ell\}$ eine Halbordnung $\preceq$ definiert ist mit einem Minimalelement ${\,{\bf0}}\in E$ und einem Maximalelement ${\,{\bf 1}}\in E$, d.h., es gelte

  (a)

  ${\mathbf{x}}\preceq{\mathbf{x}}\,,\qquad\forall\,{\mathbf{x}}\in E\,,$

  (b)

  aus ${\mathbf{x}}\preceq{\mathbf{y}}$ und ${\mathbf{y}}\preceq{\mathbf{z}}$ folgt ${\mathbf{x}}\preceq{\mathbf{z}}\,,\qquad\forall\,{\mathbf{x}},{\mathbf{y}},{\mathbf{z}}\in E\,,$

  (c)

  aus ${\mathbf{x}}\preceq{\mathbf{y}}$ und ${\mathbf{y}}\preceq{\mathbf{x}}$ folgt ${\mathbf{x}}={\mathbf{y}}\,,\qquad\forall\,{\mathbf{x}},{\mathbf{y}}\in E\,,$

  (d)

  ${\,{\bf0}}\preceq{\mathbf{x}}\preceq{\,{\bf 1}}\,,\qquad\forall\,{\mathbf{x}}\in E\,.$

• Außerdem setzen wir voraus,
  • dass die Update-Funktion $\varphi:E\times(0,1]\to E$ isoton bezüglich der Halbordnung $\preceq$ ist, d.h., für beliebige ${\mathbf{x}},{\mathbf{y}}\in E$ mit ${\mathbf{x}}\preceq{\mathbf{y}}$ gelte

    $$\varphi({\mathbf{x}},u)\preceq \varphi({\mathbf{y}},u)\,,\qquad\forall\, u\in(0,1]\,.$$ (91)

    
    

• Die Innovationen ${\mathbf{U}}^{(1)},\ldots,{\mathbf{U}}^{(\ell)}$ seien mit Wahrscheinlichkeit $1$ identisch,
  • d.h., wir betrachten lediglich eine Folge ${\mathbf{U}}=\bigl(U_0,U_{-1},\ldots\bigr)$ von unabhängigen und $(0,1]$-gleichverteilten Zufallsvariablen und setzen ${\mathbf{U}}^{(1)}=\ldots={\mathbf{U}}^{(\ell)}={\mathbf{U}}$,
  • wobei die Markov-Kette ${\mathbf{X}}^{(m,i)}$ für beliebige $m\in\{-1,-2,\ldots\}$ und $i\in\{1,\ldots,\ell\}$ rekursiv gegeben sei durch

    $${\mathbf{X}}_n^{(m,i)}=\varphi\bigl({\mathbf{X}}^{(m,i)}_{n-1},U_n\bigr)\,, \qquad\forall\,n=m+1,m+2,\ldots\,.$$ (92)

    
    

Beachte

 

• Wenn ${\mathbf{x}}_i\preceq{\mathbf{x}}_j$, dann ergibt sich aus (91) und (92), dass für jedes $n\ge m$

  $${\mathbf{X}}_n^{(m,i)}\preceq{\mathbf{X}}_n^{(m,j)}\,.$$ (93)

  
  

• Insbesondere gilt für beliebige $n\ge m$ und $i\in\{1,\ldots,\ell\}$, dass

  $${\mathbf{X}}_n^{(m,\min)}\preceq{\mathbf{X}}_n^{(m,i)}\preceq{\mathbf{X}}_n^{(m,\max)}\,.$$ (94)

  
  
  • Dabei seien ${\mathbf{X}}^{(m,\min)}$ und ${\mathbf{X}}^{(m,\max)}$ die durch (92) rekursiv definierten Markov-Ketten
    $${\mathbf{X}}^{(m,\min)}=({\mathbf{X}}_m^{(m,\min)},{\mathbf{X}}_{m+1}^{(m,\min)},\ldots)$$   und$$\qquad {\mathbf{X}}^{(m,\max)}=({\mathbf{X}}_m^{(m,\max)},{\mathbf{X}}_{m+1}^{(m,\max)},\ldots)$$

  • mit ${\mathbf{X}}_m^{(m,\min)}={\,{\bf0}}$ bzw. ${\mathbf{X}}_m^{(m,\max)}={\,{\bf 1}}$.
• Wegen (94) genügt es, den Startpunkt der Simulation so weit in die Vergangenheit zu legen,
  • dass die Pfade der Minorante ${\mathbf{X}}^{(m,\min)}$ und der Majorante ${\mathbf{X}}^{(m,\max)}$ bis zum Zeitpunkt 0 miteinander verschmelzen,
  • d.h., wir betrachten die CFTP-Kopplungszeit

    $$\zeta=\min\bigl\{-m\ge 1:\,{\mathbf{X}}_0^{(m,\min)}={\mathbf{X}}_0^{(m,\max)}\bigr\}\,.$$ (95)

    
    

Theorem 3.24   $\;$ Die Update-Funktion $\varphi:E\times(0,1]\to E$ genüge der Isotonie-Bedingung $(\ref{iso.upd.fun})$.

• Für die in $(\ref{mon.kop.zei})$ definierte CFTP-Kopplungszeit gilt dann $\zeta<\infty$ mit Wahrscheinlichkeit $1$.
• 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

 

• Der Nachweis, dass ${\mathbf{X}}_0^{(m,i)}={\mathbf{X}}_0^{(-\zeta,j)}\sim{\boldsymbol{\pi}}$ für beliebige $m\le-\zeta$ und $i,j\in\{1,\ldots,\ell\}$ gilt, falls $P(\zeta<\infty)=1$, verläuft ähnlich wie im Beweis von Theorem 3.23 und wird deshalb hier weggelassen.
• Wir zeigen lediglich, dass $P(\zeta<\infty)=1$ gilt.
  • Dabei nutzen wir die Tatsache, dass für jedes $r\ge 1$

    $$\{\zeta>r\}\subset\Bigl\{{\mathbf{X}}_{-r+1}^{(-r,\min)}\not={\,{\bf 1}},\,\ldots,\, {\mathbf{X}}_0^{(-r,\min)}\not={\,{\bf 1}}\Bigr\}\,,$$ (96)

    
    
    denn aus (94) ergibt sich, dass
    

    $$\{\zeta>r\} = \Bigl\{ {\mathbf{X}}_0^{(-r,\min)}\not={\mathbf{X}}_0^{(-r,\max)}\Bigr\}$$

    $$= \Bigl\{{\mathbf{X}}_{-r+1}^{(-r,\min)}\not={\mathbf{X}}_{-r+1}^{(... ...)},\,\ldots,\, {\mathbf{X}}_0^{(-r,\min)}\not={\mathbf{X}}_0^{(-r,\max)}\Bigr\}$$

    $$\stackrel{(\ref{sem.min.maj})}{\subset} \Bigl\{{\mathbf{X}}_{-r+1}^{(-r,\min)}\not={\,{\bf 1}},\,\ldots,\, {\mathbf{X}}_0^{(-r,\min)}\not={\,{\bf 1}}\Bigr\}\,.$$

    
    

  • So wie im Beweis von Theorem 3.21 sei nun $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\,,$$ (97)

    
    
    und sei $r=m(r)n_0+k$ für gewisse Zahlen $m(r)=0,1,\ldots$ und $k=0,1,\ldots,n_0-1$.
  • Dann ergibt sich aus (96) und (97), dass
    

    $$P\bigl(\zeta=\infty\bigr) = \lim\limits_{r\to\infty}P\bigl(\zeta>r\bigr)$$

    $$\stackrel{(\ref{ent.hal.rel})}{\le} \lim\limits_{r\to\infty} P\Bigl({\mathbf{X}}_{-r+1}^{(-r,\min)}\not={\,{\bf 1}},\,\ldots,\, {\mathbf{X}}_0^{(-r,\min)}\not={\,{\bf 1}}\Bigr)$$

    $$\le \lim\limits_{r\to\infty} \sum\limits_{{\mathbf{x}}_1,\ldots,{\mat... ...hbf{x}}_2}\cdot\ldots\cdot p^{(n_0)}_{{\mathbf{x}}_{m(r)-1}{\mathbf{x}}_{m(r)}}$$

    $$\stackrel{(\ref{min.ube.war})}{\le} \lim\limits_{r\to\infty} (1-c)^{m(r)}=0\,.$$

    
    
    
     
      $\Box$
    
    
    

Beachte

 

• Manchmal ist die Update-Funktion $\varphi:E\times(0,1]\to E$ nicht isoton, sondern antiton bezüglich der Halbordnung $\preceq$, d.h., für beliebige ${\mathbf{x}},{\mathbf{y}}\in E$ mit ${\mathbf{x}}\preceq{\mathbf{y}}$ gilt

  $$\varphi({\mathbf{x}},u)\succeq \varphi({\mathbf{y}},u)\,,\qquad\forall\, u\in(0,1]\,.$$ (98)

  
  

• In diesem Fall ist die folgende Cross-Over-Technik nützlich.
  • Dabei konstruieren wir mit Hilfe der Update-Funktion $\varphi:E\times(0,1]\to E$ eine neue (isotone) Update-Funktion $\varphi^\prime:E\times(0,1]^2\to E$, die gegeben ist durch

    $$\varphi^\prime({\mathbf{x}};u_1,u_2)=\varphi(\varphi({\mathbf{x}},u_1),u_2)\,,\qquad\forall \,{\mathbf{x}}\in E;\,u_1,u_2\in(0,1]\,.$$ (99)

    
    

  • Aus (98) und (99) ergibt sich nämlich, dass für beliebige ${\mathbf{x}},{\mathbf{y}}\in E$ mit ${\mathbf{x}}\preceq{\mathbf{y}}$
    $$\varphi^\prime({\mathbf{x}};u_1,u_2)=\varphi(\varphi({\mathbf{x}}... ...u_2)=\varphi^\prime({\mathbf{y}};u_1,u_2)\,,\qquad\forall \,u_1,u_2\in(0,1]\,,$$
    d.h., $\varphi^\prime:E\times(0,1]^2\to E$ ist isoton, falls $\varphi:E\times(0,1]\to E$ antiton ist.
• Sei nun $\varphi:E\times(0,1]\to E$ eine gültige Update-Funktion bezüglich der irreduziblen und aperiodischen Übergangsmatrix ${\mathbf{P}}=(p_{{\mathbf{x}}{\mathbf{x}}^\prime})$ mit der ergodischen (Grenz-) Verteilung ${\boldsymbol{\pi}}=(\pi_{\mathbf{x}},\,{\mathbf{x}}\in E)$.
  • Dann ist die in (99) definierte Abbildung $\varphi^\prime:E\times(0,1]^2\to E$ eine gültige Update-Funktion bezüglich der (irreduziblen und aperiodischen) Zwei-Schritt-Übergangsmatrix ${\mathbf{P}}^{(2)}=(p^{(2)}_{{\mathbf{x}}{\mathbf{x}}^\prime})$ mit der gleichen ergodischen (Grenz-) Verteilung ${\boldsymbol{\pi}}=(\pi_{\mathbf{x}},\,{\mathbf{x}}\in E)$,
  • und für die Kopplungszeit $\zeta^\prime=\min\bigl\{-m\ge 1:\,{\mathbf{X}}_0^{(2m,\min)}={\mathbf{X}}_0^{(2m,\max)}\bigr\}$ ergibt sich auf die gleiche Weise wie im Beweis von Theorem 3.24, dass $\zeta^\prime<\infty$ mit Wahrscheinlichkeit $1$ und ${\mathbf{X}}_0^{(-2\zeta^\prime,i)}\sim{\boldsymbol{\pi}}$ für jedes $i\in\{1,\ldots,\ell\}$, falls $\varphi:E\times(0,1]\to E$ antiton ist.