Markow-Ketten: Übergangsmatrix, stationäre Verteilung und PageRank

Die Markow-Eigenschaft, die Übergangsmatrix und die Entwicklung einer Verteilung an einem Wettermodell, die stationäre Verteilung und der Ergodensatz, Markows Vokalanalyse angewandt auf Máchas Máj, PageRank und Textgenerierung.

13 Minuten Matěj Žalmánek 2026-10-15

Serie KI-Grundlagen Teil 38 von 52

1. Landkarte der künstlichen Intelligenz: was was ist und wie alles zusammenpasst
2. Eine kurze Geschichte der künstlichen Intelligenz: von Turing bis zu Sprachmodellen
3. Daten, Modell, Training, Inferenz: die Grundbegriffe an einem einzigen Beispiel
4. Mathematische Notation lesen: Symbole, Indizes, Summen und Quantoren
5. Mengen und Relationen: der Baukasten, aus dem Definitionen in der KI bestehen
6. Funktionen und Abbildungen: warum jedes KI-Modell eine Funktion ist
7. Logik und Beweise: die Regeln, nach denen KI schließt
8. Graphen und Bäume: die Struktur, auf der Suche und neuronale Netze stehen
9. Lineare Algebra für maschinelles Lernen: Vektoren, Matrizen und warum KI vor allem multipliziert
10. Ableitungen, Gradient und Kettenregel: wie ein Modell herausfindet, in welche Richtung es lernen soll
11. Gradientenabstieg: wie ein Modell lernt
12. Was ist Wahrscheinlichkeit: vom Würfelwurf zu den Kolmogorow-Axiomen
13. Bedingte Wahrscheinlichkeit und der Satz von Bayes: wie du deine Einschätzung änderst, wenn du etwas Neues erfährst
14. Zufallsvariable und Verteilungsfunktion: eine Funktion, die alles über eine Verteilung verrät
15. Dichtefunktion und Wahrscheinlichkeitsfunktion: warum eine stetige Zufallsvariable in einem Punkt die Wahrscheinlichkeit null hat
16. Erwartungswert, Varianz und Kovarianz: wo eine Verteilung liegt, wie breit sie ist und was womit zusammenhängt
17. Überblick über Wahrscheinlichkeitsverteilungen: Bernoulli-, Binomial-, Poisson-, Gleich-, Normal- und Exponentialverteilung
18. Gesetz der großen Zahlen und zentraler Grenzwertsatz: Warum sich Durchschnitte so vorhersagbar verhalten
19. Statistik und Parameterschätzung: Maximum Likelihood, MAP und Konfidenzintervalle
20. Informationstheorie: Entropie, Kreuzentropie und KL-Divergenz — woher Verlustfunktionen kommen
21. Zustandsraumsuche: BFS, DFS, UCS und A* mit Animationen
22. Spiele und Gegner: Minimax, Alpha-Beta-Suche und Monte Carlo Tree Search
23. Constraint Satisfaction: Backtracking, Constraint-Propagierung und AC-3 an Sudoku und einer Karte tschechischer Regionen
24. Logik und wissensbasierte Systeme: Vorwärts- und Rückwärtsverkettung, Resolution und Expertensysteme
25. Planung: STRIPS, die Blockwelt, Heuristiken aus Relaxierung und Planung in KI-Agenten
26. Lokale Suche und simulierte Abkühlung: ein Handlungsreisender durch die tschechischen Regionalhauptstädte
27. Genetische Algorithmen: Population, Kreuzung, Mutation und Selektion am Rucksack für die Wanderung
28. Evolutionsstrategien und genetische Programmierung: von der 1/5-Erfolgsregel zum Keplerschen Gesetz
29. Ameisenkolonieoptimierung: wie eine Pheromonspur einen kurzen Weg findet
30. Partikelschwarmoptimierung: Trägheit, eigene Erfahrung und die Erfahrung des Schwarms
31. Neuroevolution: Evolution der Gewichte und der Gestalt neuronaler Netze und der Algorithmus NEAT
32. Fuzzy-Mengen und Zugehörigkeitsfunktionen: wie man „etwas warm“ aufschreibt
33. Fuzzy-Logik und Wahrscheinlichkeit: warum „etwas warm“ nicht „wahrscheinlich warm“ bedeutet
34. Fuzzy-Logik: t-Normen, Implikationen und WENN–DANN-Regeln
35. Fuzzy-Regelung: Mamdani und Sugeno vom Ventilator bis zum Pendel auf dem Wagen
36. Fuzzy-Clustering: der Algorithmus fuzzy c-means und Punkte zwischen den Clustern
37. Neuro-Fuzzy-Systeme (ANFIS): Fuzzy-Regeln, die aus Daten lernen
38. Markow-Ketten: Übergangsmatrix, stationäre Verteilung und PageRank
39. Hidden-Markov-Modelle: der Viterbi-Algorithmus und das unehrliche Kasino
40. Bayessche Netze: warum das Gras nass ist und was das für den Rasensprenger bedeutet
41. Der Kalman-Filter: wie man aus ungenauen Messungen schätzt, wo ein Auto ist und wie schnell es fährt
42. Arten des maschinellen Lernens: überwacht, unüberwacht, halbüberwacht und mehr
43. Prompts, Kontext und RAG: wie man einem Modell die richtigen Informationen gibt
44. Variational Autoencoder (VAE): neue Bilder aus einem stetigen latenten Raum
45. Generative Adversarial Networks (GAN): der Fälscher gegen den Detektiv
46. Diffusionsmodelle: wie aus reinem Rauschen ein Bild wird
47. Markow-Entscheidungsprozesse: Zustände, Aktionen, Belohnungen und Bellman-Gleichungen
48. Q-Learning und DQN: den Wert von Aktionen lernen, von der Tabelle bis zum neuronalen Netz
49. Policy Gradient und PPO: die Strategie direkt lernen
50. Wie ein KI-Agent funktioniert: ein Sprachmodell in einer Schleife mit Werkzeugen
51. Programmieren mit KI-Agenten: Auftrag, Tests und Kontrolle
52. Bewertung und Sicherheit von KI-Systemen: wie man misst und wie man überwacht

