Diese Ausarbeitung, welche mit LaTeX geschrieben wurde, umfasst die Grundlagen für das differenzierte Verständnis über Markov-Ketten im Studium.
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.
[...]
- Quote paper
- Felix Busch (Author), 2019, Markov-Ketten Grundlagen, Munich, GRIN Verlag, https://www.grin.com/document/538580
