Beispiel: Hard-Core-Modell

(vgl. O. Häggström (2002) Finite Markov Chains and Algorithmic Applications. CU Press, Cambridge)

• Wir betrachten 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, die jeweils zwei Eckpunkte miteinander verbinden.
• Jedem Eckpunkt aus $V$ wird entweder der Wert 0 oder $1$ zugeordnet,
  • wobei die folgende Menge $E\subset\{0,1\}^{\vert V\vert}$ von zulässigen Konfigurationen betrachtet wird,
  • für die keinem Paar von verbundenen Eckpunkten gleichzeitig der Wert $1$ zugeordnet wird, vgl. die Abbildung 4.
• Um unter den zulässigen Konfigurationen ${\mathbf{x}}\in E$ ,,auf gut Glück'' auswählen zu können, betrachten wir die (diskrete) Gleichverteilung ${\boldsymbol{\pi}}$ auf der Menge $E$ mit

  $$\pi_{\mathbf{x}}=\frac{1}{\ell}\;,\qquad\forall\, {\mathbf{x}}\in E\,,$$ (30)

  
  
  wobei $\ell=\vert E\vert$ die Anzahl aller zulässigen Konfigurationen bezeichnet.

Abbildung: Quadratisches Gitter $G$ der Größe $8\times 8$, wobei die schwarz gesetzten Pixel dem Wert $1$ entsprechen

[width=7cm, angle=1800]bild4.eps

• Wenn die Anzahlen $\vert V\vert$ und $\vert K\vert$ der Eckpunkte und Kanten des verbundenen Graphen $G=(V,K)$ große Zahlen sind,
  • dann ist die explizite Beschreibung der Menge $E$ der zulässigen Konfigurationen im allgemeinen schwierig,
  • die Anzahl $\ell$ aller zulässigen Konfigurationen ist deshalb typischerweise unbekannt,
  • und die Formel (30) kann somit nicht direkt zur Simulation von ,,zufällig ausgewählten'' zulässigen Konfigurationen genutzt werden.

MCMC-Simulationsalgorithmus

 

• Eine alternative Simulationsmethode besteht darin, eine Markov-Kette ${\mathbf{X}}_0,{\mathbf{X}}_1,\ldots$ zu konstruieren,
  • mit dem Zustandsraum $E$ und mit einer (geeignet gewählten) irreduziblen und aperiodischen Übergangsmatrix ${\mathbf{P}}$,
  • so dass die ergodische (Grenz-) Verteilung ${\boldsymbol{\pi}}$ der Markov-Kette ${\mathbf{X}}_0,{\mathbf{X}}_1,\ldots$ durch (30) gegeben ist.
• Dabei erzeugen wir einen ,,Pfad'' ${\mathbf{x}}_0,{\mathbf{x}}_1,\ldots$ der Markov-Kette, und zwar mit Hilfe der rekursiven Konstruktion von Markov-Ketten, die bereits in Abschnitt 2.1.3 diskutiert wurde:
  1. Wähle eine zulässige Anfangskonfiguration ${\mathbf{x}}_0\in E$.
  2. Wähle ,,auf gut Glück'' einen beliebigen Eckpunkt $v\in V$ und wirf eine faire Münze.
  3. Falls das Ereignis ,,Wappen'' eintritt und falls $x_n(w)=0$ für sämtliche Eckpunkte $w\in V$ gilt, die mit $v\in V$ verbunden sind, dann setze $x_{n+1}(v)=1$; ansonsten setze $x_{n+1}(v)=0$.
  4. Die Werte sämtlicher Eckpunkte $w\not= v$ bleiben unverändert, d.h., es gilt $x_{n+1}(w)=x_n(w)$ für jedes $w\not= v$.

Beachte

 

• Um die Schritte 2 - 4 dieses Algorithmus zu implementieren, muss die in (2.19) betrachtete ,,Update-Funktion'' $\varphi:E\times[0,1]\to E$ entsprechend spezifiziert werden.
• Das Einheitsintervall $(0,1]$ wird dabei in $2\vert V\vert$ gleichlange Teilintervalle (der Länge $1/2\vert V\vert$) zerlegt,
  • die den Ereignissen $(v_1$, Wappen), $(v_1$, Zahl), $\ldots$, $(v_{\vert V\vert}$, Wappen), $(v_{\vert V\vert}$, Zahl) entsprechen,
  • und es gilt ${\mathbf{x}}^\prime=\varphi({\mathbf{x}},z)$ mit

    $$x^\prime(v_i)=\left\{\begin{array}{ll} 1\,,&\mbox{falls $\display... ...c{2i-2}{2\vert V\vert}\;,\;\frac{2i}{2\vert V\vert}\Bigr]$.} \end{array}\right.$$ (31)

    
    

• Aus dem folgenden Theorem ergibt sich, dass für hinreichend großes $n$ die $n$-te Rückgabe ${\mathbf{x}}_n=(x_n(v),\, v\in V)$ des Algorithmus näherungsweise als ,,zufällig ausgewählte'' (d.h. gemäß ${\boldsymbol{\pi}}$-verteilte) zulässige Konfiguration angesehen werden kann.

Theorem 3.10    

• Sei ${\mathbf{P}}=(p_{{\mathbf{x}}{\mathbf{x}}^\prime})$ die Übergangsmatrix des in $(\ref{ueb.mat.mcm})$ betrachteten MCMC-Algorithmus für das Hard-Core-Modell, und sei ${\boldsymbol{\pi}}$ die in $(\ref{gle.ver.gra})$ gegebene Wahrscheinlichkeitsfunktion.
• Dann ist ${\mathbf{P}}$ irreduzibel und aperiodisch, und das Paar $({\mathbf{P}},{\boldsymbol{\pi}})$ ist reversibel.