Der ganze Lehrplan der Serie 52 von 83 Themen fertig

Im Jahr 1913 saß der russische Mathematiker Andrei Markow über Puschkins Eugen Onegin und tat etwas, das ein Literaturwissenschaftler für Barbarei halten würde: Er zählte, wie oft auf einen Vokal ein weiterer Vokal folgt. Er wollte zeigen, dass das Gesetz der großen Zahlen auch für Ereignisse gilt, die voneinander abhängen — und erfand dabei ein Modell, das heute die Rangfolge der Seiten in einer Suchmaschine berechnet, das Wetter vorhersagt, Text erzeugt und hinter einer ganzen Familie von KI-Algorithmen steht. Mit diesem Teil beginnt das Modul über probabilistische Modelle.

Er knüpft an die Teile Bedingte Wahrscheinlichkeit und der Satz von Bayes und Lineare Algebra für maschinelles Lernen an.

1. Ein Prozess ohne Gedächtnis

Definition — Markow-Kette

Eine Folge von Zufallsvariablen X₀, X₁, X₂, … mit Werten in einer endlichen Zustandsmenge S ist eine Markow-Kette, wenn für alle t und alle Zustände die Markow-Eigenschaft gilt:

P(X_t+1 = j | X_t = i, X_t−1, …, X₀) = P(X_t+1 = j | X_t = i).

Hängt diese Wahrscheinlichkeit nicht von t ab, heißt die Kette homogen.

Was die Markow-Eigenschaft bringt, sieht man an der Wahrscheinlichkeit eines ganzen Pfades. Allgemein zerfällt sie nach der Kettenregel in ein Produkt bedingter Wahrscheinlichkeiten, von denen jede von der ganzen Vergangenheit abhängt. Die Markow-Eigenschaft streicht aus jeder Bedingung alles außer dem letzten Zustand:

P(X₀ = x₀, …, X_T = x_T) = π₀(x₀) · ∏_t=1^T P(x_t | x_t−1)

P(X₀ = x₀, …)

die Wahrscheinlichkeit, dass die Kette genau diese Folge von Zuständen durchläuft

