Beispiele: Geburts- und Todesprozresse; Ising-Modell

1. Geburts- und Todesprozesse 
   • Die in (88) definierte Update-Funktion $\varphi:E\times(0,1]\to E$ genügt insbesondere dann der Isotonie-Bedingung (91),
     • wenn der Zustandsraum mit der Menge $E=\{1,\ldots,\ell\}$ identifiziert wird und dabei die natürliche Ordnung $\le$ der Zahlen $1,\ldots,\ell$ betrachtet wird
     • und wenn die Simulationsmatrix ${\mathbf{P}}=(p_{ij})$ isoton bezüglich der Ordnung $\le$ ist, d.h., für beliebige $i,j\in E$ mit $i \le j$ gelte

       $$\sum\limits_{r=k}^\ell p_{ir}\le \sum\limits_{r=k}^\ell p_{jr}\,, \qquad\forall\, k=1,\ldots,\ell\,.$$ (100)

       
       

   • Eine Klasse von Übergangsmatrizen ${\mathbf{P}}=(p_{ij})$, für die die Isotonie-Bedingung (100) erfüllt ist, ist durch die tridiagonalen Matrizen von Geburts- und Todesprozessen gegeben, so dass
     $${\mathbf{P}}=\left(\begin{array}{ccccc} 1-p_{12} & p_{12} & 0 &\l... ..._{\ell-1,\ell}\\ 0 & 0 & 0 &\ldots & 1-p_{\ell,\ell-1} \end{array}\right)\;,$$
     wobei $0<p_{i,i+1}\le 1/2$ für jedes $i=1,\ldots,\ell-1$ und $0<p_{i,i-1}\le 1/2$ für jedes $i=2,\ldots,\ell$.

     
     

     Abbildung: Monotone Rückwärtskopplung bei isotonen Geburts- und Todesprozessen

     

     
     

   • Andererseits genügt die in (88) definierte Update-Funktion $\varphi:E\times(0,1]\to E$ der Antitonie-Bedingung (98),
     • wenn ${\mathbf{P}}=(p_{ij})$ antiton bezüglich der Ordnung $\le$ ist,
     • d.h., wenn für beliebige $i,j\in E$ mit $i \le j$

       $$\sum\limits_{r=k}^\ell p_{ir}\ge \sum\limits_{r=k}^\ell p_{jr}\,, \qquad\forall\, k=1,\ldots,\ell\,.$$ (101)

       
       

   • Man kann leicht zeigen, dass es keine tridiagonale Übergangsmatrix ${\mathbf{P}}=(p_{ij})$ gibt, so dass die Bedingung (101) erfüllt ist, d.h. Geburts- und Todesprozessen sind niemals antiton.

     
     

   • Die Antitonie-Bedingung (101) ist jedoch beispielsweise für die folgende Matrix erfüllt:
     $${\mathbf{P}}=\left(\begin{array}{ccccc} 0 &\ldots & 0 & 0 & 1\\ ... ...& 1/(\ell-1)\\ 1/\ell & \ldots & 1/\ell & 1/\ell & 1/\ell \end{array}\right)$$

   
   

