Metropolis-Hastings-Algorithmus

• Wir zeigen nun, dass der in Abschnitt 3.3.2 betrachtete Gibbs-Sampler ein Spezialfall einer größeren Klasse von MCMC-Algorithmen ist, und zwar der sogenannten Algorithmen vom Metropolis-Hastings-Typ, wobei die Verallgemeinerung in zweierlei Hinsicht erfolgt:
  1. Der in (36) betrachtete Ansatz

     $$p_{{\mathbf{x}}{\mathbf{x}}^\prime}=\sum\limits_{v\in V} q_v \pi_... ...bf{x}}^\prime(-v)\bigr)\,,\qquad\forall\, {\mathbf{x}},{\mathbf{x}}^\prime\in E$$ (46)

     
     
     für die Matrix ${\mathbf{P}}=(p_{{\mathbf{x}}{\mathbf{x}}^\prime})$ der Übergangswahrscheinlichkeiten $p_{{\mathbf{x}}{\mathbf{x}}^\prime}$ wird verallgemeinert.
  2. Zusätzlich wird ein Verfahren zur Akzeptanz bzw. Verwerfung der Updates ${\mathbf{x}}\longrightarrow{\mathbf{x}}^\prime$ in den Algorithmus integriert, dass auf einer ähnlichen Idee wie die in Abschnitt 3.2.3 diskutierte Akzeptanz- und Verwerfungsmethode beruht, vgl. insbesondere Theorem 3.5.

  
  

• Sei $V$ eine endliche (nichtleere) Index-Menge, und sei ${\mathbf{X}}=(X(v),\,v\in V)$ ein diskreter Zufallsvektor,
  • der mit Wahrscheinlichkeit $1$ seine Werte in der endlichen (Zustands-) Menge $E\subset\mathbb{R}^{\vert V\vert}$ annimmt,
  • wobei wir sowie bisher für die Wahrscheinlichkeitsfunktion ${\boldsymbol{\pi}}=(\pi_{\mathbf{x}},\,{\mathbf{x}}\in E)$ des Zufallsvektors ${\mathbf{X}}$ voraussetzen, dass $\pi_{\mathbf{x}}>0$ für jedes ${\mathbf{x}}\in E$.
