Periodische Markow-Kette

Periodische Markow-Kette i​st ein Begriff a​us der Stochastik u​nd beschreibt e​ine für d​ie Konvergenz wichtige Eigenschaft e​iner Markow-Kette. Anschaulich i​st eine Markow-Kette periodisch, w​enn man t​rotz der Zufälligkeit d​es Gesamtsystems exakte Voraussagen darüber treffen kann, i​n welcher Teilmenge d​er Zustandsmenge s​ich das System a​n einem bestimmten Zeitpunkt befinden wird. Aperiodizität i​st besonders wichtig für d​as Konvergenzverhalten v​on Markow-Ketten g​egen eine Stationäre Verteilung.

Definition

Gegeben sei eine Markow-Kette in diskreter Zeit und mit höchstens abzählbarem Zustandsraum ${\displaystyle Z}$ . Dann ist für alle ${\displaystyle i\in Z}$ die Menge

${\displaystyle N_{i}:=\{n|P(X_{n}=i|X_{0}=i)>0\}}$

der möglichen Rückkehrzeiten zum Startpunkt definiert. Dann heißt ${\displaystyle d(i):=\operatorname {ggT} (N_{i})}$ die Periode des Zustandes ${\displaystyle i}$ . Hierbei bezeichnet ${\displaystyle \operatorname {ggT} }$ den größten gemeinsamen Teiler. Ist ${\displaystyle P(X_{n}=i|X_{0}=i)=0}$ für alle ${\displaystyle n>0}$ , so setzen wir ${\displaystyle d(i)=\infty }$ . Haben alle Zustände der Markow-Kette Periode eins, so heißt diese aperiodisch. Haben alle Zustände dieselbe Periode ${\displaystyle d>1}$ , so heißt die Markow-Kette periodisch mit Periode ${\displaystyle d}$ . Bei periodischen Markow-Ketten kann bei Kenntnis des Startzustandes also immer mithilfe des Zeitpunktes auf den aktuellen Zustand geschlossen werden.

Eigenschaften

• Anschaulich bedeutet dies folgendes: Startet man in einem Zustand mit Periode ${\displaystyle d(i)>1}$ , so kann das System höchstens zu den Zeitpunkten ${\displaystyle nd(i)}$ zurückkehren.
• Tatsächlich gilt für jeden Zustand ${\displaystyle i}$ mit Periode ${\displaystyle d(i)}$ , dass ab einem bestimmten Zeitpunkt eine Rückkehr zu jeder Periode möglich ist. Es existiert also ein ${\displaystyle N(i)}$ , so dass ${\displaystyle p_{ii}^{nd(i)}>0}$ für alle ${\displaystyle n>N(i)}$
• Miteinander kommunizierende Zustände besitzen dieselbe Periode.
• Demnach besitzen in einer irreduziblen Markow-Kette alle Zustände dieselbe Periode. Die Kette ist also immer periodisch oder aperiodisch.
• Ist der Zustandsraum der Markow-Kette endlich, und existiert eine Potenz der Übergangsmatrix, deren Einträge alle positiv sind, dann ist die Markow-Kette irreduzibel und aperiodisch.
• Eine irreduzible, positiv rekurrente Markow-Kette ist genau dann aperiodisch, wenn sie gegen eine stationäre Verteilung konvergiert.
• Bei einer irreduziblen Markow-Kette mit Periode d lässt sich der Zustandsraum disjunkt zerlegen in

${\displaystyle Z={\dot {\bigcup _{k=0,\dots ,d-1}}}Z_{k}}$

so dass wenn ${\displaystyle i}$ in ${\displaystyle Z_{k}}$ ist und ${\displaystyle p_{ij}>0}$ gilt, dann muss ${\displaystyle j\in Z_{k+1\operatorname {mod} d}}$ gelten. Die Zerlegungen können also nur in einer bestimmten Reihenfolge durchlaufen werden. Damit definiert die Zerlegung einen d-partiten Graph auf dem Übergangsgraph.

• Ist die Markow-Kette nicht irreduzibel, so kann man die Äquivalenzklasse aller mit ${\displaystyle i}$ kommunizierenden Zuständen betrachten. Diese lässt sich dann wie oben in disjunkte Teilmengen zerlegen, die wieder nur in eine Richtung durchlaufen werden können.
• Ist der Übergangsgraph bipartit und zusammenhängend, so ist die Markow-Kette periodisch mit gerader Periode. Ist er nicht zusammenhängend, so hat immerhin jeder Zustand gerade Periode. Allgemeinere Aussagen mit k-partiten Graphen gelten aber im Allgemeinen nicht.