Beweis

 

• Um die Aperiodizität von ${\mathbf{P}}=(p_{{\mathbf{x}}{\mathbf{x}}^\prime})$ zu zeigen, genügt es zu beachten, dass sämtliche Diagonalelemente von $p_{{\mathbf{x}}{\mathbf{x}}}$ von ${\mathbf{P}}$ positiv sind.
• Die Irreduzibilität von ${\mathbf{P}}$ ergibt sich aus den folgenden Überlegungen.
  • Seien ${\mathbf{x}},{\mathbf{x}}^\prime\in E$ zwei zulässige Konfigurationen, und seien $m({\mathbf{x}})$ bzw. $m({\mathbf{x}}^\prime)$ die Anzahlen der auf $1$ gesetzten Eckpunkte der Konfigurationen ${\mathbf{x}}$ bzw. ${\mathbf{x}}^\prime$.
  • Dann ist zunächst der Übergang ${\mathbf{x}}\longrightarrow{\mathbf{x}}_0$ in den ,,Nullzustand'' ${\mathbf{x}}_0\in E$ in $m({\mathbf{x}})$ Schritten mit positiver Wahrscheinlichkeit möglich, wobei ${\mathbf{x}}_0(v)=0$ für jedes $v\in V$ gilt.
  • Dabei werden (jeweils mit positiver Wahrscheinlichkeit) die ursprünglich auf $1$ gesetzten Eckpunkte von ${\mathbf{x}}$ der Reihe nach auf 0 gesetzt.
  • Anschließend kann man auf ähnliche Weise in $m({\mathbf{x}}^\prime)$ Schritten mit jeweils positiver Wahrscheinlichkeit vom ,,Nullzustand'' ${\mathbf{x}}_0$ in den Zustand ${\mathbf{x}}^\prime$ übergehen.
  • Hieraus ergibt sich insgesamt, dass der Übergang ${\mathbf{x}}\longrightarrow{\mathbf{x}}^\prime$ in endlich vielen Schritten mit positiver Wahrscheinlichkeit möglich ist.
• Es ist nun noch die Gültigkeit der Detailed-Balance-Gleichung (2.85) zu zeigen, d.h., dass

  $$\pi_{\mathbf{x}}\,p_{{\mathbf{x}}{\mathbf{x}}^\prime}=\pi_{{\math... ...\prime{\mathbf{x}}}\,, \qquad\forall\, {\mathbf{x}},{\mathbf{x}}^\prime\in E\,.$$ (32)

  
  
  • Wenn die Konfigurationen ${\mathbf{x}},{\mathbf{x}}^\prime\in E$ übereinstimmen, dann ist die Gültigkeit von (32) offensichtlich.
  • Wenn $x(v)\not=x^\prime(v)$ für mehr als einen Eckpunkt $v\in V$, dann gilt $p_{{\mathbf{x}}{\mathbf{x}}^\prime}=p_{{\mathbf{x}}^\prime{\mathbf{x}}}=0$, und (32) gilt somit auch in diesem Fall.
  • Es gelte nun $x(v)\not=x^\prime(v)$ für ein $v\in V$ und $x(w)=x^\prime(w)$ für alle $w\not= v$.
  • Dann gilt $x(w)=x^\prime(w)=0$ für sämtliche Eckpunkte $w\not= v$, die mit $v$ verbunden sind, und folglich ist
    $$\pi_{\mathbf{x}}\,p_{{\mathbf{x}}{\mathbf{x}}^\prime}\;=\;\frac{1... ...V\vert} \;=\;\pi_{{\mathbf{x}}^\prime}\,p_{{\mathbf{x}}^\prime{\mathbf{x}}}\,.$$
    
     
      $\Box$
    
    
    

Beachte

 

• Für jedes ${\mathbf{x}}\in E$ sei $m({\mathbf{x}})$ die Anzahl der auf $1$ gesetzten Eckpunkte der zulässigen Konfiguration ${\mathbf{x}}$.
• Wenn die zulässige Konfiguration ,,auf gut Glück'' ausgewählt wird, dann gilt für den Erwartungswert ${\mathbb{E}\,}Y$ der zufalligen Anzahl $Y$ der auf $1$ gesetzten Eckpunkte, dass

  $${\mathbb{E}\,}Y=\frac{1}{\ell}\;\sum\limits_{{\mathbf{x}}\in E} m({\mathbf{x}})\,.$$ (33)

  
  

• Wenn $\ell$ eine große Zahl ist, dann ist jedoch die direkte Bestimmung des Erwartungswertes ${\mathbb{E}\,}Y$ mit Hilfe von Formel (33) im allgemeinen nicht möglich, weil die analytische Bestimmung der Anzahlen $m({\mathbf{x}})$ schwierig ist.
• Eine alternative Methode zur (näherungsweisen) Bestimmung des Erwartungswertes ${\mathbb{E}\,}Y$ beruht auf der Erzeugung von $k$ ,,zufällig ausgewählten'' zulässigen Konfigurationen ${\mathbf{x}}_n^{(1)},{\mathbf{x}}_n^{(2)},\ldots,{\mathbf{x}}_n^{(k)}\in E$ mit $k$ Runs des oben beschriebenen Algorithmus der MCMC-Simulation.
• Das arithmetische Mittel $\bigl(m({\mathbf{x}}_n^{(1)})+m({\mathbf{x}}_n^{(2)})+\ldots+m({\mathbf{x}}_n^{(k)})\bigr)/k$ liegt wegen des starken Gesetzes der großen Zahlen (mit hoher Wahrscheinlichkeit) nahe bei ${\mathbb{E}\,}Y$, falls die Runlänge $n$ und der Stichprobenumfang $k$ jeweils hinreichend groß sind.