π₀(x₀)

die Anfangsverteilung — wo die Kette startet, sagt die Matrix nicht; diese Angabe muss von außen kommen

∏_t=1^T

Produkt über die Schritte — die Schritte folgen aufeinander und jeder muss „aufgehen“, deshalb wird multipliziert

P(x_t | x_t−1)

die Übergangswahrscheinlichkeit eines Schritts, also das Element der Übergangsmatrix in Zeile x_t−1 und Spalte x_t — dank der Markow-Eigenschaft hängt sie nur vom vorherigen Zustand ab, nicht von der ganzen Vorgeschichte; ohne sie stünde hier P(x_t | x₀, …, x_t−1)

2. Die Übergangsmatrix

Definition — Übergangsmatrix

Eine homogene Kette mit n Zuständen ist durch die Übergangsmatrix P = (p_ij) bestimmt, wobei p_ij = P(X_t+1 = j | X_t = i). Die Matrix ist stochastisch: p_ij ≥ 0 und jede Zeile hat die Summe 1.

Ein Spielzeugmodell des Wetters mit drei Zuständen: Nach einem sonnigen Tag ist es mit Wahrscheinlichkeit 0,6 wieder sonnig, mit 0,3 bewölkt und mit 0,1 regnet es; nach einem bewölkten 0,3 / 0,4 / 0,3; nach einem regnerischen 0,2 / 0,4 / 0,4. Als Graph:

Dieselbe Information als Matrix — die Zeile ist das heutige Wetter, die Spalte das morgige:

Beispiel — Wahrscheinlichkeit eines Pfades

Heute ist es sonnig (π₀ = (1; 0; 0)). Wie wahrscheinlich ist es, dass die nächsten drei Tage sonnig, bewölkt, Regen sind? Nach der Formel für einen Pfad gilt

P = 1 · p_{sonnig→sonnig} · p_{sonnig→bewölkt} · p_{bewölkt→Regen} = 1 · 0,6 · 0,3 · 0,3 = 0,054.

Also 5,4 %. Die Summe über alle 3³ = 27 möglichen Dreiergruppen von Tagen ist 1 — genau deshalb, weil jede Zeile der Matrix die Summe 1 hat.

3. Wie sich die Verteilung entwickelt

Satz — Verteilung nach n Schritten

Ist π_t der Zeilenvektor der Verteilung von X_t, dann gilt π_t+1 = π_t P und somit π_t = π₀ P^t. Das Element (i, j) der Matrix Pⁿ ist die Wahrscheinlichkeit, in n Schritten von i nach j zu gelangen.

π_t+1(j) = ∑_i π_t(i) · p_ij

π_t+1(j)

die Wahrscheinlichkeit, dass morgen der Zustand j herrscht — eine Komponente des neuen Zeilenvektors

∑_i

Summe über alle heutigen Zustände — nach j kommt man von überall her, und diese Wege schließen sich gegenseitig aus, also addieren sich ihre Wahrscheinlichkeiten (Satz von der totalen Wahrscheinlichkeit)

π_t(i)

wie wahrscheinlich es ist, dass wir heute in i sind — das Gewicht des Weges über i

p_ij

die Wahrscheinlichkeit des Übergangs von i nach j — wegen der Markow-Eigenschaft genügt es, nur den heutigen Zustand zu kennen

Beispiel — Verteilung für übermorgen

Morgen (nach einem sonnigen Heute) ist π₁ = (0,6; 0,3; 0,1). Für übermorgen komponentenweise — eine Spalte der Matrix multipliziert mit dem Vektor π₁:

• sonnig: 0,6 · 0,6 + 0,3 · 0,3 + 0,1 · 0,2 = 0,36 + 0,09 + 0,02 = 0,47,
• bewölkt: 0,6 · 0,3 + 0,3 · 0,4 + 0,1 · 0,4 = 0,18 + 0,12 + 0,04 = 0,34,
• Regen: 0,6 · 0,1 + 0,3 · 0,3 + 0,1 · 0,4 = 0,06 + 0,09 + 0,04 = 0,19.

