Übergangsmatrizen und Markow-Ketten

Manche Prozesse hängen nur vom heutigen Zustand ab: Ist es heute sonnig, ist die Chance auf Sonne morgen hoch, ganz gleich, wie das Wetter vor einer Woche war. Solche Prozesse nennt man Markow-Ketten. Mit Matrizen lassen sie sich einfach berechnen. Du brauchst dazu das Multiplizieren von Matrizen und das Lösen von linearen Gleichungssystemen.

Zuerst kommt ein einfaches Beispiel mit zwei Zuständen, dann die Rechnung mit Matrix und Vektor, die stationäre Verteilung und ein Abiturbeispiel mit drei Zuständen. Zum Schluss geht es kurz um Populationsmodelle. Wahrscheinlichkeiten und Baumdiagramme werden vorausgesetzt, sie stehen bei der Wahrscheinlichkeitsrechnung.

Prozesse mit Zuständen

Ein Modell für das Wetter hat zwei Zustände: sonnig und regnerisch. Nach einer Reihe von Beobachtungen nimmt man an:

• Auf einen sonnigen Tag folgt mit 80 % wieder ein sonniger und mit 20 % ein regnerischer.
• Auf einen regnerischen Tag folgt mit 40 % ein sonniger und mit 60 % ein regnerischer.

Das sind die Übergangswahrscheinlichkeiten. Im Übergangsgraphen zeigt jeder Pfeil einen möglichen Wechsel, die Zahl am Pfeil ist die Wahrscheinlichkeit. Die Zahlen an den Pfeilen, die einen Zustand verlassen, ergeben zusammen 1.

Das Baumdiagramm zeigt, wie sich die Wahrscheinlichkeiten über zwei Tage zusammensetzen (Pfadregeln). Ist es heute sonnig, so ist es übermorgen sonnig über zwei Wege: sonnig, sonnig (0,8 · 0,8 = 0,64) oder regnerisch, sonnig (0,2 · 0,4 = 0,08). Zusammen sind das 0,72.

Diese Rechnung wird bei vielen Tagen schnell länglich. Mit einer Matrix geht es systematisch.

Die Übergangsmatrix

Schreibe die Wahrscheinlichkeiten in eine Matrix. In der ersten Zeile steht „nach sonnig“, in der zweiten „nach regnerisch“. Die erste Spalte gilt „von sonnig“, die zweite „von regnerisch“:

Jede Spalte ist eine Wahrscheinlichkeitsverteilung, sie hat die Summe 1. Eine Matrix mit nicht negativen Einträgen und Spaltensumme 1 heißt stochastische Matrix.

Der Zustandsvektor $v_n$ enthält die Anteile oder Wahrscheinlichkeiten der Zustände nach n Tagen. Startet man an einem sonnigen Tag, ist $v_0=\left(\begin{array}{c}1\\ 0\end{array}\right)$. Den nächsten Tag liefert die Multiplikation mit der Matrix:

Das passt zum Baumdiagramm: Übermorgen ist es mit 72 % sonnig.

Mehrere Schritte

Wendest du die Matrix n Mal an, erhältst du die n-te Potenz: $v_n=A^n·v_0$. Die Potenzen berechnest du mit dem Matrizenprodukt:

Die Spalten sind wieder Verteilungen. Die erste Spalte von $A^3$ sagt: Ist es heute sonnig, ist es in drei Tagen mit 68,8 % sonnig. Die zweite Spalte gehört zum Start „regnerisch“. Der Eintrag oben rechts, 0,624, ist die Wahrscheinlichkeit für „in drei Tagen sonnig, wenn es heute regnet“.

Langfristiges Verhalten: die stationäre Verteilung

Die Zahlen nähern sich offenbar einem festen Wert. Eine Verteilung v, die sich bei einem Schritt nicht mehr ändert, heißt stationär (oder Fixvektor):

Das ist ein lineares Gleichungssystem. Mit $v=\left(\begin{array}{c}s\\ r\end{array}\right)$ lautet $A·v=v$ ausgeschrieben:

Beide Gleichungen sind gleichwertig zu $\mathrm{0,2}s=\mathrm{0,4}r$, also $s=2r$. Mit $s+r=1$ folgt $3r=1$. Die stationäre Verteilung ist $s=2/3$ und $r=1/3$. Langfristig ist es an zwei Dritteln der Tage sonnig, unabhängig vom Startwert.

Der Grund steckt in den Eigenwerten. Die Gleichung $A·v=v$ sagt, dass v ein Eigenvektor zum Eigenwert 1 ist. Die Matrix hat den zweiten Eigenwert 0,4. Er bestimmt, wie schnell die Abweichung schrumpft: Der Abstand zu 2/3 wird bei jedem Schritt mit 0,4 multipliziert.

Nicht jede Kette nähert sich einer stationären Verteilung. Hilfreich ist diese Regel: Gibt es eine Potenz von A mit lauter positiven Einträgen, so gibt es genau eine stationäre Verteilung, und jede Startverteilung nähert sich ihr. Gegenbeispiele sind die Matrix, die zwei Zustände immer vertauscht (die Verteilung pendelt zwischen (1|0) und (0|1)), und Ketten mit einem Zustand, den man nie verlässt.

Populationsmodelle nach Leslie

Die gleiche Rechnung beschreibt Tierbestände nach Altersklassen. Die erste Zeile der Leslie-Matrix enthält die Fortpflanzungsraten, die Nebendiagonale die Überlebensanteile von einer Klasse zur nächsten. Patrick H. Leslie führte sie 1945 ein. Die Spaltensummen sind hier nicht 1, denn es werden Tiere geboren und sterben.

Der Bestand wächst nicht gleichmäßig, aber im Mittel um den Faktor $\lambda \approx \mathrm{1,088}$ pro Jahr. Das ist der größte Eigenwert von L, die Lösung von ${\lambda }^3-\lambda -\mathrm{0,2}=0$.

Abituraufgabe: Anbieterwechsel

So könnte eine Aufgabe im Abitur aussehen. Versuche sie zuerst selbst.

Typische Fehler

Übungen

Geschichte: Markow, Onegin und PageRank

Andrei Andrejewitsch Markow (1856 bis 1922) war Mathematiker in St. Petersburg und Schüler von Pafnuti Tschebyschow. Er wollte zeigen, dass das Gesetz der großen Zahlen auch gilt, wenn die Ergebnisse nicht unabhängig sind. Dazu untersuchte er Ketten von Zuständen, bei denen jeder Zustand nur vom vorigen abhängt. 1913 wandte er das auf die Buchstabenfolgen in Puschkins Versroman Eugen Onegin an.

Eine Matrix für Altersklassen führte Patrick H. Leslie 1945 in der Zeitschrift Biometrika ein. Heute stecken Markow-Ketten in vielen Anwendungen: in der Bewertung von Webseiten (PageRank, siehe PageRank), in der Warteschlangentheorie, in der Spracherkennung und in Versicherungsmodellen.

Häufige Fragen

Quellen und weiterführende Literatur

• Patrick H. Leslie: On the use of matrices in certain population mathematics. Biometrika, 1945.
• Wikipedia: Markow-Kette
• Wikipedia: Übergangsmatrix
• Wikipedia: Leslie-Matrix