Lineare Algebra · Markow-Kette

Markow-Kette

Eine Markow-Kette wechselt zufällig den Zustand. Die Wahrscheinlichkeiten für den nächsten Zustand hängen nur vom aktuellen ab. Mit der Übergangsmatrix P ergibt die heutige Verteilung mal P die morgige. Bei wiederholter Anwendung entsteht oft eine stationäre Verteilung π mit πP = π, ein linker Eigenvektor zum Eigenwert 1.

Markow-Kette in dieser Darstellung

In einer Markow-Kette hängen die Wahrscheinlichkeiten des nächsten Zustands nur vom aktuellen ab. Hier gibt es Sonne, Wolken und Regen. Zeile ii der Übergangsmatrix PP enthält die Wahrscheinlichkeiten für morgen, wenn heute Zustand ii gilt. Jede Zeile ist ein Wahrscheinlichkeitsvektor. Aus dem heutigen Zeilenvektor pp wird morgen pPpP und nach nn Tagen pn=p0Pnp_n = p_0 P^n. Bei drei Zuständen liegt jede Verteilung in einem Dreieck. An einer Ecke ist ein Zustand sicher, die drei Wahrscheinlichkeiten sind die Gewichte der Ecken. Die dunklen Punkte sind die Zeilen von PP, Blau ist der Start, Rot verbindet p0,p1,p2,…p_0, p_1, p_2, \dots.

Was ein Schritt bewirkt

Ein Schritt bildet jede Ecke auf die entsprechende Zeile ab. Auf sichere Sonne folgt die Verteilung der ersten Zeile. Jede andere Verteilung pp ist ein gewichtetes Mittel der Ecken. Also ist pPpP das entsprechend gewichtete Mittel der Zeilen. Das Dreieck wird auf das von den Zeilen aufgespannte kleinere Dreieck abgebildet, nach zwei Schritten auf das der Zeilen von P2P^2. Hat eine Potenz von PP nur positive Einträge, ziehen sich die verschachtelten Dreiecke auf einen Punkt zusammen: die stationäre Verteilung π\pi.

Warum π ein Eigenvektor ist und wie schnell pₙ dorthin gelangt

Der Fixpunkt erfüllt πP=π\pi P = \pi. Somit ist π\pi ein Eigenvektor zum Eigenwert 1, genauer ein linker Eigenvektor (in Spaltenschreibweise PTπT=πTP^{\mathsf T}\pi^{\mathsf T} = \pi^{\mathsf T}). Die Einträge der Differenz p0−πp_0 - \pi summieren sich zu 0. Auf diesem Unterraum hat PP die beiden übrigen Eigenwerte λ2,λ3\lambda_2, \lambda_3. In jeder Eigenrichtung skaliert ein Schritt mit dem zugehörigen Eigenwert. Liegen beide Beträge unter 1, konvergiert pnp_n gegen π\pi. Der größere Betrag ∣λ2∣|\lambda_2| bestimmt die maßgebliche Rate. Bei der Wetterkette gilt ∣λ2∣≈0.462|\lambda_2| \approx 0.462. Für große nn bleibt je Schritt knapp die Hälfte des Abstands, sofern der Start einen Anteil in der Richtung zu λ2\lambda_2 hat. Komplexe Eigenwerte bewirken zusätzlich eine Drehung.

Wann die Verteilung nicht konvergiert

Im Zyklus folgen Sonne, Wolken und Regen immer aufeinander. Die beiden übrigen Eigenwerte haben Betrag 1. Außer beim Start in π\pi kreist pnp_n unbegrenzt. Bei zwei Fallen sind Sonne und Regen absorbierend. Der Eigenwert 1 ist doppelt, jede Mischung aus Sonne und Regen bleibt fest. So konvergiert pnp_n, doch der Grenzwert hängt vom Start ab. Für eine endliche Kette konvergiert pnp_n von jedem Start gegen dasselbe π\pi genau dann, wenn es genau eine abgeschlossene Klasse gibt und diese aperiodisch ist. Innerhalb einer solchen Klasse sind alle Zustände gegenseitig erreichbar und man kann sie nicht verlassen. Eine hinreichende Bedingung ist, dass eine Potenz PmP^m ausschließlich positive Einträge hat.

Worauf du achten kannst

  • In der Wetterkette beschreibt die stationäre Verteilung die Wetterwahrscheinlichkeiten für einen fernen Tag, unabhängig vom Start. Das Wetter selbst wechselt weiterhin.
  • Bei mehr als drei Zuständen bilden die Verteilungen ein höherdimensionales Gegenstück zum Dreieck, einen Simplex. Das Argument bleibt dasselbe.

Bedienung

  • Zieh einen dunklen Punkt, um eine Matrixzeile zu ändern, oder den blauen für den Start. Die Pfeiltasten verschieben den fokussierten Punkt um ein Hundertstel.

Verwandte Themen