Die Summe ist wieder 1. Für drei Tage ergibt sich auf dieselbe Weise (0,422; 0,353; 0,225).

Interessant: Nach etwa einer Woche ist es egal, ob heute die Sonne scheint oder es regnet. Beide Verteilungen treffen sich bei denselben Werten und ändern sich danach nicht mehr. Die Kette hat „vergessen“, wo sie begonnen hat.

Satz — wie schnell die Kette vergisst

Hat die Matrix P mit n Zuständen n verschiedene Eigenwerte 1 = λ₁, λ₂, …, λ_n und ist |λ_k| < 1 für k ≥ 2, dann zerlegt sich jede Anfangsverteilung in die linken Eigenvektoren, und es gilt

π_t = π + a₂λ₂^tu₂ + … + a_nλ_n^tu_n,

wobei π die stationäre Verteilung ist. Die Abweichung von π fällt also wie |λ₂|^t, wobei λ₂ der betragsmäßig zweitgrößte Eigenwert ist.

π_t ≈ π + a₂u₂ · λ₂^t

π_t

die Verteilung nach t Tagen

π

die stationäre Verteilung — sie gehört zum Eigenwert 1, der sich beim Potenzieren nicht ändert; deshalb ist sie der einzige Teil, der überlebt

a₂u₂

die anfängliche Abweichung in Richtung des zweiten Eigenvektors — nur hier zeigt sich, wo die Kette gestartet ist (Sonne oder Regen); in der Komponente sonnig ist sie bei sonnigem Start positiv und bei regnerischem negativ

λ₂^t

mit jedem Tag schrumpft die Abweichung um den Faktor λ₂ — die Geschwindigkeit des Vergessens; die übrigen Glieder mit kleinerem |λ| verschwinden noch schneller, deshalb dürfen wir sie weglassen

Beispiel — Eigenwerte der Wettermatrix

Die Summe der Eigenwerte ist die Spur der Matrix, 0,6 + 0,4 + 0,4 = 1,4, und ihr Produkt ist die Determinante, die 0,01 ergibt. Ein Eigenwert ist 1 (die Zeilen haben die Summe 1), also erfüllen die beiden übrigen λ₂ + λ₃ = 0,4 und λ₂λ₃ = 0,01. Sie sind die Wurzeln von λ² − 0,4λ + 0,01 = 0:

λ_2,3 = 0,2 ± √0,03 = (2 ± √3)/10, also λ₂ ≈ 0,373 und λ₃ ≈ 0,027.

Die Abweichung der Wahrscheinlichkeit für sonnig vom stationären Wert 0,393 beträgt bei sonnigem Start nach 3, 4, 5 Tagen 0,0286; 0,0107; 0,0040 — jeden Tag etwa 0,373-mal so groß. Nach einer Woche sind es 0,0006 und bei regnerischem Start −0,0005: Beide Anfänge unterscheiden sich erst an der vierten Nachkommastelle. Auf ein Hundertstel schrumpft die Abweichung in ln 0,01 / ln 0,373 ≈ 4,7 Tagen.

4. Die stationäre Verteilung

Definition — stationäre Verteilung

Eine Verteilung π ist stationär, wenn π P = π — π ist also ein linker Eigenvektor der Matrix P zum Eigenwert 1.

Definition — irreduzible und aperiodische Kette

Bezeichne p_ij⁽ⁿ⁾ das Element (i, j) der Matrix Pⁿ, also die Wahrscheinlichkeit, in n Schritten von i nach j zu gelangen.

• Die Kette ist irreduzibel, wenn es für je zwei Zustände i, j ein n ≥ 1 mit p_ij⁽ⁿ⁾ > 0 gibt.
• Die Periode des Zustands i ist d(i) = ggT{n ≥ 1 : p_ii⁽ⁿ⁾ > 0} — der größte gemeinsame Teiler der Längen aller Wege, die nach i zurückkehren. Bei d(i) = 1 ist der Zustand aperiodisch; in einer irreduziblen Kette haben alle Zustände dieselbe Periode.

