Rekurrente Markow-Kette

Die Rekurrenz und der damit eng verbundene Begriff der Transienz bilden die Basis für die Untersuchung des Langzeitverhaltens von Markow-Ketten. Hierbei wird insbesondere die Frage untersucht, wie oft eine Markow-Kette wieder zu ihrem Startzustand zurückkehrt. Tut sie dies unendlich oft, so heißt sie rekurrent, ansonsten transient. Rekurrenz ist wichtig für die Existenz einer stationären Verteilung und der Konvergenz gegen diese. Teilweise ist sie auch von eigenständigem Interesse, wie z. B. bei Irrfahrten.

Ein wichtiges Hilfsmittel zur Untersuchung der Rekurrenz ist die Green-Funktion.

Definition

Gegeben sei eine homogene Markow-Kette Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (X_n)_{n \in \N_0}} in diskreter Zeit und mit abzählbarem Zustandsraum $Z$. Dann ist

$\tau _{ij}=\min\{n\geq 1\quad |\quad X_{n}=j\,\,\,\land \,\,\,X_{0}=i\}$

die Wartezeit bei Start in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i } bis zum erstmaligen Erreichen von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j} (ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i=j } spricht man von der Wiederkehrzeit). Sei nun

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tilde p_{ij}^n:=P(\tau_{ij}=n) }

die Ersteintrittswahrscheinlichkeit in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j} , also die Wahrscheinlichkeit bei einem Start im Zustand Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} nach genau Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Schritten zum ersten Mal in den Zustand $j$ zu gelangen. Ein Zustand Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i } heißt rekurrent, wenn

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tilde p_{i}:=P(\tau_{ii}< \infty)=\sum_{n=1}^\infty \tilde p_{ii}^n=1 }

gilt, der Zustand also fast sicher wieder besucht wird. Ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tilde p_i <1 } , so heißt der Zustand transient. Ist der Zustand rekurrent, und gilt für die erwartete Wiederkehrzeit

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{E}(\tau_{ii})=\sum_{n=1}^\infty n\tilde p_{ii}^n < \infty } ,

so heißt der Zustand positiv rekurrent. Ist der Erwartungswert unendlich, so heißt der Zustand null-rekurrent. Eine Markow-Kette heißt rekurrent (transient), falls jeder Zustand rekurrent (transient) ist.

Eigenschaften

• Sind Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i } und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j } miteinander kommunizierende Zustände, so gilt: Ist $i$ transient, so ist auch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j } transient. Dasselbe gilt auch für null-rekurrente und positiv-rekurrente Zustände.
• Transiente Zustände werden fast sicher nur endlich oft wieder besucht, rekurrente Zustände werden fast sicher unendlich oft wieder besucht.
• Für die erwartete Anzahl der Besuche eines Zustandes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i } bei Start in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i } gilt

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G(i,i):=\operatorname{E}\left( \sum_{n=1}^{\infty}\mathbf{1}_{X_n=i}\right) = \sum_{n=1}^{\infty}\operatorname{E}(\mathbf{1}_{X_n=i})=\sum_{n=1}^{\infty}p^n_{ii}} .

Hierbei bezeichnet Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p^n_{ii} } die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -Schritt-Übergangswahrscheinlichkeit, also die Wahrscheinlichkeit, im $n$-ten Schritt im Zustand Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} zu sein. Damit folgt: Die Transienz eines Zustandes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i } ist äquivalent zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G(i,i) < \infty} , die Rekurrenz ist äquivalent zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G(i,i) = \infty} . Dies erleichtert oftmals die Bestimmung von Rekurrenz und Transienz, da nur Abschätzungen benötigt werden und auch die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -Schritt-Übergangswahrscheinlichkeiten meistens leichter zu bestimmen sind als die Ersteintrittswahrscheinlichkeiten.

• Bei einer irreduziblen Markow-Kette sind Existenz einer stationären Verteilung und die positive Rekurrenz äquivalent. Des Weiteren gilt dann Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{E}(\tau_{ii})= \frac{1}{P_\pi(\{i\})} } wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P_\pi } die stationäre Verteilung ist.
• Im Falle eines endlichen Zustandsraumes folgt aus Irreduzibilität bereits positive Rekurrenz. Etwas abgeschwächt folgt, dass jeder wesentliche Zustand positiv rekurrent ist.
• Bei höchstens abzählbarem Zustandsraum ist jeder rekurrente Zustand wesentlich.

Beispiele

Endlicher Zustandsraum

