www.wikidata.de-de.nina.az

Rekurrente Markow Kette Die Rekurrenz und der damit eng verbundene Begriff der Transienz bilden die Basis für die Unters

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 Bearbeiten

Gegeben sei eine homogene Markow-Kette in diskreter Zeit und mit abzählbarem Zustandsraum . Dann ist

die Wartezeit bei Start in bis zum erstmaligen Erreichen von (ist spricht man von der Wiederkehrzeit). Sei nun

die Ersteintrittswahrscheinlichkeit in , also die Wahrscheinlichkeit bei einem Start im Zustand nach genau Schritten zum ersten Mal in den Zustand zu gelangen. Ein Zustand heißt rekurrent, wenn

gilt, der Zustand also fast sicher wieder besucht wird. Ist , so heißt der Zustand transient. Ist der Zustand rekurrent, und gilt für die erwartete Wiederkehrzeit

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 Bearbeiten

  • Sind und miteinander kommunizierende Zustände, so gilt: Ist transient, so ist auch 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 bei Start in gilt
  • Bei einer irreduziblen Markow-Kette sind Existenz einer stationären Verteilung und die positive Rekurrenz äquivalent. Des Weiteren gilt dann wobei 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 Bearbeiten

Endlicher Zustandsraum Bearbeiten

Betrachte eine homogene Markow-Kette auf dem Zustandsraum mit der Übergangsmatrix

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 und . Daher ist . 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

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

Mit der geometrischen Reihe folgt dann, dass

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 Bearbeiten

Betrachten wir als Beispiel eine homogene Markow-Kette auf dem Zustandsraum mit Übergangswahrscheinlichkeiten

mit . Dies ist der Random Walk auf . Es ist , 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

nach der Stirlingformel. Damit gilt

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