Das Wetter ist sofort beides: Alle Elemente von P sind positiv (n = 1 genügt) und p_ii > 0, also ist eine Rückkehr in 1 Schritt möglich und die Periode ist 1. Dagegen ist eine Kette mit zwei Zuständen, die regelmäßig abwechseln (p₁₂ = p₂₁ = 1), irreduzibel, hat aber die Periode 2: π₀P^t springt für den Start (1; 0) endlos zwischen (1; 0) und (0; 1) hin und her, obwohl die stationäre Verteilung (½; ½) existiert.

Satz — Ergodensatz für endliche Ketten

Ist eine endliche Kette irreduzibel (von jedem Zustand kommt man in jeden) und aperiodisch, dann hat sie eine einzige stationäre Verteilung π, und für jede Anfangsverteilung gilt π₀ P^t → π. Außerdem nähert sich der Anteil der Zeit, den die Kette im Zustand j verbringt, mit Wahrscheinlichkeit 1 dem Wert π_j, und die mittlere Rückkehrzeit nach j beträgt 1/π_j.

Für unser Modell ergibt sich die stationäre Verteilung exakt als (24/61; 22/61; 15/61) ≈ (0,393; 0,361; 0,246): Auf lange Sicht ist es an 39 % der Tage sonnig, an 36 % bewölkt, und an 25 % regnet es. Nach einem Regentag warten wir auf den nächsten Regen im Mittel 1/0,246 ≈ 4,07 Tage.

Beispiel — stationäre Verteilung des Wetters von Hand

Wir suchen π = (a; b; c) mit πP = π. Nach den Spalten der Matrix:

• a = 0,6a + 0,3b + 0,2c, also 4a = 3b + 2c,
• b = 0,3a + 0,4b + 0,4c,
• c = 0,1a + 0,3b + 0,4c, also 6c = a + 3b.

Die Gleichungen sind abhängig (addiert man alle drei, erhält man a + b + c = a + b + c), also lassen wir die mittlere weg. Aus der dritten folgt a = 6c − 3b, eingesetzt in die erste 24c − 12b = 3b + 2c, also b = 22c/15 und a = 6c − 66c/15 = 24c/15. Das Verhältnis ist a : b : c = 24 : 22 : 15, und die Bedingung a + b + c = 1 ergibt

π = (24/61; 22/61; 15/61) ≈ (0,393; 0,361; 0,246).

Die mittlere Rückkehrzeit zum Regen beträgt 1/π_Regen = 61/15 ≈ 4,07 Tage.

Und die Simulation eines einzelnen zufälligen Verlaufs zeigt den Ergodensatz in Aktion:

Die Simulation lost jeden Tag einzeln aus der Zeile des heutigen Zustands: Eine Zufallszahl u aus [0, 1) wird mit den laufenden Summen der Zeile verglichen. Nach einem sonnigen Tag führt u < 0,6 zu sonnig, 0,6 ≤ u < 0,9 zu bewölkt und der Rest zu Regen:

stav = sonnig
for den in 1 … N:
    u = Zufallszahl aus [0, 1)
    j = 0
    while u ≥ P[stav][j]:          # Wahrscheinlichkeiten abziehen, bis u in ein Fach „fällt“
        u = u − P[stav][j]
        j = j + 1
    stav = j
    počet[stav] += 1
podíly = počet / N                 # nach dem Ergodensatz → π

Die stationäre Verteilung selbst lässt sich ohne Auslosen berechnen, durch wiederholte Multiplikation mit der Matrix:

import numpy as np

P = np.array([[0.6, 0.3, 0.1],
              [0.3, 0.4, 0.3],
              [0.2, 0.4, 0.4]])

pi = np.ones(3) / 3
for _ in range(100):          # Potenzmethode: π ← π P
    pi = pi @ P
print(pi.round(3))            # [0.393 0.361 0.246]

5. Markow, Onegin und Máj

Markow ging die ersten 20 000 Buchstaben von Eugen Onegin durch und markierte jeden als Vokal oder Konsonant. Vokale waren es 43,2 %. Folgten die Buchstaben unabhängig aufeinander, käme ein Vokal nach einem Vokal ebenfalls in 43,2 % der Fälle. Markow zählte aber nur 12,8 %, nach einem Konsonanten dagegen 66,3 %. Die Buchstaben hängen voneinander ab — und trotzdem konvergiert der Anteil der Vokale in einem langen Text zuverlässig. Das war sein Beweis, dass das Gesetz der großen Zahlen keine Unabhängigkeit braucht.

