Markov-Ketten: Von russischen Mathematikern zu Google und KI – Eine faszinierende Reise

Wie oft muss man ein Kartenspiel mischen, damit es wirklich zufällig ist? Oder wie viel Uran braucht man für eine Atombombe? Und wie zum Teufel weiß Google, welche Seite du eigentlich suchst? Überraschenderweise kennen wir die Antworten auf all diese Fragen wegen eines bizarren Mathematikerstreits in Russland vor über 100 Jahren. Dieser Konflikt legte den Grundstein für eine mathematische Methode, die heute unser digitales Leben maßgeblich prägt: die Markov-Ketten.

Im Jahr 1905 tobte in Russland nicht nur ein politischer Kampf zwischen Zarentreuen und Sozialisten, sondern auch ein intellektueller Krieg in der Welt der Mathematik. Auf der einen Seite stand Pawel Nekrasow, der inoffizielle „Zar der Wahrscheinlichkeit“. Ein zutiefst religiöser Mann, der glaubte, Mathematik könne den freien Willen und den Willen Gottes erklären. Auf der anderen Seite: Andrej Markov, auch bekannt als „Andrej der Wütende“. Ein Atheist, der jede Form von wissenschaftlicher Unsauberkeit verabscheute und Nekrasows Arbeiten öffentlich als „Missbrauch der Mathematik“ brandmarkte.

Der russische Mathematikerstreit: Die Geburtsstunde der Markov-Ketten

Der Streit drehte sich um das damals grundlegende Konzept der Wahrscheinlichkeitstheorie: das Gesetz der großen Zahlen. Dieses besagt, dass bei einer großen Anzahl unabhängiger Ereignisse (wie dem Münzwurf) der Durchschnitt immer näher am erwarteten Wert liegt. Nekrasow ging davon aus: Wenn man die Konvergenz zum Durchschnitt beobachtet, müssen die zugrunde liegenden Ereignisse unabhängig und somit Akte des freien Willens sein. Er sah dies in sozialen Statistiken wie Heirats- oder Kriminalitätsraten bestätigt.

Doch Markov hielt das für absurd. Er wollte beweisen, dass auch abhängige Ereignisse dem Gesetz der großen Zahlen folgen können. Seine geniale Idee: Textanalyse. Er nahm die ersten 20.000 Buchstaben aus Alexander Puschkins Gedicht „Eugen Onegin“, entfernte Satzzeichen und Leerzeichen und untersuchte die Abfolge von Vokalen und Konsonanten. Das Ergebnis war eindeutig: Die Wahrscheinlichkeit, dass auf einen Vokal ein weiterer Vokal folgt, war viel geringer, als wenn die Buchstaben voneinander unabhängig wären. Die Buchstaben waren offensichtlich abhängig.

Um Nekrasow endgültig zu widerlegen, baute Markov eine Art „Vorhersagemaschine“. Er definierte Zustände (Vokal oder Konsonant) und Übergangswahrscheinlichkeiten, also wie wahrscheinlich es ist, von einem Zustand in den nächsten zu wechseln. Selbst bei diesem abhängigen System konvergierte das Verhältnis von Vokalen zu Konsonanten nach vielen Schritten zu einem stabilen Wert. Markov hatte bewiesen: Man kann Wahrscheinlichkeit auch mit abhängigen Ereignissen berechnen. Er hatte die Grundlage für die Markov-Ketten geschaffen – ein System, bei dem der nächste Zustand nur vom aktuellen Zustand abhängt, nicht von der gesamten Historie. Man spricht hier von der Gedächtnislosigkeit des Systems.

Vom Atomkraftwerk zum Spieltisch: Die Monte-Carlo-Methode

Markovs Arbeit war ein Durchbruch, blieb aber zunächst weitgehend unbeachtet. Jahrzehnte später, während des geheimen Manhattan-Projekts im Zweiten Weltkrieg, stieß der Mathematiker Stanislaw Ulam auf ein schier unlösbares Problem: Wie verhalten sich Neutronen in einer Atombombe? Es ging darum, die kritische Masse zu bestimmen – wie viel Uran-235 man brauchte, um eine explosionsartige Kettenreaktion auszulösen.