Literatur Bearbeiten

  • 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.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Die Rekurrenz und der damit eng verbundene Begriff der Transienz bilden die Basis fur die Untersuchung des Langzeitverhaltens von Markow Ketten Hierbei wird insbesondere die Frage untersucht wie oft eine Markow Kette wieder zu ihrem Startzustand zuruckkehrt Tut sie dies unendlich oft so heisst sie rekurrent ansonsten transient Rekurrenz ist wichtig fur die Existenz einer stationaren Verteilung und der Konvergenz gegen diese Teilweise ist sie auch von eigenstandigem Interesse wie z B bei Irrfahrten Ein wichtiges Hilfsmittel zur Untersuchung der Rekurrenz ist die Green Funktion Inhaltsverzeichnis 1 Definition 2 Eigenschaften 3 Beispiele 3 1 Endlicher Zustandsraum 3 2 Abzahlbar unendlicher Zustandsraum 4 LiteraturDefinition BearbeitenGegeben sei eine homogene Markow Kette X n n N 0 displaystyle X n n in mathbb N 0 nbsp in diskreter Zeit und mit abzahlbarem Zustandsraum Z displaystyle Z nbsp Dann ist t i j min n 1 X n j X 0 i displaystyle tau ij min n geq 1 quad quad X n j land X 0 i nbsp die Wartezeit bei Start in i displaystyle i nbsp bis zum erstmaligen Erreichen von j displaystyle j nbsp ist i j displaystyle i j nbsp spricht man von der Wiederkehrzeit Sei nun p i j n P t i j n displaystyle tilde p ij n P tau ij n nbsp die Ersteintrittswahrscheinlichkeit in j displaystyle j nbsp also die Wahrscheinlichkeit bei einem Start im Zustand i displaystyle i nbsp nach genau n displaystyle n nbsp Schritten zum ersten Mal in den Zustand j displaystyle j nbsp zu gelangen Ein Zustand i displaystyle i nbsp heisst rekurrent wenn p i P t i i lt n 1 p i i n 1 displaystyle tilde p i P tau ii lt infty sum n 1 infty tilde p ii n 1 nbsp gilt der Zustand also fast sicher wieder besucht wird Ist p i lt 1 displaystyle tilde p i lt 1 nbsp so heisst der Zustand transient Ist der Zustand rekurrent und gilt fur die erwartete Wiederkehrzeit E t i i n 1 n p i i n lt displaystyle operatorname E tau ii sum n 1 infty n tilde p ii n lt infty nbsp so heisst der Zustand positiv rekurrent Ist der Erwartungswert unendlich so heisst der Zustand null rekurrent Eine Markow Kette heisst rekurrent transient falls jeder Zustand rekurrent transient ist Eigenschaften BearbeitenSind i displaystyle i nbsp und j displaystyle j nbsp miteinander kommunizierende Zustande so gilt Ist i displaystyle i nbsp transient so ist auch j displaystyle j nbsp transient Dasselbe gilt auch fur null rekurrente und positiv rekurrente Zustande Transiente Zustande werden fast sicher nur endlich oft wieder besucht rekurrente Zustande werden fast sicher unendlich oft wieder besucht Fur die erwartete Anzahl der Besuche eines Zustandes i displaystyle i nbsp bei Start in i displaystyle i nbsp giltG i i E n 1 1 X n i n 1 E 1 X n i n 1 p i i n 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 ii n nbsp Hierbei bezeichnet p i i n displaystyle p ii n nbsp die n displaystyle n nbsp Schritt Ubergangswahrscheinlichkeit also die Wahrscheinlichkeit im n displaystyle n nbsp ten Schritt im Zustand i displaystyle i nbsp zu sein Damit folgt Die Transienz eines Zustandes i displaystyle i nbsp ist aquivalent zu G i i lt displaystyle G i i lt infty nbsp die Rekurrenz ist aquivalent zu G i i displaystyle G i i infty nbsp Dies erleichtert oftmals die Bestimmung von Rekurrenz und Transienz da nur Abschatzungen benotigt werden und auch die n displaystyle n nbsp Schritt Ubergangswahrscheinlichkeiten meistens leichter zu bestimmen sind als die Ersteintrittswahrscheinlichkeiten Bei einer irreduziblen Markow Kette sind Existenz einer stationaren Verteilung und die positive Rekurrenz aquivalent Des Weiteren gilt dann E t i i 1 P p i displaystyle operatorname E tau ii frac 1 P pi i nbsp wobei P p displaystyle P pi nbsp die stationare Verteilung ist Im Falle eines endlichen Zustandsraumes folgt aus Irreduzibilitat bereits positive Rekurrenz Etwas abgeschwacht folgt dass jeder wesentliche Zustand positiv rekurrent ist Bei hochstens abzahlbarem Zustandsraum ist jeder rekurrente Zustand wesentlich Beispiele BearbeitenEndlicher Zustandsraum Bearbeiten Betrachte eine homogene Markow Kette auf dem Zustandsraum 1 2 3 4 displaystyle 1 2 3 4 nbsp mit der Ubergangsmatrix P 0 0 5 0 5 0 0 5 0 0 5 0 0 4 0 4 0 0 2 0 0 0 1 displaystyle P begin bmatrix 0 amp 0 5 amp 0 5 amp 0 0 5 amp 0 amp 0 5 amp 0 0 4 amp 0 4 amp 0 amp 0 2 0 amp 0 amp 0 amp 1 end bmatrix nbsp Die Zustande 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 mogliche Wege sind dabei 1 2 1 und 1 3 1 jeweils mit Wahrscheinlichkeiten 0 5 0 5 0 25 displaystyle 0 5 cdot 0 5 0 25 nbsp und 0 5 0 4 0 2 displaystyle 0 5 cdot 0 4 0 2 nbsp Daher ist p 1 2 0 25 0 2 0 45 displaystyle tilde p 1 2 0 25 0 2 0 45 nbsp Ist der Zeitschritt gerade so hilft folgende Uberlegung Beim Start in 1 braucht man einen Zeitschritt um 2 oder 3 zu erreichen Um nun weder zu fruh wieder bei 1 anzukommen noch in 4 gefangen zu werden mussen nun Runden zwischen 2 und 3 gelaufen werden bis einen Zeitschritt vor Wiedereintrittstzeit und dann erst wird zum Zustand zuruckgekehrt Damit folgt p 1 2 n 1 4 2 10 n 1 2 10 2 10 n 1 9 20 1 5 n 1 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 nbsp Analoge Uberlegungen mit dem Unterschied dass hier halbe Runden gelaufen werden ergeben fur ungerade Wiedereintrittszeiten p 1 2 n 1 2 10 1 2 2 10 n 1 1 4 2 5 2 10 n 1 1 5 n 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 nbsp Mit der geometrischen Reihe folgt dann dass p i n 1 p i j 2 n n 1 p i j 2 n 1 13 16 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 nbsp gilt der Zustand 1 ist also transient Daraus folgt dass die Zustande 2 und 3 auch transient sind Zustand 4 ist rekurrent da er nicht mehr verlassen werden kann Abzahlbar unendlicher Zustandsraum Bearbeiten Betrachten wir als Beispiel eine homogene Markow Kette auf dem Zustandsraum Z displaystyle mathbb Z nbsp mit Ubergangswahrscheinlichkeiten P X n k X n 1 l p falls k l 1 q falls k l 1 0 sonst displaystyle P X n k X n 1 l begin cases p amp text falls k l 1 q amp text falls k l 1 0 amp text sonst end cases nbsp mit p q 1 displaystyle p q 1 nbsp Dies ist der Random Walk auf Z displaystyle mathbb Z nbsp Es ist p 00 2 n 1 0 displaystyle p 00 2n 1 0 nbsp 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 p 00 2 n 2 n n p n q n 4 p q n p n displaystyle p 00 2n binom 2n n p n q n sim frac 4pq n sqrt pi n nbsp nach der Stirlingformel Damit gilt B 0 n 1 4 p q n p n falls p q 1 2 lt sonst displaystyle B 0 sim sum n 1 infty frac 4pq n sqrt pi n begin cases infty amp text falls p q frac 1 2 lt infty amp text sonst end cases nbsp Ist die Irrfahrt also symmetrisch so ist die Markow Kette rekurrent ansonsten ist sie transient Literatur BearbeitenUlrich Krengel Einfuhrung in die Wahrscheinlichkeitstheorie und Statistik 8 Auflage Vieweg 2005 ISBN 3 8348 0063 5 Hans Otto Georgii Stochastik Einfuhrung in die Wahrscheinlichkeitstheorie und Statistik 4 Auflage de Gruyter 2009 ISBN 978 3 110 21526 7 Christian Hesse Angewandte Wahrscheinlichkeitstheorie Eine fundierte Einfuhrung mit uber 500 realitatsnahen Beispielen und Aufgaben Vieweg Braunschweig Wiesbaden 2003 ISBN 3 528 03183 2 Abgerufen von https de wikipedia org w index php title Rekurrente Markow Kette amp oldid 208318052