Wiederholen wir das an der ersten Strophe von „Máj“ (Mai), dem Gedicht von Karel Hynek Mácha („Byl pozdní večer – první máj…“). Sie hat 311 Buchstaben, davon 37,6 % Vokale. Die Schätzung der Übergangsmatrix aus den Paarzählungen:

In der Strophe gibt es nur 6 Paare aufeinanderfolgender Vokale — das Tschechische wechselt sie noch lieber mit Konsonanten ab als das Russische. Und die stationäre Verteilung dieser Kette ergibt 37,7 % Vokale: Die aus dem Text geschätzte Kette „pendelt sich“ praktisch auf dem Anteil ein, der tatsächlich im Text steckt (den Unterschied machen nur der erste und der letzte Buchstabe).

p̂_ij = n_ij / ∑_k n_ik

p̂_ij

die Schätzung der Übergangswahrscheinlichkeit — das Dach sagt, dass es eine aus Daten berechnete Zahl ist, nicht der wahre Wert

n_ij

wie oft im Text auf i unmittelbar j folgte — gezählt werden Paare benachbarter Buchstaben, denn eine Markow-Kette blickt nur einen Schritt zurück

∑_k n_ik

wie oft auf i irgendetwas folgte — durch die Division summiert sich die Zeile zu 1, wie es eine stochastische Matrix verlangt

Beispiel — Paarzählungen in der ersten Strophe

311 Buchstaben ergeben 310 benachbarte Paare. Vokal–Vokal 6, Vokal–Konsonant 111, Konsonant–Vokal 111, Konsonant–Konsonant 82. Daraus folgt

p̂_vok→vok = 6/117 = 0,051, p̂_vok→kon = 111/117 = 0,949, p̂_kon→vok = 111/193 = 0,575, p̂_kon→kon = 82/193 = 0,425.

Eine Kette mit zwei Zuständen hat eine stationäre Verteilung, die eine einfache Formel angibt:

π_vok = p_kon→vok / (p_vok→kon + p_kon→vok)

π_vok

der langfristige Anteil der Vokale

p_kon→vok

der Fluss zu den Vokalen — je öfter man vom Konsonanten zum Vokal wechselt, desto mehr Vokale

p_vok→kon

der Fluss von den Vokalen weg — je schneller man den Vokal verlässt, desto weniger gibt es davon

Beispiel — Máj und Onegin nach der Formel

Máj: π_vok = 0,575 / (0,949 + 0,575) = 0,377. Genauer: Übergänge Vokal→Konsonant und Konsonant→Vokal gibt es gleich viele (111), also π_vok = (111/193) / (111/117 + 111/193) = 117/310. Der tatsächliche Anteil der Vokale ist 117/311 — er unterscheidet sich nur im Nenner, weil der letzte Buchstabe der Strophe („r“) kein Paar beginnt.

Onegin: Aus Markows Zahlen (Vokal nach Vokal 12,8 %, also Vokal→Konsonant 87,2 %; Vokal nach Konsonant 66,3 %) ergibt sich π_vok = 0,663 / (0,872 + 0,663) = 0,432 — genau die 43,2 % Vokale, die Markow direkt gezählt hat.

6. PageRank: der zufällige Surfer

1998 schlugen Sergey Brin und Larry Page, die Gründer von Google, vor, wie man Webseiten nach ihrer Wichtigkeit ordnen kann. Sie stellten sich einen Surfer vor, der zufällig auf Links klickt, und fragten: Auf welchen Seiten verbringt er die meiste Zeit?

Definition — PageRank

Seite i mit k_i ausgehenden Links. Der zufällige Surfer klickt mit Wahrscheinlichkeit d (üblicherweise 0,85) gleichverteilt zufällig auf einen der Links, andernfalls springt er auf eine beliebige der N Seiten:

p_ij = (1 − d)/N + d/k_i, wenn i auf j verlinkt, sonst (1 − d)/N.

