Irreduzible Markow-Kette
# Irreduzible Markow-Kette

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

Sei $(X_{t}),\;t\in \mathbb {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 strikt positiver Wahrscheinlichkeit erreichbar sein.

### Äquivalente Definitionen

Äquivalent sind:

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

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

* Der Übergangsgraph der Markow-Kette ist stark zusammenhängend.
* 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.

### Schwache Irreduzibilität

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

* 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 $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

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.

