Einstellungen
Aktionen
Anzeigeoptionen
Übergangsmatrix-Editor
Jede Zeile muss sich zu 1,0 summieren (stochastische Matrix)
Wahrscheinlichkeitsverteilung
Konvergenz zur Stationären Verteilung
Mathematische Analyse
Aktuelle Verteilung p_t
Stationäre Verteilung π
π erfüllt π = πP
Eigenwerte von P
λ₁ = 1 ist für stochastische Matrizen garantiert
Ketten-Eigenschaften
Mischzeit-Schätzung
Schritte um Abstand ε = 0,01 von π zu erreichen
Gesamtvariations-Abstand
δ(t) = 0.5 × Σ|p_t(i) - π(i)|
Was ist eine Markow-Kette?
Eine Markow-Kette ist ein stochastischer Prozess mit der Gedächtnislosigkeit-Eigenschaft: Der zukünftige Zustand hängt nur vom aktuellen Zustand ab, nicht von der Folge der vorangegangenen Ereignisse.
Markow-Eigenschaft
P(X_{t+1} | X_t, X_{t-1}, ..., X_0) = P(X_{t+1} | X_t)
Übergangsformel
p_{t+1} = p_t P
wobei p_t der Verteilungsvektor zum Zeitpunkt t ist und P die Übergangsmatrix
Wichtige Konzepte
- Zustandsraum S: Die Menge aller möglichen Zustände
- Übergangsmatrix P: P[i][j] = P(X_{t+1}=j | X_t=i)
- Stochastische Matrix: Jede Zeile summiert sich zu 1,0
- Pfadwahrscheinlichkeit: Produkt der Übergangswahrscheinlichkeiten entlang des Pfades
Stationäre Verteilung π
Eine stationäre Verteilung π ist eine Wahrscheinlichkeitsverteilung, die in der Markow-Kette unverändert bleibt: Sobald das System π erreicht, bleibt es dort für immer.
Stationäre Gleichung
π = πP
oder äquivalent: π(P - I) = 0
Linker Eigenvektor-Interpretation
π ist der linke Eigenvektor von P entsprechend dem Eigenwert 1
πP = λπ where λ = 1
Existenz und Eindeutigkeit
- Existenz: Jede endliche Markow-Kette hat mindestens eine stationäre Verteilung
- Eindeutigkeit: Garantiert für irreduzible Ketten (alle Zustände kommunizieren)
- Perron-Frobenius: Für reguläre Ketten hat π alle positiven Einträge
Gesamtvariations-Abstand
δ(t) = 0.5 × Σ|p_t(i) - π(i)|
Misst wie nah die aktuelle Verteilung an der stationären ist
Konvergenzeigenschaften
Unter welchen Bedingungen konvergiert eine Markow-Kette zu ihrer stationären Verteilung?
Kettentypen
- Regulär (Aperiodisch + Irreduzibel): Konvergiert zu eindeutigem π von jeder Anfangsverteilung
- Periodisch: Zustände zyklen durch ein periodisches Muster
- Reduzibel: Enthält absorbierende Zustände oder mehrere kommunizierende Klassen
Konvergenzrate
Bestimmt durch den zweitgrößten Eigenwertbetrag (SLEM):
|p_t - π| ≈ C × |λ_2|^t
Spektrallücke = 1 - |λ₂|, größere Lücke = schnellere Konvergenz
Mischzeit
Zeit um ε-nah an der stationären Verteilung zu sein:
t_mix(ε) = log(ε) / log(|λ_2|)
Periodizitätserkennung
Ein Zustand hat Periode d, wenn alle Zyklen von diesem Zustand Längen haben, die durch d teilbar sind
- Aperiodisch: d = 1 (kann jederzeit zurückkehren)
- Periodisch: d > 1 (Zyklen sind synchronisiert)
Detailliertes Gleichgewicht (Umkehrbare Ketten)
π(i)P(i,j) = π(j)P(j,i)
Eine hinreichende Bedingung für π stationär zu sein
Praktische Anwendungen
PageRank-Algorithmus
Googles PageRank modelliert Web-Surfen als Zufallswanderung. Die stationäre Verteilung gibt die Bedeutung jeder Seite an.
P = (1-d)M + d(1/n)J
M: Linkmatrix, d: Dämpfungsfaktor, J: Einsen-Matrix
Zufallswanderungen auf Graphen
Verwendet in Netzwerkanalyse, Empfehlungssystemen und Graph-Sampling. Die stationäre Verteilung bezieht sich auf Knotengrade.
MCMC-Samplingmethoden
Markow-Ketten-Monte-Carlo-Methoden generieren Stichproben aus komplexen Wahrscheinlichkeitsverteilungen durch Konstruktion von Ketten mit dem Ziel als stationäre Verteilung.
- Metropolis-Hastings algorithm
- Gibbs sampling
- Boltzmann machines
Versteckte Markow-Modelle (HMM)
Verwendet in Spracherkennung, Bioinformatik und Finanzen. HMMs haben eine zugrundeliegende Markow-Kette mit versteckten Zuständen.
Warteschlangentheorie
Geburts- und Todesprozesse modellieren Warteschlangen. Die stationäre Verteilung gibt die Langzeitwahrscheinlichkeit an, n Kunden im System zu haben.
Brettspiele
Spiele wie Monopoly und Schlangen und Leitern können als Markow-Ketten modelliert werden, um die erwartete Spieldauer und Besuchshäufigkeiten zu berechnen.