Irreduzible Markow-Kette

Sei ${\displaystyle (X_{t}),\;t\in \mathbb {N} _{0}}$  eine (zeitlich homogene) Markow-Kette auf dem diskreten Zustandsraum ${\displaystyle S=\{s_{1},s_{2},s_{3},\ldots \}}$ . Dann heißt die Markow-Kette irreduzibel, wenn es für alle ${\displaystyle s_{i},s_{j}\in S}$  ein ${\displaystyle n\in \mathbb {N} }$  gibt, so dass

${\displaystyle P(X_{n}=s_{i}|X_{0}=s_{j})>0}$ .

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

Folgende Aussagen sind äquivalent:

1. Die Markow-Kette ist irreduzibel.
2. Es ist ${\displaystyle P(\tau _{ij}<\infty )>0}$  ist für alle Zustände ${\displaystyle i,j}$ . Dabei ist ${\displaystyle \tau _{ij}}$  die Wartezeit vom Start in Zustand ${\displaystyle i}$  bis zum erstmaligen Erreichen von ${\displaystyle j}$ .
3. Alle Zustände des Zustandsraumes kommunizieren miteinander.
4. Jeder Zustand ${\displaystyle i}$  ist von jedem anderen Zustand ${\displaystyle j}$  aus erreichbar.
5. Es existiert nur eine Kommunikationsklasse.

Ist der Zustandsraum endlich, so lässt sich die Liste erweitern um die folgenden Punkte:

1. Der Übergangsgraph der Markow-Kette ist stark zusammenhängend.
2. Die Übergangsmatrix, welche die Markow-Kette beschreibt, ist irreduzibel.

Manche Autoren definieren zuerst die irreduzibilität einer Teilmenge des Zustandsraumes (auch über die obigen Kriterien) und nennen dann die Markow-Kette irreduzibel, wenn der gesamte Zustandsraum eine irreduzible Menge ist.^[1]

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

${\displaystyle P(\tau _{ij}<\infty )+P(\tau _{ji}<\infty )>0}$  gilt,

wobei ${\displaystyle \tau _{ij}}$  die oben definierte Wartezeit ist.^[2]

• Irreduzible Markow-Ketten sind entweder periodisch oder aperiodisch, da alle Zustände dieselbe Periode besitzen.
• Irreduzible Markow-Ketten besitzen keine absorbierenden 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 ${\displaystyle M}$  die Übergangsmatrix der Markow-Kette, dann existiert folgendes Irreduzibilitäts-Kriterium: Existiert ein ${\displaystyle n\in \mathbb {N} }$ , so dass ${\displaystyle 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.

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

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

${\displaystyle 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 ${\displaystyle \{1,3\}}$  und ${\displaystyle \{2,4\}}$ . In diesem Beispiel lässt sich die Kette in zwei separate Ketten auf den beiden Äquivalenzklassen und mit Matrizen

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

• 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-11-021526-7
• Achim Klenke: Wahrscheinlichkeitstheorie. 3. Auflage. Springer-Verlag, Berlin Heidelberg 2013, ISBN 978-3-642-36017-6, doi:10.1007/978-3-642-36018-3. 
• David Meintrup, Stefan Schäffler: Stochastik. Theorie und Anwendungen. Springer-Verlag, Berlin Heidelberg New York 2005, ISBN 3-540-21676-6, doi:10.1007/b137972. 

1. ↑ Meintrup, Schäffler: Stochastik. 2005, S. 242.
2. ↑ Klenke: Wahrscheinlichkeitstheorie. 2013, S. 377.