Definition und Beispiele

• Eine stationäre Markov-Kette $X_0,X_1,\ldots:\Omega\to E$ bzw. das zugehörige Paar $({\mathbf{P}},{\boldsymbol{\alpha}})$ bestehend aus der Übergangsmatrix ${\mathbf{P}}$ und der (stationären) Anfangsverteilung ${\boldsymbol{\alpha}}$ heißt reversibel, wenn ihre endlich-dimensionalen Verteilungen nicht von der Orientierung der Zeitachse abhängen, d.h., wenn

  $$P(X_0=i_0,X_1=i_1,\ldots,X_{n-1}=i_{n-1},X_n=i_n)=P(X_n=i_0,X_{n-1}=i_1,\ldots,X_1=i_{n-1},X_0=i_n)$$ (84)

  
  
  für beliebige $n\ge 0$ und $i_0,\ldots,i_n\in E$.
• Die Reversibilität von Markov-Ketten ist insbesondere bei der Konstruktion von dynamischen Simulationsalgorithmen eine nützliche Modelleigenschaft, vgl. die Abschnitte 3.3 bis 3.5.

Wir leiten zunächst eine einfache Charakterisierung der Reversibilität von stationären (jedoch nicht unbedingt ergodischen) Markov-Ketten her.

Theorem 2.13    

• Sei $X_0,X_1,\ldots:\Omega\to E$ eine Markov-Kette mit dem Zustandsraum $E$, mit der Übergangsmatrix ${\mathbf{P}}=(p_{ij})$ und der stationären Anfangsverteilung ${\boldsymbol{\alpha}}=(\alpha_1,\alpha_2,\ldots)^\top$, so dass $\alpha_i>0$ für jedes $i\in E$.
• Die Markov-Kette ist genau dann reversibel, wenn

  $$\alpha_i \,p_{ij}=\alpha_j\,p_{ji} \mbox{für beliebige $i,j\in E$.}$$ (85)

  
  

Beweis

 

• Die Notwendigkeit der Bedingung (85) ergibt sich unmittelbar aus der Definitionsgleichung (84). Aus (84) folgt nämlich insbesondere, dass
  $$P(X_0=i,X_1=j)=P(X_1=i,X_0=j)$$   $$\mbox{für beliebige $i,j\in E$.}$$$$$$

• Somit gilt auch
  

  $$\alpha_i \,p_{ij} = P(X_0=i,X_1=j)$$

  $$= P(X_1=i,X_0=j)$$

  $$= \alpha_j\,p_{ji}\,.$$

  
  

• Wenn umgekehrt (85) gilt, dann ergibt sich aus der Definitionsgleichung (3) von Markov-Ketten, dass
  

  $${ P(X_0=i_0,X_1=i_1,\ldots,X_{n-1}=i_{n-1}, X_n=i_n)}$$

  $$\stackrel{(\ref{def.mar.for})}{=} \alpha_{i_0}p_{i_0i_1}p_{i_1i_2}\ldots p_{i_{n-1}i_n}$$

  $$\stackrel{(\ref{for.cha.rev})}{=} p_{i_1i_0}\alpha_{i_1}p_{i_1i_2}\ldots p_{i_{n-1}i_n}$$

  $$\vdots$$

  $$\stackrel{(\ref{for.cha.rev})}{=} p_{i_1i_0}p_{i_2i_1}\ldots p_{i_ni_{n-1}}\alpha_{i_n}$$

  $$= \alpha_{i_n} p_{i_ni_{n-1}}\ldots p_{i_2i_1}p_{i_1i_0}$$

  $$\stackrel{(\ref{def.mar.for})}{=} P(X_0=i_n,X_1=i_{n-1},\ldots,X_{n-1}=i_1,X_n=i_1)$$

  $$= P(X_n=i_0,X_{n-1}=i_1,\ldots,X_1=i_{n-1},X_0=i_n)\,.$$

  
  

• Damit ist die Gültigkeit von (84) bewiesen.
  
  $\Box$

Beachte

 

• Im Beweis von Theorem 2.13 wird nicht benötigt,
  • dass die stationäre Markov-Kette $X_0,X_1,\ldots$ ergodisch ist,
  • sondern lediglich, dass sämtliche Komponenten $\alpha_{0i}$ der stationären Anfangangsveteilung ${\boldsymbol{\alpha}}=(\alpha_1,\alpha_2,\ldots)^\top$ positiv sind.
• Mit anderen Worten
  • Falls die Übergangsmatrix ${\mathbf{P}}$ nicht irreduzibel oder nicht aperiodisch ist und somit die Grenzverteilung ${\boldsymbol{\pi}}$ nicht existiert bzw. nicht eindeutig bestimmt ist,
  • dann bleibt die Gültigkeit von Theorem 2.13 dennoch erhalten, wenn ${\boldsymbol{\alpha}}$ eine beliebige stationäre Anfangsverteilung ist mit $\alpha_i>0$ für jedes $i\in E$.
