Markow-Ketten

Gedächtnislose Prozesse — die Zukunft hängt an der Gegenwart, nicht am Weg dorthin.

Als Nächstes empfohlen → Statistische Mechanik · PHYS · T5

Der Beitrag

Im Jahr 1906 veröffentlichte der russische Mathematiker Andrei Markov — schon bekannt für seine Reibereien mit der russisch-orthodoxen Kirche und der zaristischen Regierung — eine Arbeit, mit der er einen Streit ganz anderer Art aufnahm. Die Wahrscheinlichkeitstheorie setzte damals weithin Unabhängigkeit voraus: aufeinanderfolgende Versuche galten als zusammenhanglos, wie wiederholte Münzwürfe. Markov wollte das Gesetz der großen Zahlen ohne die Unabhängigkeitsannahme beweisen, und er fand die richtige Lockerung: lass jeden Versuch von dem unmittelbar vorhergehenden abhängen, von nichts weiter Zurückliegendem. Die Anwendung, für die man ihn am meisten kennt, kam einige Jahre später: 1913 zählte er den Wechsel von Vokalen und Konsonanten in Puschkins Eugen Onegin aus, und die Mechanik der abhängigen Versuche bewährte sich. Die Struktur, die er freilegte und die heute Markov-Kette heißt, beschreibt eine erstaunliche Bandbreite natürlicher und rechnerischer Prozesse.

Eine Markov-Kette ist eine Folge von Zufallsvariablen X₁, X₂, X₃, …, die Werte in einem Zustandsraum S annehmen, mit der Markov-Eigenschaft: die bedingte Verteilung des nächsten Zustands hängt nur vom aktuellen Zustand ab, nicht von der Vorgeschichte. Formal: P(X_{n+1} = j | X_n = i, X_{n−1}, X_{n−2}, …) = P(X_{n+1} = j | X_n = i). Die vollständige Beschreibung einer endlichen Markov-Kette steckt in ihrer Übergangsmatrix P, wobei P_ij die Wahrscheinlichkeit ist, von Zustand i nach Zustand j zu wechseln. Jede Zeile von P summiert sich zu 1 — es ist eine stochastische Matrix. Die Wahrscheinlichkeitsverteilung nach n Schritten folgt aus wiederholter Multiplikation: π_n = π₀·Pⁿ; das Langzeitverhalten einer Markov-Kette wird also von den Potenzen von P bestimmt — und damit von deren Eigenwerten. Unter milden Bedingungen — Irreduzibilität (jeder Zustand ist von jedem anderen erreichbar) und Aperiodizität — existiert eine eindeutige stationäre Verteilung π mit πP = π, der Linkseigenvektor von P zum Eigenwert 1, und jede Anfangsverteilung konvergiert gegen π, wenn n → ∞. Die Konvergenzrate setzt der zweitgrößte Eigenwert von P. Verallgemeinerungen reichen weit: Markov-Prozesse in kontinuierlicher Zeit, Markov-Entscheidungsprozesse (Markov-Ketten mit Handlungen und Belohnungen, das Fundament des Reinforcement Learning), Hidden-Markov-Modelle (Ketten, in denen die Zustände verborgen sind und nur probabilistisch verbundene Ausgaben beobachtet werden), Markov-Zufallsfelder (Ketten, übertragen auf Graphstrukturen).

Warum jetztPageRank — der Algorithmus, der Google begründete — modelliert das Surfen im Web als Markov-Kette auf dem Link-Graphen und sortiert Seiten nach der stationären Verteilung. MCMC (Markov Chain Monte Carlo) — Metropolis-Hastings, Gibbs-Sampling, der Hamilton- und der No-U-Turn-Sampler — ist das Zugpferd der heutigen bayesschen Inferenz, eingesetzt von der Kosmologie bis zur Wirkstoffentwicklung. Spracherkennung und Wortartentagging arbeiteten historisch mit Hidden-Markov-Modellen. Die Warteschlangentheorie im Operations Research ruht auf Markov-Ketten. Das Reinforcement Learning — jede Atari-spielende KI, AlphaGo, AlphaStar — operiert über Markov-Entscheidungsprozessen. Asset-Preis-Modelle der Finanzwelt arbeiten mit markovsch strukturiertem Rauschen. Die kleine Strukturannahme, die Markov 1906 traf, gehört heute zu den meistwiederverwendeten Modellen der angewandten Wissenschaft.

Zur VertiefungFür einen sauberen Einstieg mit Anwendungen ist Norris' Markov Chains (1997) knapp und ausgezeichnet. Die klassische Referenz ist Kemeny und Snells Finite Markov Chains (1960). Für die heutige MCMC-Praxis bleibt Robert und Casellas Monte Carlo Statistical Methods (2004) der Standard. Diaconis' Aufsätze zum Kartenmischen — und sein Buchkapitel in Group Representations in Probability and Statistics — sind der Ort der tiefsten Intuition.