Betrachte eine homogene Markow-Kette auf dem Zustandsraum Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \{1,2,3,4 \} } mit der Übergangsmatrix

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P= \begin{bmatrix} 0 & 0{,}5 & 0{,}5 & 0 \\ 0{,}5 & 0 & 0{,}5 & 0\\ 0{,}4 & 0{,}4 & 0 & 0{,}2\\ 0 & 0 & 0 & 1 \end{bmatrix}} .

Die Zustände 1, 2 und 3 bilden einen Kreis, der nur vom Zustand 3 aus mit Wahrscheinlichkeit 0,2 verlassen wird. Ist der Zustand 4 einmal erreicht, so kann er nicht wieder verlassen werden. 4 ist also ein absorbierender Zustand. Untersuchen wir nun Zustand 1 auf Rekurrenz oder Transienz. Da 1 keine Schleife besitzt, ist die Wiedereintrittszeit mindestens 2, mögliche Wege sind dabei 1-2-1 und 1-3-1 jeweils mit Wahrscheinlichkeiten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0{,}5 \cdot 0{,}5=0{,}25} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0{,}5 \cdot 0{,}4=0{,}2} . Daher ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tilde p_1^2=0{,}25+0{,}2=0{,}45 } . Ist der Zeitschritt gerade, so hilft folgende Überlegung: Beim Start in 1 braucht man einen Zeitschritt, um 2 oder 3 zu erreichen. Um nun weder zu früh wieder bei 1 anzukommen noch in 4 gefangen zu werden, müssen nun Runden zwischen 2 und 3 gelaufen werden bis einen Zeitschritt vor Wiedereintrittstzeit und dann erst wird zum Zustand zurückgekehrt. Damit folgt

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tilde p_1^{2n} = \frac{1}{4} \cdot \left(\frac{2}{10}\right)^{n-1}+ \frac{2}{10}\cdot \left(\frac{2}{10}\right)^{n-1}= \frac{9}{20}\cdot \left(\frac{1}{5}\right)^{n-1} } .

Analoge Überlegungen (mit dem Unterschied, dass hier halbe Runden gelaufen werden) ergeben für ungerade Wiedereintrittszeiten

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tilde p_1^{2n+1}= \frac{2}{10}\cdot \frac{1}{2} \cdot \left(\frac{2}{10}\right)^{n-1} + \frac{1}{4}\cdot \frac{2}{5}\cdot \left(\frac{2}{10}\right)^{n-1}= \left( \frac{1}{5}\right)^n } .

Mit der geometrischen Reihe folgt dann, dass

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tilde p_{i}=\sum_{n=1}^\infty \tilde p_{ij}^{2n} \quad + \quad \sum_{n=1}^\infty \tilde p_{ij}^{2n-1} \quad = \frac{13}{16}}

gilt, der Zustand 1 ist also transient. Daraus folgt, dass die Zustände 2 und 3 auch transient sind. Zustand 4 ist rekurrent, da er nicht mehr verlassen werden kann.

Abzählbar unendlicher Zustandsraum

Betrachten wir als Beispiel eine homogene Markow-Kette auf dem Zustandsraum Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{Z} } mit Übergangswahrscheinlichkeiten

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P(X_n=k | X_{n-1}=l):= \begin{cases} p & \text{falls } k = l+1 \\ q & \text{falls } k = l-1 \\ 0 & \text{sonst} \end{cases}}

mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p+q=1 } . Dies ist der Random Walk auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{Z} } . Es ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_{00}^{2n+1}:=0 } , da die Markow-Kette Periode zwei hat und sich daher bei Start im Nullpunkt zu einem ungeraden Zeitpunkt immer in einem ungeraden Zustand befindet. Da die Anzahl der Schritte binomialverteilt ist (siehe Random Walk), gilt

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_{00}^{2n}= \binom{2n}{n}p^nq^n \sim \frac{(4pq)^n}{\sqrt{\pi n}} }

nach der Stirlingformel. Damit gilt

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B_0 \sim \sum_{n=1}^\infty \frac{(4pq)^n}{\sqrt{\pi n}}= \begin{cases} \infty & \text{falls } p=q=\frac{1}{2} \\ < \infty & \text{sonst} \end{cases}} .

Ist die Irrfahrt also symmetrisch, so ist die Markow-Kette rekurrent, ansonsten ist sie transient.

Literatur

• Ulrich Krengel: Einführung in die Wahrscheinlichkeitstheorie und Statistik. 8. Auflage, Vieweg, 2005. ISBN 3-8348-0063-5.
• 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 3-528-03183-2.