next up previous contents
Nächste Seite: Rekursive Konstruktion der ,,Vergangenheit'' Aufwärts: Abschätzung der Konvergenzgeschwindigkeit; Reversibilität Vorherige Seite: Abschätzung der Konvergenzgeschwindigkeit; Reversibilität   Inhalt


Definition und Beispiele


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


Theorem 2.13    

Beweis
 

Beachte
 

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

      $\displaystyle 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

      $\displaystyle {\boldsymbol{\alpha}}^\top=(\alpha_0,\ldots,\alpha_\ell)\,,$   $\displaystyle \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

      $\displaystyle \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

      $\displaystyle \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
      $\displaystyle K$ $\displaystyle =$ $\displaystyle \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),$  
          $\displaystyle (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

        $\displaystyle 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

        $\displaystyle {\boldsymbol{\alpha}}=\Bigl(\frac{d_1}{d}\;,\ldots,\;\frac{d_\ell}{d}\Bigr)^\top\,,$   $\displaystyle \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

        $\displaystyle \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

      $\displaystyle {\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

        $\displaystyle {\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

      $\displaystyle \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

      $\displaystyle {\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.


next up previous contents
Nächste Seite: Rekursive Konstruktion der ,,Vergangenheit'' Aufwärts: Abschätzung der Konvergenzgeschwindigkeit; Reversibilität Vorherige Seite: Abschätzung der Konvergenzgeschwindigkeit; Reversibilität   Inhalt
Ursa Pantle 2003-09-29