Der PageRank ist die stationäre Verteilung dieser Kette. Die Sprünge garantieren, dass die Kette irreduzibel und aperiodisch ist.

Ganz oben steht C (0,374), auf die fast jede Seite verlinkt. Interessanter ist A: Sie hat einen einzigen eingehenden Link und ist trotzdem Zweite (0,342) — weil dieser Link von C kommt und C nirgendwo anders hin verlinkt. B, auf die nur A verlinkt, bekommt die Hälfte des Gewichts von A (0,171). Die Seiten D, E und F, die vor allem untereinander verlinken, bleiben bei etwa 0,04. Der echte PageRank berechnete dasselbe für Milliarden von Seiten, mit der Potenzmethode.

Die Gleichung π = πP, für eine einzelne Seite ausgeschrieben, ergibt die bekannte Form des PageRank:

PR(j) = (1 − d)/N + d ∑_i→j PR(i) / k_i

PR(j)

der PageRank der Seite j — der Anteil der Zeit, den der Surfer auf ihr verbringt; die Summe über alle Seiten ist 1

(1 − d)/N

der Beitrag der zufälligen Sprünge — jede Seite bekommt ihn gleich, auch eine, auf die nichts verlinkt; dank ihm ist die Kette irreduzibel und aperiodisch

d

die Wahrscheinlichkeit, dass der Surfer auf einen Link klickt, statt woandershin zu springen — 0,85 im ursprünglichen Artikel von Brin und Page

∑_i→j

Summe nur über die Seiten, die auf j verlinken — ein Link ist eine „Stimme“ für die Zielseite

PR(i) / k_i

die Stimme der Seite i wiegt so viel, wie wichtig i selbst ist, und teilt sich auf alle ihre k_i Links auf — eine Seite mit tausend Links gibt jedem nur wenig

Beispiel — Überprüfung von A, B und C

Für N = 6 und d = 0,85 ist (1 − d)/N = 0,025. Nach A führt nur der Link von C, das einen einzigen Link hat (k_C = 1); nach B nur der von A, das zwei hat:

• PR(A) = 0,025 + 0,85 · 0,37351 / 1 = 0,34248,
• PR(B) = 0,025 + 0,85 · 0,34248 / 2 ≈ 0,1706,
• PR(C) = 0,025 + 0,85 · (PR(A)/2 + PR(B)/1 + PR(D)/2 + PR(E)/3 + PR(F)/1) = 0,025 + 0,85 · 0,41001 = 0,37351.

Die Werte aus der Potenzmethode erfüllen die Gleichung — daran erkennt man, dass die Iteration fertig ist.

PR = [1/N] * N                              # gleichmäßig beginnen
repeat:
    nové = [(1 − d)/N] * N                  # zufällige Sprünge
    for i in stránky:
        if i hat keine Links:               # Sackgasse: irgendwohin springen
            nové[j] += d · PR[i]/N  für alle j
        else:
            for j in odkazy[i]:
                nové[j] += d · PR[i]/k_i
    PR = nové
until PR sich kaum noch ändert

7. Ketten, Text und Sprachmodelle

Eine Kette, deren Zustände Buchstaben sind, kann man generieren lassen. Aus den Buchstabenpaaren der ersten Strophe von Máj schätzen wir, was auf welchen Buchstaben folgt, und losen dann. So sehen 90 Zeichen aus:

lal kou lasvavzvný dnkyl plásnětičaskol dnou ta javu snáscezepráro pl h jin trů bo kylalav

Unsinn — aber Unsinn, der „tschechisch klingt“: Er wechselt Vokale und Konsonanten ab, hat kurze Wörter und Silben wie „lás“ oder „kol“. Denselben Versuch machte Claude Shannon 1948 mit dem Englischen und zeigte, dass der Text mit längerem Kontext (Buchstabentripel, Wortpaare) immer natürlicher aussieht.

Beispiel — die Zeile „l“ des Bigrammmodells

Wir wandeln den Text der Strophe in Kleinbuchstaben um und ersetzen die Satzzeichen durch Leerzeichen. Auf den Buchstaben „l“ folgt darin 31-mal ein weiteres Zeichen: 13-mal ein Leerzeichen, 7-mal „a“, 6-mal „á“, 2-mal „o“ und je einmal „i“, „h“, „u“. Nach der Schätzformel ist also

