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 erste Anwendung, die er wählte, war beinahe schalkhaft — die Verteilung von Vokalen und Konsonanten in Puschkins Eugen Onegin — und sie funktionierte. 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).
PageRank — 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.