Irreduzible Markow-Kette

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Irreduzibilität ist ein Attribut für diskrete Markow-Ketten, welches vereinfacht aussagt, ob die Kette in mehrere Einzelketten auf Teilmengen des ursprünglichen Zustandsraumes zerlegt (reduziert) werden kann. Irreduzibilität ist vor allem bei der Suche nach stationären Verteilungen von Bedeutung. Da eine Markow-Kette stets durch einen Übergangsgraph dargestellt werden kann, ist auch der äquivalente Begriff Transitivität gebräuchlich. Vereinfacht bedeutet Transitivität, dass es von jedem Zustand einen Weg in jeden anderen Zustand gibt.

Definition[Bearbeiten]

Sei  (X_t), \; t \in \N_0 eine (zeitlich homogene) Markow-Kette auf dem diskreten Zustandsraum  S = \{ s_1, s_2, s_3, \ldots \} und mit Übergangswahrscheinlichkeit  P_{ij}=P(X_n=s_j \mid X_{n-1}=s_i) \,.

Dann wird durch  s_i \rightarrow s_j \iff \exist\; n \in \mathbb{N}_0: (P^n)_{ij} >0 eine Relation und durch

 s_i \leftrightarrow s_j \iff s_i \rightarrow s_j\ \text{und}\ s_j \rightarrow s_i

eine Äquivalenzrelation auf S definiert. Gilt  s_i \leftrightarrow s_j , so nennt man diese Zustände miteinander verbunden. Die Verbundenheit sagt also aus, ob man von einem Zustand aus in endlicher Zeit und mit positiver Wahrscheinlichkeit zu einem anderen gelangen kann und umgekehrt.

Die Markow-Kette  X_t heißt nun irreduzibel, wenn S unter dieser Äquivalenzrelation nur eine Äquivalenzklasse besitzt, also jeder Zustand mit jedem verbunden ist.

Für Markow-Ketten mit endlichem Zustandsraum ist diese Definition äquivalent mit einer der folgenden Definitionen:

  1. Die Markow-Kette ist genau dann irreduzibel, wenn ihr Übergangsgraph stark zusammenhängend ist
  2. Die Markow-Kette ist genau dann irreduzibel, wenn die Übergangsmatrix, die sie beschreibt irreduzibel ist.
  3. Die Markow-Kette ist genau dann irreduzibel, wenn alle Zustände des Zustandsraumes miteinander Kommunizieren

Beispiele[Bearbeiten]

Man betrachte die auf dem Zustandsraum  S=\{ 1,2,3,4 \} durch die Übergangsmatrix 
\begin{pmatrix} 
    1/2 &  1/2 & 0 & 0 \\ 
     0 & 1/2 & 1/2 & 0 \\
    0 & 0 & 1/2 & 1/2 \\
    1/2 & 0 & 0 & 1/2
  \end{pmatrix}
definierte Kette.

Diese Kette springt, wenn sie sich im Zustand i befindet, mit 50-prozentiger Wahrscheinlichkeit nach i+1, sonst bleibt sie bei i (ist i=4, springt sie mit 50-prozentiger Wahrscheinlichkeit zurück zu 1). Offensichtlich kann die Kette von jedem Zustand aus innerhalb von drei Schritten zu jedem anderen Zustand gelangen, also sind alle Zustände miteinander verbunden. Diese Markow-Kette ist demnach irreduzibel.


Ein weiteres Beispiel: Betrachte auf demselben Zustandsraum die Matrix 
\begin{pmatrix} 
    1/2 &  0 & 1/2 & 0 \\ 
     0 & 1/3 & 0 & 2/3 \\
    1/2 & 0 & 1/2 & 0 \\
    0 & 2/3 & 0 & 1/3
  \end{pmatrix}
.

Hier gelangt man von Zustand 1 aus nur zu Zustand 3, und von diesem aus auch wieder nur zur 1 zurück. Die Zustände 2 und 4 sind von 1 und 3 aus auch in beliebig vielen Schritten nicht erreichbar und umgekehrt. S zerfällt hier also in die Äquivalenzklassen  \{ 1,3\} und  \{ 2,4 \} . In diesem Beispiel lässt sich die Kette in zwei separate Ketten auf den beiden Äquivalenzklassen und mit Matrizen


\begin{pmatrix} 
    1/2 &  1/2 \\ 
    1/2 &  1/2 \\
   \end{pmatrix}
sowie 
\begin{pmatrix} 
    1/3 &  2/3 \\ 
    2/3 &  1/3 \\
   \end{pmatrix}
zerlegen.

Literatur[Bearbeiten]

  • Albrecht Irle: Wahrscheinlichkeitstheorie und Statistik: Grundlagen - Resultate - Anwendungen. Teubner, Wiesbaden 2005.
  • Kai Lai Chung: Markov Chains with Stationary Transition Probabilities. Springer, Berlin 1967.
  • Esa Nummelin: General Irreducible Markov Chains and Non-Negative Operators. Cambridge University Press, Cambridge 2004.
  • Hans-Otto Georgii: Stochastik: Einführung in die Wahrscheinlichkeitstheorie und Statistik, 4. Auflage, de Gruyter, 2009. ISBN 978-3-110-21526-7