P(Leerzeichen | l) = 13/31 ≈ 0,42, P(a | l) = 7/31 ≈ 0,23, P(á | l) = 6/31 ≈ 0,19, P(o | l) = 2/31 ≈ 0,06 und die übrigen 1/31 ≈ 0,03.

Das Generieren macht dann dasselbe wie die Wettersimulation: Aus der Zeile des aktuellen Zeichens lost es das nächste Zeichen aus. Nach „l“ ist ein Wort meistens zu Ende — „byl“, „lhal“, „kol“, „bol“.

Definition — n-Gramm-Modell

Ein n-Gramm-Modell sagt das nächste Symbol anhand der n − 1 vorherigen vorher: P(w_t | w_t−n+1, …, w_t−1). Es ist eine Markow-Kette, deren Zustand die letzten n − 1 Symbole sind.

Beispiel — wie viele Zustände ein n-Gramm-Modell hat

Mit einem Vokabular aus V Symbolen hat ein n-Gramm-Modell |V|ⁿ⁻¹ Zustände und in jeder Zeile |V| Wahrscheinlichkeiten. Die Strophe von Máj verwendet 32 verschiedene Zeichen (Buchstaben und Leerzeichen):

• Bigramme (n = 2): 32 Zustände, eine Matrix mit 32 × 32 = 1 024 Zahlen — mehr, als die Strophe Zeichen hat, sodass die meisten davon null ergeben;
• Trigramme: 32² = 1 024 Zustände und über 32 Tausend Zahlen — die meisten Buchstabenpaare kommen in der Strophe gar nicht vor, und ihre Zeilen bleiben leer;
• ein Sprachmodell mit einem Vokabular von 50 000 Tokens und einem Fenster von 1 000 Tokens: 50 000^1 000 ≈ 10^4 699 Zustände.

Deshalb braucht ein längerer Kontext entweder riesige Datenmengen oder ein Modell, das die Wahrscheinlichkeiten nicht aus einer Tabelle nimmt, sondern sie mit einer Funktion schätzt — mit einem neuronalen Netz.

8. Wohin Markow-Ketten führen

• Hidden-Markov-Modelle — was, wenn wir den Zustand nicht sehen, sondern nur seine Auswirkungen? Darum geht es im nächsten Teil.
• Markow-Entscheidungsprozesse fügen Aktionen und Belohnungen hinzu: Auf ihnen beruht das bestärkende Lernen.
• Markov-Chain-Monte-Carlo-Verfahren (MCMC) bauen eine Kette, deren stationäre Verteilung genau die ist, aus der wir Stichproben ziehen wollen — typischerweise die A-posteriori-Verteilung in der bayesschen Statistik. Das Metropolis-Kriterium aus dem Teil über simulierte Abkühlung ist genau so eine Kette.

9. Zusammenfassung

• Eine Markow-Kette hat kein Gedächtnis: Der nächste Zustand hängt nur vom aktuellen ab. Beschrieben wird sie durch eine stochastische Übergangsmatrix P.
• Die Verteilung entwickelt sich durch Multiplikation mit der Matrix, π_t = π₀ P^t.
• Eine irreduzible aperiodische Kette pendelt sich auf einer einzigen stationären Verteilung π = π P ein, unabhängig vom Anfang; für das Wetter (0,393; 0,361; 0,246).
• Markow zeigte die Abhängigkeit der Buchstaben an Onegin; in Máj folgt ein Vokal auf einen Vokal nur in 5 % der Fälle.
• PageRank ist die stationäre Verteilung des zufälligen Surfers; n-Gramm-Modelle und auch heutige Sprachmodelle sind Markow-Ketten mit einem großen Zustand.

Willst du es selbst ausprobieren? Lass einen KI-Agenten ein Wort-Bigrammmodell aus dem ganzen Máj oder aus deinen eigenen E-Mails bauen und daraus Sätze generieren — und probiere dann Trigramme aus.

Siehst du das anders? Schreib an support@coden-app.com.