Über dieses Experiment
Eine Markow-Kette springt zufällig zwischen Zuständen hin und her, doch die Wahrscheinlichkeit jedes Sprungs hängt nur davon ab, wo sie sich gerade befindet, nicht davon, wie sie dorthin gelangt ist. Das Wetter morgen hängt vom Wetter heute ab, die nächste Seite eines Websurfers von der aktuellen und die nächste Form eines Moleküls von seiner gegenwärtigen Form. Unabhängig davon, wie die Kette startet: Eine gutartige Kette vergisst ihren Anfang und pendelt sich in einem stationären Zustand π ein. Ändere die Übergangswahrscheinlichkeiten, führe die Kette aus und beobachte, wie sowohl die langfristigen Häufigkeiten als auch die Verteilung pₙ gegen π konvergieren.
Lernziele
- Stelle die Übergangsmatrix einer Markow-Kette auf und prüfe, ob sich jede Zeile zu 1 summiert
- Berechne die Verteilung nach n Schritten als p₀Pⁿ
- Bestimme die stationäre Verteilung, indem du πP = π löst
- Setze die Konvergenzgeschwindigkeit in Beziehung zum zweitgrößten Eigenwert von P
- Erkenne Ketten, die nicht konvergieren, etwa periodische Ketten
Anleitung
- 1Drücke bei der Wetterkette auf „Ausführen“ und beobachte den Token. Drücke dann auf „1000 Schritte“. Wie nah liegen die Balken an den gestrichelten Linien?
- 2Ändere den Anfangszustand. Ändert sich der stationäre Zustand? Ändert sich der frühe Teil des oberen Diagramms?
- 3Überprüfe den stationären Zustand von Hand: Multipliziere π mit der Matrix und zeige, dass du wieder π erhältst.
- 4Wähle „Langsames Mischen“. Wie viele Schritte braucht das obere Diagramm, um sich einzupendeln? Vergleiche das mit |λ₂| und der Anzeige.
- 5Wähle „Periodischer Zyklus“. Warum pendelt sich das obere Diagramm nie ein, obwohl sich der Zeitanteil in jedem Zustand einpendelt?
- 6Wähle „Vergisst sofort“. Warum erreicht die Verteilung π bereits nach einem Schritt?
Das Modell
Annahmen
- Drei Zustände und zeitlich homogene Übergangswahrscheinlichkeiten. Jede Zeile wird mit zwei Schiebereglern bearbeitet; die Wahrscheinlichkeit, im selben Zustand zu bleiben, ergibt sich aus dem Rest.
- Der Stichprobenpfad stammt aus einem initialisierten Zufallszahlengenerator, sodass dieselbe Laufnummer immer denselben Pfad ergibt; „Neuer Lauf“ ändert den Startwert.
- Der stationäre Zustand wird durch exaktes Lösen der linearen Gleichungen ermittelt. Die Anzahl der Schritte, um bis auf 1 % heranzukommen, wird mit ln 100 / (-ln |λ₂|) geschätzt.
Im Unterricht ausprobieren
- Q1Bestimmen Sie für P = [[0.9, 0.1], [0.5, 0.5]] die stationäre Verteilung.
- Q2Zeigen Sie, dass die Gleichverteilung stationär ist, wenn auch jede Spalte von P die Summe 1 hat.
- Q3Eine Kette hat |λ₂| = 0.95. Wie viele Schritte braucht sie ungefähr, um ihren Anfangszustand zu vergessen?
- Q4Erklären Sie, warum die Kette mit periodischem Zyklus eine stationäre Verteilung hat, pₙ aber nicht gegen sie konvergiert.
- Q5Googles ursprünglicher PageRank ist die stationäre Verteilung eines zufälligen Surfers. Warum wurde eine kleine Wahrscheinlichkeit hinzugefügt, zu einer beliebigen Seite zu springen?
Häufig gestellte Fragen
Was bedeutet hier gedächtnislos?
Die Zukunft hängt von der Vergangenheit nur über den gegenwärtigen Zustand ab. Wenn Sie wissen, dass es heute regnet, erfahren Sie nichts Weiteres über morgen, wenn Sie zusätzlich wissen, dass es letzte Woche sonnig war.
Hat jede Kette einen stationären Zustand?
Jede endliche Markov-Kette hat mindestens eine stationäre Verteilung. Sie ist eindeutig, wenn jeder Zustand von jedem anderen aus erreichbar ist, und pₙ konvergiert von jedem Startzustand aus gegen sie, wenn die Kette zusätzlich nichtperiodisch ist.
Wo werden Markov-Ketten eingesetzt?
In Warteschlangen- und Zuverlässigkeitsmodellen, in der Genetik, Spracherkennung, Textvorhersage und Finanzwirtschaft sowie bei der Markov-Ketten-Monte-Carlo-Methode, die eine Kette erzeugt, deren stationäre Verteilung die Verteilung ist, aus der man Stichproben ziehen möchte.