2. Ising-Modell 
   • Ähnlich wie bei dem in Abschnitt 3.3.1 diskutierten Hard-Core-Modell
     • betrachten wir einen verbundenen Graph $G=(V,K)$ mit der Menge $V=\{v_1,\ldots,v_{\vert V\vert}\}$ von (endlich vielen) Eckpunkten
     • und mit einer gewissen Menge $K\subset V^2$ von Kanten $e=(v_i,v_j)$, die jeweils zwei Eckpunkte $v_i,v_j$ miteinander verbinden.

     
     

   • Jedem Eckpunkt aus $V$ wird entweder der Wert $-1$ oder $1$ zugeordnet,
     • wobei der Zustandsraum $E=\{-1,1\}^{\vert V\vert}$ aller Konfigurationen ${\mathbf{x}}=(x(v),\,v\in V)$ betrachtet wird, d.h., es gilt entweder $x(v)=-1$ oder $x(v)=1$ für jedes $v\in V$
     • mit der ,,Bild-Interpretation'', dass $x(v)=-1$ ein weißes Pixel und $x(v)=1$ ein schwarzes Pixel bedeutet.

     
     

   • Für jedes ${\mathbf{x}}\in E$ sei die Wahrscheinlichkeit $\pi_{\mathbf{x}}$ der Konfiguration ${\mathbf{x}}$ gegeben durch den Ansatz (vgl. auch Übungsaufgabe 11.1)

     $$\pi_{\mathbf{x}}=\frac{1}{z_{G,J}}\;\exp\Biggl(J\sum\limits_{e=(v_i,v_j)\in K} x(v_i)x(v_j)\Biggr)$$ (102)

     
     
     für einen gewissen Parameter $J\ge0$, der in der Physik als ,,inverse Temperatur'' interpretiert wird:

     
     

     • Für $J=0$ (unendliche Temperatur) ist die in (102) gegebene Verteilung ${\boldsymbol{\pi}}=(\pi_{\mathbf{x}},\,{\mathbf{x}}\in E)$ die (diskrete) Gleichverteilung auf $E$.
     • Für $J\gg 0$ (niedrige Temperatur) besitzen diejenigen Konfigurationen große Wahrscheinlichkeiten, für die nur wenige benachbarte (d.h. durch Kanten verbundene) Paare von Eckpunkten unterschiedlich gefärbt sind.
     • Für $J\to\infty$ (Null-Temperatur) konvergiert die in (102) gegebene Verteilung ${\boldsymbol{\pi}}=(\pi_{\mathbf{x}},\,{\mathbf{x}}\in E)$ gegen die ,,Zwei-Punkt-Gleicherteilung'' $\bigl(\delta_{{\,{\bf0}}}+\delta_{{\,{\bf 1}}}\bigr)/2$,
     • wobei ${\,{\bf0}}$ und ${\,{\bf 1}}$ die beiden (extremen) Konfigurationen sind, die entweder nur aus weißen oder nur aus schwarzen Pixeln bestehen, d.h. $0(v)=-1$ bzw. $1(v)=1$ für jedes $v\in V$.

   • Dabei ist $z_{G,J}>0$ eine (im allgemeinen unbekannte) Normierungskonstante mit
     $$z_{G,J}=\sum\limits_{{\mathbf{x}}\in E}\exp\Biggl(-J\sum\limits_{e=(v_i,v_j)\in K} x(v_i)x(v_j)\Biggr)\,.$$

   • Die folgenden Abbildungen wurde dem Buch von O. Häggström (2002) Finite Markov Chains and Algorithmic Applications, CU Press, Cambridge entnommen.
     • Sie verdeutlichen die oben erwähnte Rolle des Parameters $J$,
     • d.h., mit wachsendem $J$ werden die zusammenhängenden ,,Klumpen'' von jeweils identisch gefärbten Pixeln größer.

     Abbildung: Typische Konfigurationen des Ising-Models für $J=0$ (oben links), $J=0.15$ (oben rechts), $J=0.3$ (unten links) bzw. $J=0.5$ (unten rechts)

     

     
     

   • Die Simulationsmatrix ${\mathbf{P}}=(p_{{\mathbf{x}}{\mathbf{x}}^\prime})$ sei durch den Gibbs-Sampler gegeben. Es gelte also (36), d.h.
     $$p_{{\mathbf{x}}{\mathbf{x}}^\prime}=\sum\limits_{v\in V} q_v \pi_... ...}}^\prime(-v)\bigr)\,,\qquad\forall\, {\mathbf{x}},{\mathbf{x}}^\prime\in E\,.$$
     • Dabei gilt für beliebige ${\mathbf{x}},{\mathbf{x}}^\prime\in E$ mit ${\mathbf{x}}(-v)={\mathbf{x}}^\prime(-v)$
       $$\pi_{x^\prime(v)\mid\, {\mathbf{x}}(-v)}=\left\{\begin{array}{ll}... ...+\pi_{{\mathbf{x}}_-}}\;, & \mbox{falls $x^\prime(v)= -1$,} \end{array}\right.$$
       wobei $x_-(v)=-1$ und ${\mathbf{x}}_-(-v)={\mathbf{x}}(-v)$ bzw. $x_+(v)=1$ und ${\mathbf{x}}_+(-v)={\mathbf{x}}(-v)$.
     • Aus (102) ergibt sich somit für $x^\prime(v)=1$
       $$\pi_{x^\prime(v)\mid\, {\mathbf{x}}(-v)} = \frac{\exp\Bigl(J\bigl... ...igr)+\exp\Bigl(J\bigl(k_+({\mathbf{x}}(-v))-k_-({\mathbf{x}}(-v))\bigr)\Bigr)}$$
       und analog für $x^\prime(v)=-1$
       $$\pi_{x^\prime(v)\mid\, {\mathbf{x}}(-v)} = \frac{\exp\Bigl(J\bigl... ...igr)+\exp\Bigl(J\bigl(k_-({\mathbf{x}}(-v))-k_+({\mathbf{x}}(-v))\bigr)\Bigr)}$$
       bzw.

       $$\pi_{x^\prime(v)\mid\, {\mathbf{x}}(-v)} = \left\{\begin{array}{l... ...thbf{x}}(-v))\bigr)\Bigr)}\;,&\mbox{falls $x^\prime(v)=-1$,} \end{array}\right.$$ (103)

       
       
       wobei $k_+({\mathbf{x}}(-v))$ bzw. $k_-({\mathbf{x}}(-v))$ die Anzahl derjenigen mit $v$ verbundenen Eckpunkte ist, die auf $1$ bzw. $-1$ gesetzt sind.

     
     

   • Für den Zustandsraum $E=\{-1,1\}^{\vert V\vert}$ definieren wir nun die Halbordnungsrelation $\preceq$
     • mit ${\mathbf{x}}\preceq{\mathbf{y}}$, falls $x(v)\le y(v)$ für jedes $v\in V$, so dass ${\,{\bf0}}\preceq{\mathbf{x}}\preceq{\,{\bf 1}}$ für jedes ${\mathbf{x}}\in E$,
     • wobei die Elemente des Zustandsraumes $E=\{{\mathbf{x}}_1,\ldots,{\mathbf{x}}_\ell\}$ so numeriert sein mögen, dass $i \le j$ gilt, falls ${\mathbf{x}}_i\preceq{\mathbf{x}}_j$ (was beispielsweise bei der lexikographischen Numierung der Elemente von $E$ zutreffend ist).

   • Aus (103) ergibt sich dann, dass für beliebige ${\mathbf{x}},{\mathbf{y}}\in E$ mit ${\mathbf{x}}\preceq{\mathbf{y}}$

     $$\pi_{1 \mid\, {\mathbf{x}}(-v)}\le \pi_{1\mid\, {\mathbf{y}}(-v)} \qquad \pi_{-1 \mid\, {\mathbf{x}}(-v)}\ge \pi_{-1\mid\, {\mathbf{y}}(-v)}\,,$$ (104)

     
     
     weil $1/(1+e^{-a})\le 1/(1+e^{-b})$ für beliebige Zahlen $a,b\in\mathbb{R}$ mit $a\le b$.
   • Die Update-Funktion $\varphi:E\times(0,1]^2\to E$ sei gegeben durch $\varphi({\mathbf{x}};u_1,u_2)={\mathbf{x}}^\prime$, wobei ${\mathbf{x}}^\prime=\bigl({\mathbf{x}}^\prime(v),\,v\in V\bigr)$ und für jedes $i=1,\ldots,\vert V\vert$
     $${\mathbf{x}}^\prime(v_i)=\left\{\begin{array}{ll} 1\,,&\mbox{fall... ...x}}(-v_i)}$,}\\ [3\jot] {\mathbf{x}}(v_i)\,,&\mbox{sonst.} \end{array}\right.$$
     • Für diese Update-Funktion $\varphi:E\times(0,1]^2\to E$ ergibt sich aus (104), dass für beliebige ${\mathbf{x}},{\mathbf{y}}\in E$ mit ${\mathbf{x}}\preceq{\mathbf{y}}$
       $$\varphi({\mathbf{x}};u_1,u_2)\preceq \varphi({\mathbf{y}};u_1,u_2)\,,\qquad\forall\, u_1,u_2\in(0,1]\,.$$

     • D.h., die (91) entsprechende Isotonie-Bedingung ist bezüglich der Halbordnung $\preceq$ erfüllt.