Irreduzible Markow-Kette

aus Wikipedia, der freien Enzyklopädie

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 Markovkette stets durch einen Graphen 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.

[Bearbeiten] Definition

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

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

$s_i \leftrightarrow s_j \Leftrightarrow s_i \rightarrow s_j\; 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.

[Bearbeiten] Beispiele

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.