Nach einer schweren Gehirnentzündung vertrieb sich Ulam die Zeit mit Patiencen. Dabei fragte er sich: Wie hoch ist die Chance, eine zufällig gemischte Patience zu gewinnen? Analytisch unmöglich zu lösen, da es 52 Fakultät (etwa 8×10^67) mögliche Anordnungen gibt. Seine Einsicht: Man könnte einfach hunderte Partien spielen und die Gewinne zählen, um eine statistische Annäherung zu erhalten.

Zurück in Los Alamos erkannte Ulam: Dieses Prinzip könnte auch für die Neutronen im Bombenkern funktionieren. Sein Kollege John von Neumann sah die Genialität, aber auch ein Problem: Bei Patience sind die Spiele unabhängig. Neutronen hingegen sind abhängig; ihr Verhalten hängt von ihrem aktuellen Ort, ihrer Geschwindigkeit und ihren vorherigen Interaktionen ab. Was sie brauchten, war eine Markov-Kette. Sie modellierten die Neutronen mit Zuständen (Streuung, Absorption, Spaltung) und Übergangswahrscheinlichkeiten und simulierten das Ganze auf dem ersten elektronischen Computer, dem ENIAC. Die Ergebnisse gaben Aufschluss über den Multiplikationsfaktor „k“, der entscheidend für eine Kettenreaktion ist.

Ulam nannte die neue Methode Monte-Carlo-Methode, inspiriert vom berühmten Casino in Monaco und der Zufälligkeit der Simulationen. Diese bahnbrechende statistische Methode revolutionierte nicht nur die Atomforschung, sondern fand schnell Anwendung in unzähligen wissenschaftlichen und technischen Bereichen.

Wie Google das Web organisierte: Der PageRank-Algorithmus

In den frühen 90ern explodierte das Internet förmlich. Plötzlich gab es Millionen von Webseiten, und es war fast unmöglich, die gewünschten Informationen zu finden. Erste Suchmaschinen wie Yahoo indexierten Seiten meist nur danach, wie oft ein Suchbegriff auf einer Seite vorkam. Das führte zu billigen Tricks wie dem massenhaften Verstecken von Keywords – die Qualität der Ergebnisse ließ oft zu wünschen übrig.

Die Stanford-Doktoranden Sergey Brin und Larry Page suchten nach einer besseren Lösung. Ihre Idee: Man kann das Web als eine riesige Markov-Kette modellieren. Jede Webseite ist ein Zustand, und jeder Link von einer Seite zur anderen ist ein Übergang. Ein Link ist wie eine Empfehlung. Je mehr Links eine Seite erhält, desto wichtiger ist sie. Aber nicht alle Empfehlungen sind gleichwertig: Eine Empfehlung von einer sehr wichtigen Seite zählt mehr als von einer unwichtigen.

Sie stellten sich einen „zufälligen Surfer“ vor, der von Seite zu Seite springt. Die Wahrscheinlichkeit, auf einer bestimmten Seite zu landen und dort zu verweilen, bestimmte deren Wichtigkeit. Dieser Algorithmus, den sie PageRank nannten (benannt nach Larry Page und der „Page“ im Web), ermöglichte Google, Suchergebnisse nicht nur nach Relevanz, sondern auch nach Qualität zu ordnen. Das war der entscheidende Vorteil, der Google innerhalb weniger Jahre zum meistgenutzten Suchmaschine der Welt machte. Im Herzen dieses Billionen-Dollar-Algorithmus schlägt bis heute eine Markov-Kette.

Von Gmail zu Large Language Models: Moderne Anwendungen und Grenzen

Die Ideen der Markov-Ketten finden sich heute in vielen weiteren Anwendungen. Bereits in den 1940er Jahren erweiterte Claude Shannon, der Vater der Informationstheorie, Markovs Konzept der Textvorhersage. Er zeigte, dass man umso bessere Vorhersagen über das nächste Wort treffen kann, je mehr vorherige Wörter man berücksichtigt. Dieses Prinzip nutzen heute zum Beispiel die prädiktiven Texteingaben in Gmail. Sie basieren auf erweiterten Markov-Ketten, die Wahrscheinlichkeiten für die Abfolge von „Tokens“ (Buchstaben, Wörtern, Satzzeichen) berechnen.

