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, dass die Kette nicht in mehrere Einzelketten auf Teilmengen des ursprünglichen Zustandsraumes zerlegt (reduziert) werden kann. Irreduzibilität ist neben der Aperiodizität eine der wichtigen Eigenschaften von Markow-Ketten, die für die Konvergenz gegen eine stationäre Verteilung von Bedeutung ist. Da eine Markow-Kette stets durch einen Übergangsgraphen 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 \} . Dann heißt die Markow-Kette irreduzibel, genau dann, wenn es für alle  s_i, s_j \in S ein  n \in \mathbb{N} gibt, so dass

 P(X_n=s_i|X_0=s_j)>0

Jeder Zustand muss also von jedem anderen Zustand mit positiver Wahrscheinlichkeit erreichbar sein.

Äquivalente Definitionen[Bearbeiten]

Alternative Definitionen sind:

  1. Die Markow-Kette ist genau dann irreduzibel, wenn alle Zustände des Zustandsraumes miteinander kommunizieren.
  2. Ist  \tau_{ij} die Wartezeit vom Start in Zustand i bis zum erstmaligen Erreichen von j . Dann ist die Markow-Kette irreduzibel genau dann, wenn  P(\tau_{ij}<\infty)>0 ist für alle Zustände  i,j .

Ist der Zustandsraum endlich, so gilt:

  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.

Schwache Irreduzibilität[Bearbeiten]

Außerdem gibt es noch den Begriff der schwachen Irreduzibilität. Eine Markow-Kette heißt genau dann schwach irreduzibel, wenn

 P(\tau_{ij}<\infty)+P(\tau_{ji}<\infty)>0 gilt, wobei  \tau_{ij} die oben definierte Wartezeit ist.

Eigenschaften[Bearbeiten]

Ein Übergangsgraph mit Übergangsmatrix. Der Graph zerfällt, die Matrix ist reduzibel
  • Irreduzible Markow-Ketten sind immer entweder periodisch oder aperiodisch, da alle Zustände dieselbe Periode besitzen.
  • Irreduzible Markow-Ketten besitzen nie absorbierende Zustände.
  • Irreduzible Markow-Ketten sind entweder transient oder rekurrent, da diese Eigenschaft immer bei allen ihren Zuständen zugleich auftritt.
  • Ist der Zustandsraum endlich und  M die Übergangsmatrix der Markow-Kette, dann existiert folgendes Irreduzibilitäts-Kriterium: Existiert ein  n \in \mathbb{N} , so dass  M^n >0 gilt, dann ist die Markow-Kette irreduzibel und aperiodisch. Dabei ist das Größer-Zeichen komponentenweise zu verstehen.
  • Im Falle eines endlichen Zustandsraumes folgt aus Irreduzibilität positive Rekurrenz.

Beispiele[Bearbeiten]

Man betrachte die auf dem Zustandsraum  S=\{ 1,2,3,4 \} durch die Übergangsmatrix

 M_1=
\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

 M_2=
\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