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 {\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, genau dann, wenn es für alle {\displaystyle s_{i},s_{j}\in S} ein  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 positiver Wahrscheinlichkeit erreichbar sein.

Äquivalente Definitionen

Äquivalent sind:

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

Schwache Irreduzibilität

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

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

Eigenschaften

Ein Übergangsgraph mit Übergangsmatrix. Der Graph zerfällt, die Matrix ist reduzibel

Beispiele

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.

Trenner
Basierend auf einem Artikel in: Wikipedia.de
Seitenende
Seite zurück
©  biancahoegel.de
Datum der letzten Änderung: Jena, den: 21.12. 2023