Auch die modernen Large Language Models (LLMs), die hinter ChatGPT und Co. stecken, bauen auf diesen grundlegenden Ideen auf. Sie erweitern die Markov-Ketten jedoch um komplexe Mechanismen wie „Attention“. Das bedeutet, sie berücksichtigen nicht nur die unmittelbare Vergangenheit, sondern können auch weiter entfernte Wörter im Satz kontextbezogen gewichten, um noch präzisere Vorhersagen zu treffen. So können sie bei einem Satz wie „Die Struktur der Zelle“ anhand des vorherigen Kontexts (z.B. „Blut“ oder „Mitochondrien“) erkennen, ob es sich um eine biologische Zelle oder eine Gefängniszelle handelt.

Doch auch diese erweiterten Systeme stoßen an Grenzen. Bei Feedbackschleifen, wie sie beim Klimawandel oder auch in der Entwicklung von KI-Modellen selbst auftreten können (wenn KI-generierte Texte zur Trainingsgrundlage für zukünftige KIs werden), versagen die klassischen Markov-Ketten. Sie führen zu „dumpfen, stabilen Zuständen“, in denen sich die Ausgabe immer wiederholt.

Dennoch bleibt die Kernidee der Markov-Ketten – die Reduktion komplexer, abhängiger Systeme auf ihren aktuellen Zustand, um aussagekräftige Vorhersagen zu treffen – unglaublich mächtig. Sie ist der Grund, warum wir verstehen, wie viele Shuffles ein Kartenspiel benötigt, um wirklich zufällig zu sein (es sind übrigens sieben „Riffle Shuffles“!). Und sie ist der Grund, warum wir die Welt um uns herum immer besser verstehen und gestalten können. Eine mathematische Idee, geboren aus einem hitzigen Streit, die die Menschheitsgeschichte immer wieder beeinflusst hat.

—

Häufig gestellte Fragen

F: Was ist das Besondere an Markov-Ketten im Vergleich zu anderen Wahrscheinlichkeitsmodellen?

A: Das Besondere an Markov-Ketten ist ihre Fähigkeit, Systeme zu modellieren, bei denen der nächste Zustand vom aktuellen Zustand abhängt, nicht von der gesamten Vergangenheit des Systems. Man nennt dies die „Gedächtnislosigkeit“ der Markov-Kette. Im Gegensatz zum Gesetz der großen Zahlen, das unabhängige Ereignisse behandelt, können Markov-Ketten auch abhängige Ereignisse für Wahrscheinlichkeitsberechnungen nutzen.

F: Welche Rolle spielt die Monte-Carlo-Methode im Zusammenhang mit Markov-Ketten?

A: Die Monte-Carlo-Methode ist eine Simulationsmethode, die oft Markov-Ketten nutzt. Sie ermöglicht es, die Eigenschaften komplexer Systeme (wie das Verhalten von Neutronen in einer Atombombe) statistisch zu untersuchen, indem man eine große Anzahl von zufälligen Ereignisketten simuliert. Anstatt exakte, oft unmögliche Berechnungen durchzuführen, erhält man so eine zuverlässige Annäherung an das Ergebnis.

F: Sind moderne KI-Sprachmodelle wie LLMs reine Markov-Ketten?

A: Nein, moderne Large Language Models (LLMs) sind keine reinen Markov-Ketten im klassischen Sinne. Sie bauen zwar auf dem fundamentalen Konzept der Vorhersage des nächsten Tokens auf der Grundlage des vorherigen Kontexts auf, nutzen aber erweiterte Architekturen wie neuronale Netze und den „Attention“-Mechanismus. Dieser ermöglicht es ihnen, komplexere, weiter entfernte Abhängigkeiten im Text zu erkennen und zu gewichten, was über die Gedächtnislosigkeit klassischer Markov-Ketten hinausgeht.