Beispiel

Endlicher Zustandsraum

Betrachten wir als Beispiel eine Markow-Kette auf dem Zustandsraum ${\displaystyle Z=\{1,2,3,4\}}$ und mit Übergangsmatrix

${\displaystyle M={\begin{pmatrix}0&1&0&0\\0&0&1&0\\0&0{,}5&0&0{,}5\\1&0&0&0\\\end{pmatrix}}}$ .

Da die ${\displaystyle n}$ -Schritt-Übergangswahrscheinlichkeiten genau die Diagonaleinträge der ${\displaystyle n}$ -ten Potenz der Übergangsmatrix sind, überprüft man diese auf Positivität. Es gilt

${\displaystyle M^{2}=0{,}5\cdot {\begin{pmatrix}0&0&2&0\\0&1&0&1\\1&0&1&0\\0&2&0&0\\\end{pmatrix}},\quad M^{3}=0{,}25\cdot {\begin{pmatrix}0&2&0&2\\2&0&2&0\\0&3&0&1\\0&0&4&0\\\end{pmatrix}},\quad M^{4}=0{,}25\cdot {\begin{pmatrix}2&0&2&0\\0&3&0&1\\1&0&3&0\\0&2&0&2\\\end{pmatrix}}.}$

Das schachbrettartige Muster von ${\displaystyle M^{4}}$ bleibt bei allen höheren Potenzen erhalten, nur die Null- und die Nichtnulleinträge alternieren. Damit bekommen wir ${\displaystyle N_{1}=\{4,6,8,\dotsc \}}$ , und die Periode des Zustandes 1 ist zwei. Da alle Zustände miteinander kommunizieren, ist damit die Periode der Markow-Kette auch zwei. Die disjunkte Zerlegung des Zustandsraumes ist ${\displaystyle Z_{0}=\{1,3\}}$ und ${\displaystyle Z_{1}=\{2,4\}}$ .

Abzählbarer Zustandsraum

Betrachten wir als Beispiel eine homogene Markow-Kette auf dem Zustandsraum ${\displaystyle \mathbb {Z} }$ mit Übergangswahrscheinlichkeiten

${\displaystyle P(X_{n}=k|X_{n-1}=l):={\begin{cases}1/2&{\text{falls }}\quad k=l+1\\1/2&{\text{falls }}\quad k=l-1\\0&\quad \quad \quad {\text{sonst}}\end{cases}}}$ .

Dies lässt sich mit einem Betrunkenen vergleichen, der entweder nach links oder nach rechts taumelt, dies aber immer mit derselben Wahrscheinlichkeit (siehe Drunkard’s Walk). Dann ist für den Zustand 0 ${\displaystyle N_{0}=2\mathbb {N} }$ und damit dann auch ${\displaystyle d(0)=2}$ , da eine Rückkehr zum Ursprung immer nur zu geraden Zeitpunkten möglich ist. Dasselbe Ergebnis gilt auch für alle anderen Zustände, damit ist die Markow-Kette periodisch. Würde an einem beliebigen Zustand ${\displaystyle l}$ der Kette eine kleine Wahrscheinlichkeit eingeführt, in demselben Zustand zu verharren, so wäre die Markow-Kette nicht mehr periodisch, da z. B. ${\displaystyle N_{0}=2\mathbb {N} \cup \{2l+1+\mathbb {N} \}}$ gilt. Ab dem ${\displaystyle 2l+1}$ -ten Zeitschritt sind dann also beliebige Rückkehrzeiten möglich.

Ein Beispiel für e​ine periodische Markow-Kette m​it endlichem Zustandsraum i​st das Ehrenfest-Modell.

Literatur

• Ulrich Krengel: Einführung in die Wahrscheinlichkeitstheorie und Statistik. 8. Auflage, Vieweg, 2005. ISBN 978-3-834-80063-3
• Hans-Otto Georgii: Stochastik: Einführung in die Wahrscheinlichkeitstheorie und Statistik, 4. Auflage, de Gruyter, 2009. ISBN 978-3-110-21526-7
• Christian Hesse: Angewandte Wahrscheinlichkeitstheorie: eine fundierte Einführung mit über 500 realitätsnahen Beispielen und Aufgaben, Vieweg, Braunschweig/Wiesbaden 2003, ISBN 978-3-528-03183-1.