• Die Übergangsmatrix ${\mathbf{P}}=\bigl(p_{{\mathbf{x}}{\mathbf{x}}^\prime}\bigr)$ der zu konstruierenden Markov-Kette ${\mathbf{X}}_0,{\mathbf{X}}_1,\ldots$ mit der ergodischen (Grenz-) Verteilung ${\boldsymbol{\pi}}$ sei gegeben durch den Ansatz

  $$p_{{\mathbf{x}}{\mathbf{x}}^\prime}=q_{{\mathbf{x}}{\mathbf{x}}^\... ...{\mathbf{x}}^\prime}\,, \qquad\forall\, {\mathbf{x}},{\mathbf{x}}^\prime\in E\; \mbox{mit ${\mathbf{x}}\not={\mathbf{x}}^\prime$,}$$ (47)

  
  
  • wobei ${\mathbf{Q}}=\bigl(q_{{\mathbf{x}}{\mathbf{x}}^\prime}\bigr)$ eine beliebige stochastische Matrix ist, die irreduzibel und aperiodisch sei, so dass $q_{{\mathbf{x}}{\mathbf{x}}^\prime}=0$ genau dann, wenn $q_{{\mathbf{x}}^\prime{\mathbf{x}}}=0$.
  • die Matrix ${\mathbf{A}}=\bigl(a_{{\mathbf{x}}{\mathbf{x}}^\prime}\bigr)$ gegeben ist durch

    $$a_{{\mathbf{x}}{\mathbf{x}}^\prime}=\frac{s_{{\mathbf{x}}{\mathbf{x}}^\prime}}{1+t_{{\mathbf{x}}{\mathbf{x}}^\prime}}\;,$$ (48)

    
    
    so dass

    $$t_{{\mathbf{x}}{\mathbf{x}}^\prime}=\left\{\begin{array}{ll}\disp... ... 0\,, &\mbox{falls $q_{{\mathbf{x}}{\mathbf{x}}^\prime}=0$,} \end{array}\right.$$ (49)

    
    

  • und ${\mathbf{S}}=\bigl(s_{{\mathbf{x}}{\mathbf{x}}^\prime}\bigr)$ eine beliebige symmetrische Matrix ist mit

    $$0< s_{{\mathbf{x}}{\mathbf{x}}^\prime}\le 1+\min\,\bigl\{t_{{\mathbf{x}}{\mathbf{x}}^\prime}\,,t_{{\mathbf{x}}^\prime{\mathbf{x}}}\bigr\}\,.$$ (50)

    
    

Beachte

 

• Der in (47) betrachtete Strukturansatz für die Übergangsmatrix ${\mathbf{P}}=\bigl(p_{{\mathbf{x}}{\mathbf{x}}^\prime}\bigr)$ lässt sich wie folgt interpretieren.
  • Zunächst wird gemäß ${\mathbf{Q}}=\bigl(q_{{\mathbf{x}}{\mathbf{x}}^\prime}\bigr)$ ein Kandidat ${\mathbf{x}}^\prime\in E$ für den Update ${\mathbf{x}}\longrightarrow{\mathbf{x}}^\prime$ erzeugt.
  • Falls ${\mathbf{x}}^\prime\not={\mathbf{x}}$, dann wird ${\mathbf{x}}^\prime$ mit der Wahrscheinlichkeit $a_{{\mathbf{x}}{\mathbf{x}}^\prime}$ akzeptiert,
  • d.h., mit der Wahrscheinlichkeit $1-a_{{\mathbf{x}}{\mathbf{x}}^\prime}$ wird der Update ${\mathbf{x}}\longrightarrow{\mathbf{x}}^\prime$ verworfen (und der jeweils aktuelle Zustand ${\mathbf{x}}$ wird somit nicht verändert).
• Um den in (47)-(50) definierten Metropolis-Hastings-Algorithmus anwenden zu können, müssen für eine gegebene ,,potientielle'' Übergangsmatrix ${\mathbf{Q}}=\bigl(q_{{\mathbf{x}}{\mathbf{x}}^\prime}\bigr)$ lediglich die Quotienten $\pi_{\mathbf{x}}/\pi_{{\mathbf{x}}^\prime}$ für diejenigen Paare ${\mathbf{x}},\,{\mathbf{x}}^\prime\in E$ von Zuständen bekannt sein, für die $q_{{\mathbf{x}}{\mathbf{x}}^\prime}>0$ gilt.
• Der in Abschnitt 3.3.2 betrachtete Spezialfall des Gibbs-Samplers ergibt sich,
  • wenn die ,,potentiellen'' Übergangswahrscheinlichkeiten $q_{{\mathbf{x}}{\mathbf{x}}^\prime}$ so wie in (46) gewählt werden.
  • Für beliebige ${\mathbf{x}},\,{\mathbf{x}}^\prime\in E$ mit $\char93 \{v\in V:\,x(v)\not=x^\prime(v)\}\le 1$ gilt dann
    $$\pi_{\mathbf{x}}q_{{\mathbf{x}}{\mathbf{x}}^\prime}= \pi_{{\mathbf{x}}^\prime}q_{{\mathbf{x}}^\prime{\mathbf{x}}}$$   und somit$$\qquad t_{{\mathbf{x}}{\mathbf{x}}^\prime}=1\,.$$

  • Mit der Wahl $s_{{\mathbf{x}}{\mathbf{x}}^\prime}= 1+\min\,\bigl\{t_{{\mathbf{x}}{\mathbf{x}}^\prime}\,,t_{{\mathbf{x}}^\prime{\mathbf{x}}}\bigr\}$ ergibt sich nun, dass $a_{{\mathbf{x}}{\mathbf{x}}^\prime}=1$ für beliebige ${\mathbf{x}},\,{\mathbf{x}}^\prime\in E$ mit $\char93 \{v\in V:\,x(v)\not=x^\prime(v)\}\le 1$.

Theorem 3.14   $\;$ Die in $(\ref{ube.mat.met})$- $(\ref{bed.mat.ess})$ gegebene Übergangsmatrix ${\mathbf{P}}=(p_{{\mathbf{x}}{\mathbf{x}}^\prime})$ ist irreduzibel und aperiodisch, und das Paar $({\mathbf{P}},{\boldsymbol{\pi}})$ ist reversibel.

Beweis

 

• Weil die in (48)-(50) gegebenen Akzeptanzwahrscheinlichkeiten $a_{{\mathbf{x}}{\mathbf{x}}^\prime}$ für beliebige ${\mathbf{x}},\,{\mathbf{x}}^\prime\in E$ positiv sind, ergibt sich die Irreduzibilität und Aperiodizität ${\mathbf{P}}=(p_{{\mathbf{x}}{\mathbf{x}}^\prime})$ aus den entsprechenden Eigenschaften von ${\mathbf{Q}}=(q_{{\mathbf{x}}{\mathbf{x}}^\prime})$.
• Um die 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\,,$$ (51)

  
  
  unterscheiden wir zwei Fälle.
  • Wenn $q_{{\mathbf{x}}{\mathbf{x}}^\prime}=q_{{\mathbf{x}}^\prime{\mathbf{x}}}=0$, dann gilt $p_{{\mathbf{x}}{\mathbf{x}}^\prime}=p_{{\mathbf{x}}^\prime{\mathbf{x}}}=0$ und somit auch (51).
  • Wenn $q_{{\mathbf{x}}{\mathbf{x}}^\prime}>0$, dann gilt auch $q_{{\mathbf{x}}^\prime{\mathbf{x}}}>0$, und aus (47)-(50) ergibt sich, dass
    

    $$\pi_{\mathbf{x}}p_{{\mathbf{x}}{\mathbf{x}}^\prime} = \pi_{\mathbf{x}} q_{{\mathbf{x}}{\mathbf{x}}^\prime} a_{{\mathbf{x}}{\mathbf{x}}^\prime}$$

    $$= \pi_{\mathbf{x}} q_{{\mathbf{x}}{\mathbf{x}}^\prime}\;\frac{s_{{\... ...f{x}}^\prime{\mathbf{x}}}+ \pi_{\mathbf{x}}q_{{\mathbf{x}}{\mathbf{x}}^\prime}}$$

    $$= \pi_{{\mathbf{x}}^\prime} p_{{\mathbf{x}}^\prime{\mathbf{x}}}\,,$$

    
    
    wobei sich die letzte Gleichheit aus der Symmetrie der Matrix ${\mathbf{S}}=\bigl(s_{{\mathbf{x}}{\mathbf{x}}^\prime}\bigr)$ ergibt.
    
    $\Box$

Beispiele

 

1. Metropolis-Algorithmus 
   • Der klassische Metropolis-Algorithmus ergibt sich, wenn in (50) die Gleichheit betrachtet wird, d.h., wenn
     $$s_{{\mathbf{x}}{\mathbf{x}}^\prime}= 1+\min\,\bigl\{t_{{\mathbf{x... ...athbf{x}}}\bigr\}\,, \qquad\forall\,{\mathbf{x}},\,{\mathbf{x}}^\prime\in E\,.$$

   • Für die Akzeptanzwahrscheinlichkeiten $a_{{\mathbf{x}}{\mathbf{x}}^\prime}$ gilt dann für beliebige ${\mathbf{x}},\,{\mathbf{x}}^\prime\in E$ mit $q_{{\mathbf{x}}{\mathbf{x}}^\prime}>0$, dass
     

     $$a_{{\mathbf{x}}{\mathbf{x}}^\prime} = \frac{1+\min\,\bigl\{t_{{\mathbf{x}}{\mathbf{x}}^\prime}\,,t_{{\mathbf{x}}^\prime{\mathbf{x}}} \bigr\}}{1+t_{{\mathbf{x}}^\prime{\mathbf{x}}}}$$

     $$= \frac{\min\,\bigl\{1+t_{{\mathbf{x}}{\mathbf{x}}^\prime}\,,\,1+t_... ...mathbf{x}}^\prime{\mathbf{x}}}}{ 1+t_{{\mathbf{x}}{\mathbf{x}}^\prime}}\Biggr\}$$

     $$= \min\Biggl\{1,\;\frac{\pi_{{\mathbf{x}}^\prime}q_{{\mathbf{x}}^\p... ...{\mathbf{x}}}}{ \pi_{\mathbf{x}}q_{{\mathbf{x}}{\mathbf{x}}^\prime}}\Biggr\}\,,$$

     
     
     d.h.,

     $$a_{{\mathbf{x}}{\mathbf{x}}^\prime}=\min\Biggl\{1,\;\frac{\pi_{{\... ...x}}^\prime}}\Biggr\}\,,\qquad\forall\,{\mathbf{x}},\,{\mathbf{x}}^\prime\in E\; \mbox{mit $q_{{\mathbf{x}}{\mathbf{x}}^\prime}>0$.}$$ (52)

     
     

   • Wenn die Matrix ${\mathbf{Q}}=(q_{{\mathbf{x}}{\mathbf{x}}^\prime})$ der ,,potentiellen'' Übergangswahrscheinlichkeiten symmetrisch ist, dann ergibt sich aus (52), dass

     $$a_{{\mathbf{x}}{\mathbf{x}}^\prime}=\min\Bigl\{1,\;\frac{\pi_{{\m... ...{\mathbf{x}}}\Bigr\}\,,\qquad\forall\,{\mathbf{x}},\,{\mathbf{x}}^\prime\in E\; \mbox{mit $q_{{\mathbf{x}}{\mathbf{x}}^\prime}>0$.}$$ (53)

     
     

   • Die Akzeptanzwahrscheinlichkeiten $a_{{\mathbf{x}}{\mathbf{x}}^\prime}$ sind also insbesondere dann durch (53) gegeben, wenn die ,,potentiellen'' Updates ${\mathbf{x}}\longrightarrow{\mathbf{x}}^\prime$ ,,auf gut Glück'' gewählt werden, d.h., wenn
     $$q_{{\mathbf{x}}{\mathbf{x}}^\prime}=\frac{1}{\vert E\vert}\;,\qquad\forall\,{\mathbf{x}},\,{\mathbf{x}}^\prime\in E\,.$$

   
   

2. Barker-Algorithmus 
   • Der sogenannte Barker-Algorithmus ergibt sich, wenn die Matrix ${\mathbf{S}}=\bigl(s_{{\mathbf{x}}{\mathbf{x}}^\prime}\bigr)$ mit $s_{{\mathbf{x}}{\mathbf{x}}^\prime}=1$ für beliebige ${\mathbf{x}},\,{\mathbf{x}}^\prime\in E$ betrachtet wird.
   • Für die Akzeptanzwahrscheinlichkeiten $a_{{\mathbf{x}}{\mathbf{x}}^\prime}$ gilt dann

     $$a_{{\mathbf{x}}{\mathbf{x}}^\prime}= \frac{\pi_{{\mathbf{x}}^\pri... ...\mathbf{x}}^\prime}}\;,\qquad\forall\,{\mathbf{x}},\,{\mathbf{x}}^\prime\in E\; \mbox{mit $q_{{\mathbf{x}}{\mathbf{x}}^\prime}>0$.}$$ (54)

     
     

   • Wenn die Matrix ${\mathbf{Q}}=(q_{{\mathbf{x}}{\mathbf{x}}^\prime})$ der ,,potentiellen'' Übergangswahrscheinlichkeiten symmetrisch ist, dann gilt insbesondere

     $$a_{{\mathbf{x}}{\mathbf{x}}^\prime}= \frac{\pi_{{\mathbf{x}}^\pri... ... + \pi_{\mathbf{x}}}\;,\qquad\forall\,{\mathbf{x}},\,{\mathbf{x}}^\prime\in E\; \mbox{mit $q_{{\mathbf{x}}{\mathbf{x}}^\prime}>0$.}$$ (55)

     
     

MCMC-Simulationsalgorithmus

 

• Genauso wie bei dem in Abschnitt 3.3.2 diskutierten Gibbs-Sampler konstruieren wir eine Markov-Kette ${\mathbf{X}}_0,{\mathbf{X}}_1,\ldots$
  • mit dem Zustandsraum $E$ und mit der in (47)-(50) gegebenen (irreduziblen und aperiodischen) Übergangsmatrix ${\mathbf{P}}=(p_{{\mathbf{x}}{\mathbf{x}}^\prime})$,
  • so dass ${\boldsymbol{\pi}}$ die ergodische (Grenz-) Verteilung der Markov-Kette ${\mathbf{X}}_0,{\mathbf{X}}_1,\ldots$ ist.
• Für hinreichend großes $n$ stimmt dann die Verteilung ${\boldsymbol{\alpha}}_n$ von ${\mathbf{X}}_n$ näherungsweise mit ${\boldsymbol{\pi}}$ überein.
• Um Fehlerbetrachtungen für MCMC-Simulationsalgorithmen durchführen zu können, ist es nützlich,
  • den Variationsabstand $d_{\rm TV}({\boldsymbol{\alpha}}_n,\,{\boldsymbol{\pi}})$ zwischen den Verteilungen ${\boldsymbol{\alpha}}_n$ und ${\boldsymbol{\pi}}$
  • bzw. Abschätzungen hierfür zu kennen, vgl. Abschnitt 3.4.1.