Markov-Ketten Grundlagen

Irreduzible und aperiodische Markov-Ketten


Ausarbeitung, 2019

6 Seiten, Note: 1,3


Leseprobe

Irreduzible und aperiodische Markov-Ketten

Felix Busch

29.10.2019

1 Irreduzible und aperiodische Markov-Ketten

1.1 Definition

Sei eine Markov Kette (Xo,Xi,...) mit Zustandsraum {s1,..., Sk} und Ujbergangsmatrix P gegeben. Man sagt, dass ein Zustand Si mit einem Zustand Sj kommuniziert, in Zeichen Si — Sj, genau dann, wenn die Markov- Kette positive Wahrscheinlichkeit besitzt, innerhalb einer Zeit n von Zustand si nach Zustand sj zu gelangen. Also, wenn ein n e N existiert, sodass:

Abbildung in dieser Leseprobe nicht enthalten

Weiterhin gilt: Zwei Zustande Si und Sj kommunizieren miteinander, in Zeichen Si Sj, genau dann, wenn

Abbildung in dieser Leseprobe nicht enthalten

Diese Definition ist unabhangig von der Wahl von m, wie das folgende Lemma zeigt:

1.2 Lemma

Sei eine Markov-Kette (X0,X1,...) mit Zustandsraum {s1, ..., Sk} und Ujbergangsmatrix P gegeben. Seien i,j e {1,k}. Dann gilt Vm, n e N:

P(Xm+n = Sj | Xm = Si) = (Pn)i,j . Das bedeutet, dies ist unabhängig von m.

Beweis.

Sei m fest aber beliebig. Beweise die Behauptung durch Induktion uäber n:

Abbildung in dieser Leseprobe nicht enthalten

* bedeutet: Die Wahrscheinlichkeit eines gegebenen Weges durch den jäbergangsgraph mit gegebenen Zeiten ist gleich dem Produkt der einzelnen Wege mit den entsprechenden Zeiten und folgt direkt aus der Gedaächtnislosigkeit der Markov-Kette. Denn P(Xm+n+1 = Sj | Xm = Sq), wuärde nicht den vorherigen Zustand betrachten, sondern einen Zustand der schon n Schritte zuvor durchlaufen wurde. Da es väollig egal ist an welchem Punkt wir n Schritte zuvor gewesen sind, sondern nur der unmittelbare jäbergang von einem Zustand Si in einen Zustand Si+1 von Bedeutung ist, kann man sagen, dass diese Gleichheit gilt. Dies beschreibt die Haupteigenschaft der Markov-Ketten, die Gedachtnislosigkeit.

1.3 Definition

Eine Markov-Kette (X0, Xi,...) mit Zustandsraum {s1,..., sk} und Übergangsmatrix P heißt irreduzibel genau dann, wenn für alle i,j e {s1,..., sk} gilt, dass si Sj. Ansonsten heißt die Markov-Kette reduzibel. Eine äquivalente Formulierung fur Irreduzibilitat ist, dass fi'ir alle i, j e {1,..., k} ein n e N mit (P n ) i ,j > 0 existiert.

1.4 Beispiel

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: reduzible Markov-Ketten,Quelle: Schomaker, J.

Man sieht in diesem Beispiel die Rechtfertigung fuär den Begriff ”reduzibel”, da man sich auf eine kleinere Markov-Kette und damit auf eine entsprechend angepasste Üä bergangsmatrix konzentrieren kann. Wenn man im linken Beispiel die Markov-Ketten als zwei einzelne betrachten wuärde, dann haätte man zwei irreduzible Markov-Ketten.

1.5 Definition

SeieineMarkov-Kette(X0,X1,...)mitZustandsraum{s1,...,sk} und Üäbergangsmatrix P gegeben. Die Periode d(si) eines Zustandes si definiert man als:

Abbildung in dieser Leseprobe nicht enthalten

In Worten: Die Periode von si ist der gräoßte gemeinsame Teiler der Menge von Zeiten, an denen die Markov- Kette wieder nach si (mit positiver Wahrscheinlichkeit) zuruäckkehren kann. Dabei bezeichnen wir mit si = X0 den Startpunkt der Markov-Kette.

1.6 Definition

SeieineMarkov-Kette(X0,X1,...)mitZustandsraum{s1,...,sk} und Üäbergangsmatrix P gegeben.

Ist d(si) = 1, so heißt der Zustand si aperiodisch (unregelmäaßige Ruäckkehrwahrscheinlichkeit), andernfalls heißt der Zustand periodisch. Falls alle Zustäande der Markov-Kette aperiodisch sind, so heißt auch die Markov- Kette aperiodisch. Andernfalls heißt sie periodisch.

1.7 Beispiel

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2: Periodische Markov-Kette,Quelle: Eigene Darstellung

Wir nehmen an, dass wir in Punkt s1 starten. Er muss also eine gerade Anzahl an Schritten nehmen, um zurück zu s1 zu kommen. Das heißt (P n ) i ,j > 0 nur für n= 2, 4, 6,... daraus folgt: ggT {n > 1 : (P n ) i ,j > 0} = ggT{2, 4, 6,...} = 2 und die Kette ist somit periodisch.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3: Aperiodische Markov-Kette,Quelle: Schomaker, J.

Man sieht hier, dass fur jeden Zustand si gilt, dass (P2)i,i > 0 und (P3)i,i > 0 ist. Damit gilt d(si) = 1 und diese Markov-Kette ist aperiodisch.

1.8 Lemma

Sei A = {a1,a2,a3,...} eine Menge positiver, naturlicher Zahlen mit folgenden Eigenschaften:

i) ggT(A) = 1
ii) A ist abgeschlossen unter Addition, d.h. wenn a,b e A gilt, dann gilt auch a + b e A. Dann existiert ein N < to so, dass n e A Vn > N.

Beweis.

Abbildung in dieser Leseprobe nicht enthalten

Wir werden dieses Lemma im Folgenden Satz benutzen, um zu zeigen, dass die Wahrscheinlichkeit von einem Zustand si in denselben zuruck zu gelangen, nachdem N Schritte durchlaufen wurden, ftir die weiteren n Schritte positiv ist.

[...]

Ende der Leseprobe aus 6 Seiten

Details

Titel
Markov-Ketten Grundlagen
Untertitel
Irreduzible und aperiodische Markov-Ketten
Hochschule
Friedrich-Schiller-Universität Jena  (Mathematik und Informatik)
Veranstaltung
Seminar 2 - Wahrscheinlichkeitstheorie
Note
1,3
Autor
Jahr
2019
Seiten
6
Katalognummer
V538580
ISBN (eBook)
9783346147745
Sprache
Deutsch
Schlagworte
Markov-Ketten, Periodisch, Aperiodisch, reduzibel, irreduzibel, Wahrscheinlichkeitstheorie
Arbeit zitieren
Felix Busch (Autor:in), 2019, Markov-Ketten Grundlagen, München, GRIN Verlag, https://www.grin.com/document/538580

Kommentare

  • Noch keine Kommentare.
Im eBook lesen
Titel: Markov-Ketten Grundlagen



Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden