Markow-Ketten

Der russische Mathematiker Andrei Markow suchte den Streit — mit der orthodoxen Kirche, mit der zaristischen Regierung; dafür war er berühmt. 1906 legte er sich mit etwas anderem an: mit einer Grundannahme seines eigenen Fachs. Die Wahrscheinlichkeitstheorie rechnete damals fast durchweg mit Unabhängigkeit — ein Versuch weiß nichts vom vorigen, wie beim wiederholten Münzwurf. Markow wollte zeigen, dass das Gesetz der großen Zahlen auch ohne diese Annahme steht, und lockerte sie an genau der richtigen Stelle: Jeder Versuch darf von seinem unmittelbaren Vorgänger abhängen, von nichts davor. Die Anwendung, für die man ihn heute vor allem kennt, folgte 1913: Er zählte in Puschkins Eugen Onegin aus, wie Vokale und Konsonanten einander abwechseln — und die Rechnung für abhängige Versuche hielt. Die Struktur, auf die er dabei gestoßen war, heißt heute Markow-Kette, und sie beschreibt verblüffend viele Prozesse in Natur und Rechenmaschine.

Eine Markow-Kette ist eine Folge von Zufallsvariablen X₁, X₂, X₃, … mit Werten in einem Zustandsraum S, für die die Markow-Eigenschaft gilt: Wohin es als Nächstes geht, entscheidet allein der gegenwärtige Zustand, nicht die Vorgeschichte. Formal: P(X_{n+1} = j | X_n = i, X_{n−1}, X_{n−2}, …) = P(X_{n+1} = j | X_n = i). Eine endliche Kette ist vollständig beschrieben, sobald ihre Übergangsmatrix P vorliegt; der Eintrag P_ij ist die Wahrscheinlichkeit, von Zustand i nach Zustand j zu wechseln. Weil sich jede Zeile von P zu 1 summiert, heißt P eine stochastische Matrix. Die Verteilung nach n Schritten liefert wiederholtes Multiplizieren, π_n = π₀·Pⁿ — über das Langzeitverhalten einer Markow-Kette entscheiden also die Potenzen von P, und damit ihre Eigenwerte. Unter milden Bedingungen — Irreduzibilität (jeder Zustand ist von jedem aus erreichbar) und Aperiodizität — gibt es genau eine stationäre Verteilung π mit πP = π, den Linkseigenvektor von P zum Eigenwert 1; von welcher Anfangsverteilung aus man auch startet, für n → ∞ landet man bei π. Wie schnell, das legt der zweitgrößte Eigenwert von P fest. Verallgemeinert worden ist in alle Richtungen: Markow-Prozesse in stetiger Zeit; Markow-Entscheidungsprozesse — Ketten samt Handlungen und Belohnungen, das Fundament des Reinforcement Learning; Hidden-Markow-Modelle, deren Zustände verborgen bleiben und sich nur in probabilistisch gekoppelten Ausgaben zeigen; Markow-Zufallsfelder, die die Kette auf Graphen übertragen.