• Weil ${\mathbf{P}}=(p_{ij})$ eine stochastische Matrix ist, ergibt sich aus (85), dass für beliebige $i\in E$
  $$\alpha_i=\alpha_i\sum\limits_{j\in E... ...p_{ij}\stackrel{(\ref{for.cha.rev})}{=}\sum\limits_{j\in E}\alpha_j\,p_{ji}\,.$$

• Mit anderen Worten: Jede Anfangsverteilung ${\boldsymbol{\alpha}}$, die der sogenannten Detailed-Balance-Bedingung (85) genügt, ist notwendigerweise eine stationäre Anfangsverteilung, d.h., sie genügt dann auch der ,,globalen'' Balance-Bedingung ${\boldsymbol{\alpha}}^\top={\boldsymbol{\alpha}}^\top{\mathbf{P}}$.

Beispiele

 

1. Diffusionsmodell 
   • Wir kehren zu dem bereits in Abschnitt 2.2.3 betrachteten Diffusionsmodell mit dem endlichen Zustandsraum $E=\{0,1,\ldots,\ell\}$, der irreduziblen (jedoch nicht aperiodischen) Übergangsmatrix ${\mathbf{P}}=(p_{ij})$, wobei

     $$p_{ij}=\left\{\begin{array}{ll} \displaystyle \frac{\ell-i}{\ell}... ...\;, &\mbox{falls $i>0$\ und $j=i-1$,}\\ 0\,, &\mbox{sonst,} \end{array}\right.$$ (86)

     
     
     und der (gemäß Theorem 2.10 eindeutig bestimmten, jedoch nicht ergodischen) stationären Anfangsverteilung

     $${\boldsymbol{\alpha}}^\top=(\alpha_0,\ldots,\alpha_\ell)\,, \mbox{wobei $\;\;\displaystyle\alpha_i=\frac{1}{2^\ell}\;\left(\b... ...}{c}\ell\\ i\end{array}\right)\,,\qquad \forall\, i\in\{0,1,\ldots,\ell\}\,.$}$$ (87)

     
     

   • Man kann zeigen, dass dann
     $$\alpha_i \,p_{ij}=\alpha_j\,p_{ji}$$
     für beliebige $i,j\in E$ gilt, d.h., das in (86) bzw. (87) gegebene Paar $({\mathbf{P}},{\boldsymbol{\alpha}})$ ist reversibel.

   
   

2. Geburts- und Todesprozesse 
   • Für die ebenfalls in Abschnitt 2.2.3 betrachteten Geburts- und Todesprozesse mit einer oder zwei reflektierenden Schranken sei die Übergangsmatrix ${\mathbf{P}}=(p_{ij})$ so beschaffen, dass die Gleichung ${\boldsymbol{\alpha}}^\top={\boldsymbol{\alpha}}^\top{\mathbf{P}}$ eine (eindeutig bestimmte) Wahrscheinlichkeitslösung ${\boldsymbol{\alpha}}^\top=(\alpha_1,\alpha_2,\ldots)$ besitzt.
   • Dann kann man zeigen, dass
     $$\alpha_i \,p_{ij}=\alpha_j\,p_{ji}$$
     für beliebige $i,j\in E$ gilt.

   
   

3. Zufällige Irrfahrten auf Graphen 
   • Wir betrachten einen verbundenen Graph $G=(V,K)$
     • mit der Menge $V=\{v_1,\ldots,v_\ell\}$ von $\ell$ Eckpunkten und der Menge $K$ von Kanten, die jeweils zwei Eckpunkte miteinander verbinden,
     • so dass es für jedes Paar $v_i,v_j\in V$ von Eckpunkten einen ,,Pfad'' von Kanten aus $K$ gibt, der die Kanten $v_i$ und $v_j$ miteinander verbindet.
   • In der Abbildung ist ein solcher Graph $G=(V,K)$ dargestellt, und zwar mit der Menge $V=\{v_1,\ldots,v_8\}$ von 8 Eckpunkten und der Menge $K$ von $12$ Kanten, wobei
     

     $$K = \bigl\{(v_1,v_2),(v_1,v_3),(v_2,v_3),(v_2,v_8),(v_3,v_4), (v_3,v_7),(v_3,v_8),(v_4,v_5),(v_4,v_6),(v_5,v_6),$$

     $$(v_6,v_7),(v_7,v_8)\bigr\}\,.$$

     
     

   
   
   
   
   
   • Eine zufällige Irrfahrt auf dem Graph $G=(V,K)$ ist eine Markov-Kette $X_0,X_1,\ldots:\Omega\to E$
     • mit dem Zustandsraum $E=\{1,\ldots,\ell\}$ und der Übergangsmatrix ${\mathbf{P}}=(p_{ij})$, wobei

       $$p_{ij}=\left\{\begin{array}{ll} \displaystyle \frac{1}{d_i}\;, &\... ...$\ und $v_j$\ Nachbarn sind,}\\ [3\jot] 0\,, &\mbox{sonst.} \end{array}\right.$$ (88)

       
       

     • Dabei werden zwei Eckpunkte $v_i$ und $v_j$ Nachbarn genannt, falls sie die Endpunkte einundderselben Kante sind, und $d_i$ bezeichnet die Anzahl der Nachbarn von $v_i$.
   • Man kann zeigen (vgl. Übungsaufgabe 5.4), dass
     • die in (88) gegebene Übergangsmatrix irreduzibel ist,
     • die (gemäß Theorem 2.10 eindeutig bestimmte) stationäre Anfangsverteilung ${\boldsymbol{\alpha}}$ gegeben ist durch

       $${\boldsymbol{\alpha}}=\Bigl(\frac{d_1}{d}\;,\ldots,\;\frac{d_\ell}{d}\Bigr)^\top\,, \mbox{wobei $\;d=\sum\limits_{i=1}^\ell d_i$,}$$ (89)

       
       

     • das in (88)-(89) gegebene Paar $({\mathbf{P}},{\boldsymbol{\alpha}})$ reversibel ist, denn für beliebige $i,j\in\{1,\ldots,\ell\}$ gilt
       $$\alpha_i \,p_{ij}=\left\{\begin{array}{ll} \displaystyle \frac{d_... ...arn sind,}\\ [3\jot] 0=\alpha_j \,p_{ji}\,, &\mbox{sonst.} \end{array}\right.$$

   • Für das in der Abbildung betrachtete Zahlenbeispiel ist die in (88) gegebene Übergangsmatrix ${\mathbf{P}}$ nicht nur irreduzibel, sondern auch aperiodisch, und die stationäre Anfangsverteilung ${\boldsymbol{\alpha}}$ $(={\boldsymbol{\pi}}=\lim_{n\to\infty}{\boldsymbol{\alpha}}_n)$ ist in diesem Fall gegeben durch
     $${\boldsymbol{\alpha}}=\Bigl(\frac{2}{24}\;,\frac{3}{24}\;,\frac{5... ...24}\;,\frac{2}{24}\;,\frac{3}{24}\;,\frac{3}{24}\;,\frac{3}{24} \Bigr)^\top\,.$$

   
   

4. Zyklische zufällige Irrfahrten
   • Das folgende Beispiel einer zyklischen zufälligen Irrfahrt ist nicht reversibel.
     • Dabei sei $E=\{1,2,3,4\}$ und

       $${\mathbf{P}}=\left(\begin{array}{cccc} 0 & 0.75 & 0 & 0.25 \\ [3... ...\ [3\jot] 0 & 0.25 & 0& 0.75\\ [3\jot] 0.75 & 0 & 0.25 & 0 \end{array}\right)$$ (90)

       
       

     • d.h., der Übergangsgraph ist gegeben durch
       
       
       
       
       
       
       
   • Die in (90) gegebene Übergangsmatrix ist offenbar irreduzibel, jedoch nicht aperiodisch, und die (wegen Theorem 2.10 eindeutig bestimmte) Anfangsverteilung ${\boldsymbol{\alpha}}$ ist gegeben durch ${\boldsymbol{\alpha}}=(1/4,1/4,1/4,1/4)^\top$.
   • Andererseits gilt jedoch
     $$\alpha_1 p_{12}=\frac{1}{4}\;\frac{3}{4}=\frac{3}{16}>\frac{1}{16}=\frac{1}{4}\;\frac{1}{4} =\alpha_2 p_{21}\,.$$

   • Es ist intuitiv klar, warum diese zyklische zufällige Irrfahrt nicht reversibel ist, denn die ,,Fortbewegung'' im Uhrzeigersinn ist viel wahrscheinlicher als die ,,Fortbewegung'' gegen den Uhrzeigersinn.

   
   

5. Doppelt-stochastische Übergangsmatrix
   • Wir betrachten nun noch das folgende Beispiel einer Übergangsmatrix ${\mathbf{P}}=(p_{ij})$ und einer stationären Anfangsverteilung ${\boldsymbol{\alpha}}=(\alpha_1,\ldots,\alpha_\ell)^\top$, die nicht reversibel sind: Für $a,b>0$ mit $b<a$ und $2a+b=1$ sei

     $${\mathbf{P}}=\left(\begin{array}{ccc}a & a-b & 2b \\ [3\jot] a+b & b & a-b \\ [3\jot] 0 & a+b & a \end{array}\right)\;.$$ (91)

     
     

   • Diese Übergangsmatrix ${\mathbf{P}}$ ist doppelt-stochastisch, d.h., die transponierte Matrix ${\mathbf{P}}^\top$ ist ebenfalls eine stochastische Matrix, und ${\mathbf{P}}$ ist offenbar auch quasi-positiv.
   • Für die (eindeutig bestimmte) stationäre Anfangsverteilung ${\boldsymbol{\pi}}=\lim_{n\to\infty}{\boldsymbol{\alpha}}_n$ gilt dann ${\boldsymbol{\pi}}=(1/3,1/3,1/3)^\top$.
   • Weil jedoch die in (91) gegebene Übergangsmatrix ${\mathbf{P}}$ nicht symmetrisch ist, ist somit $({\mathbf{P}},{\boldsymbol{\alpha}})$ nicht reversibel.