Markov-Ketten-Gleichgewichtszustand-Rechner
Stationary Distribution · Gaussian Elimination · Power Iteration
Gib eine n×n Übergangsmatrix ein, um die Gleichgewichtsverteilung zu finden πP = π mittels Gaußscher Elimination. Enthält Potenziterationskonvergenz und Balkendiagramm.
Schnellbeispiele
Gleichgewichtszustand-Verifikation (πP = π)
Gleichgewichtsverteilungsdiagramm
Potenziteration Konvergenz
πk = π0 × Pk beginnend mit der Gleichverteilung. Zeigt Konvergenz bei k = 1, 2, 5, 10, 20, 50.
Führe zuerst den Rechner aus.
Gaussian Elimination — Augmented Matrix Schritte
Lösen von (PT − I)π = 0, letzte Gleichung ersetzt durch Σπᵢ = 1.
Führe zuerst den Rechner aus.
Was ist eine Markov-Kette?
Eine Markov-Kette ist ein stochastischer Prozess, der nach festen Übergangswahrscheinlichkeiten zwischen einer endlichen Menge von Zuständen wechselt. Die entscheidende Eigenschaft ist, dass der nächste Zustand nur vom aktuellen Zustand abhängt – nicht von der bisherigen Geschichte.
Formal wird eine zeitdiskrete Markov-Kette durch eine Übergangswahrscheinlichkeitsmatrix P definiert. Jede Zeile von P muss genau die Summe 1,0 ergeben, was P zu einer zeilenstochastischen Matrix macht.
Die Gleichgewichts-(stationäre) Verteilung
Die Gleichgewichtsverteilung (stationäre Verteilung) π = [π1, π2, …, πn] ist ein Wahrscheinlichkeitsvektor, der zwei Bedingungen erfüllt:
- Bilanzgleichung: πP = π — die Verteilung bleibt durch einen Schritt der Kette unverändert
- Normierung: Σπi = 1 — die Werte bilden eine gültige Wahrscheinlichkeitsverteilung
Intuitiv ist πi der langfristige Zeitanteil, den die Kette im Zustand i verbringt. Für ergodische Ketten konvergiert die Verteilung für k → ∞ unabhängig vom Anfangszustand gegen πj.
Wann existiert ein eindeutiger Gleichgewichtszustand?
Eine eindeutige stationäre Verteilung ist für ergodische Markov-Ketten garantiert:
- Irreduzibel: Jeder Zustand kann jeden anderen Zustand erreichen
- Aperiodisch: Kein Zustand hat einen erzwungenen periodischen Zyklus
Der Satz von Perron-Frobenius garantiert, dass eine positive stochastische Matrix immer eine eindeutige stationäre Verteilung besitzt.
Lösungsmethoden
Gaußsche Elimination
Schreibe πP = π als (PT − I)π = 0 um. Dies ist ein homogenes lineares System. Um eine eindeutige Lösung zu erhalten, ersetzen wir die letzte Gleichung durch die Normierungsbedingung Σπi = 1 und wenden die Gaußsche Elimination an.
Potenziteration
Beginne mit einer Gleichverteilung π0 und iteriere πk+1 = πkP bis zur Konvergenz.
Mittlere Rückkehrzeit
Für ergodische Ketten gibt die mittlere Rückkehrzeit μi = 1/πi die erwartete Anzahl von Schritten zwischen aufeinanderfolgenden Besuchen des Zustands i an. Zustände mit hoher stationärer Wahrscheinlichkeit haben kurze Rückkehrzeiten und umgekehrt.
Praxisanwendungen
- PageRank: Google modelliert das Web als Markov-Kette; die stationäre Verteilung ordnet Seiten nach Wichtigkeit
- Finanzen: Ratingagenturen modellieren Übergänge zwischen AAA, AA usw. als Markov-Kette
- Genetik: Hardy-Weinberg-Gleichgewicht und Allelfrequenzdrift können als Markov-Ketten modelliert werden
- Wettermodellierung: Vereinfachte Klimamuster erfasst als Übergangsmatrizen
- Warteschlangentheorie: Serverlast und Warteschlangenlängen werden berechnet
- NLP: Textgenerierung und Spracherkennung verwenden Markov-Modelle
Referenz: Wetterbeispiel (2×2)
| Von / Nach | Sonnig | Regnerisch |
|---|---|---|
| Sonnig | 0.8 | 0.2 |
| Regnerisch | 0.4 | 0.6 |
Gleichgewichtszustand: π = [2/3, 1/3] ≈ [0.6667, 0.3333]. Auf lange Sicht sind 66,7% der Tage sonnig, 33,3% regnerisch, unabhängig vom heutigen Wetter.