Explorer für stationäre Markow-Ketten

Übergangsmatrix-Simulator mit k-Schritt-Entwicklung und Anschauung zum stationären Zustand.

Rechenbeispiel — Explorer für stationäre Markow-Ketten

1	0.65985
2	0.218714
3	0.121436
Abstand zur Stationarität	0.08893

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

Lektion

Die Theorie — Explorer für stationäre Markow-Ketten

Eine Verteilung ist stationär, wenn ein weiterer Schritt nichts mehr ändert: πP = π. Sie ist ein Fixpunkt der Übergangsmatrix — die Kette bewegt sich zwar weiterhin zwischen den Zuständen, aber die Anteile verändern sich nicht mehr.

Was die einzelnen Symbole bedeuten

P: die Übergangsmatrix. Der Eintrag in Zeile i, Spalte j ist die Wahrscheinlichkeit für einen Übergang von Zustand i zu Zustand j, sodass jede Zeile in der Summe 1 ergeben muss — was das obige Gitter für dich prüft.
p(0): die Startverteilung: der Ausgangspunkt der Kette. Der Standardwert (1, 0, 0) bedeutet, dass sie mit Sicherheit in Zustand 1 beginnt.
p(k): die Verteilung nach k Schritten, die man durch schrittweises Multiplizieren mit P erhält.
π: die stationäre Verteilung — diejenige, die πP = π erfüllt.
k: wie viele Schritte ausgeführt werden, oben eingestellt. Die Trajektorientabelle zeigt jede Verteilung von p(0) bis p(k).

Woher die Formel kommt

Formuliere die Bedingung für Stationarität: Nach einem Schritt bleibt die Verteilung unverändert, also πP = π.
Umgeformt ergibt das π(P − I) = 0 — ein lineares Gleichungssystem mit einer Gleichung pro Zustand. Für sich genommen hat es unendlich viele Lösungen, da jedes Vielfache einer Lösung ebenfalls eine Lösung ist.
Fügt man die Bedingung hinzu, dass es sich um eine Wahrscheinlichkeitsverteilung handelt, Σπ = 1, ist die Lösung eindeutig bestimmt. Für die Standardmatrix lautet sie exakt 8/13, 3/13, 2/13 — das oben angegebene 0.615385, 0.230769, 0.153846.

So liest du, was du siehst

Drei Panels. p(k) zeigt, wo sich die Kette nach deinen k Schritten tatsächlich befindet; π ist der Zustand, auf den sie zusteuert, samt Iterationszahl und Konvergenzstatus; und der Abstand zur Stationarität misst die Abweichung zwischen beiden — 0.08893 beim Standardwert k = 8, weshalb im Hinweis steht, dass die Kette noch nicht vollständig durchmischt ist. Die Trajektorientabelle unten zeigt jeden Schritt ausgehend von (1, 0, 0).

Setzt voraus: Eine endliche Zustandsmenge und Übergangswahrscheinlichkeiten, die sich im Laufe der Zeit nicht verändern. Dass jede Zeile die Summe 1 ergibt, ist keine Formatierungsregel, sondern die Aussage, dass die Kette bei jedem Schritt irgendwohin wechseln muss.
Versagt, wenn: Das obige π wird aus gutem Grund als Schätzung bezeichnet: Es wird durch wiederholtes Ausführen der Kette erreicht — 83 Iterationen bei der Standardmatrix — und gestoppt, wenn sich aufeinanderfolgende Verteilungen nicht mehr verändern. Das ist eine numerische Beurteilung, kein Beweis. Die exakte Lösung ist hier die Menge der Brüche 8/13, 3/13, 2/13, und die angezeigten Dezimalzahlen sind diese auf sechs Nachkommastellen gerundet.

PageRank ist genau diese Rechnung, angewandt auf das ganze Web 🖖

Die stationäre Verteilung ist nicht nur eine Lehrbuchübung — Google wurde auf einer gegründet. Betrachte jede Webseite als Zustand und jeden Link als Übergang: die stationäre Verteilung dieser gewaltigen Kette gibt an, wie oft ein Leser, der endlos Links anklickt, auf jeder Seite landen würde. Das ist PageRank. Auch der berühmte Dämpfungsfaktor 0,85, der den Surfer in 15% der Fälle auf eine zufällige Seite schickt, ist keine willkürliche Feinjustierung: er stellt sicher, dass jeder Zustand jeden anderen erreichen kann, und genau das ist die Bedingung dafür, dass die stationäre Verteilung überhaupt eindeutig und erreichbar ist. Ohne ihn würden Seiten ohne ausgehende Links und geschlossene Kreise den Lauf einfangen und das Ergebnis zerstören.

Worauf sich der Langzeitverlauf einpendelt 🖖

Jede Zeile der Übergangsmatrix ist einfach eine Menge von Wahrscheinlichkeiten: Wenn du in einem Zustand bist, wie wahrscheinlich springst du im nächsten Schritt in jeden anderen. Multipliziere deinen aktuellen Wahrscheinlichkeitsvektor pro Schritt einmal mit P, und die Zahlen driften auf eine feste Mischung zu, die stationäre Verteilung π. Diese Mischung zeigt den Zeitanteil, den das System langfristig in jedem Zustand verbringt — probiere das Wetter-Beispiel und beobachte, wie sich p(k) einpendelt.

Ein eindeutiges Ziel, das nie erreicht wird 🖖

Setze die Zwei-Zustands-Matrix auf [[0,1],[1,0]] — eine Münze, die immer umschlägt. Sie besitzt eine völlig gültige, eindeutige stationäre Verteilung π = (0.5, 0.5), doch startet man bei (1, 0), springt p(k) für immer 1,0 → 0,1 → 1,0 und konvergiert nie. Genau solche periodischen Ketten sind der Grund, warum der Explorer converged: no melden kann; garantierte Konvergenz braucht eine aperiodische Kette, nicht nur ein eindeutiges π.

Übung

Prüfe dich selbst

Sage die Antwort zuerst voraus und probiere es dann oben aus. Zeige die Lösung erst, wenn du dich entschieden hast — genau das macht es zur Übung.

Standardmäßig startet die Kette mit Sicherheit in Zustand 1, p(0) = (1, 0, 0). Ändere das auf (0, 0, 1), sodass sie stattdessen in Zustand 3 beginnt. Sag vorher, welche Anzeigen sich ändern und welche nicht.

Antwort anzeigen

p(k) und der Abstand ändern sich; π und die Iterationszahl nicht. Von Zustand 1 aus erreichen acht Schritte 0.659852, 0.218714, 0.121436, ein Abstand von 0.08893. Von Zustand 3 aus erreichen sie 0.522304, 0.255274, 0.222421, ein Abstand von 0.18616 — weiter entfernt, denn Zustand 3 ist das seltenste Ziel. Beide Male zeigt π nach denselben 83 Iterationen 0.615385, 0.230769, 0.153846. Der Startpunkt entscheidet, wie weit die Kette ist, nie wohin sie läuft: In πP = π kommt nur die Matrix vor.
Zurück zu (1, 0, 0), und erhöhe nun die Schrittzahl. Nach wie vielen Schritten zeigt der Abstand zur Stationarität 0 — und ist die Kette dann angekommen?

Antwort anzeigen

Bei k = 80 steht dort 0, und nein, sie ist es nicht. Schon bei k = 40 beträgt der Abstand 0.000024; die sechs Nachkommastellen der Anzeige gehen einfach vor der Lücke aus. Diese Kette nähert sich π geometrisch und erreicht es in endlich vielen Schritten nie, die 0 ist also die Rundung der Anzeige — aus demselben Grund ist auch π selbst als Schätzwert ausgewiesen. Vergleiche k = 8, wo der Abstand 0.08893 ist und der Hinweis noch sagt, die Kette sei nicht durchmischt.

Aufgabe vollständig gelöst

Acht Schritte einer Kette mit drei Zuständen, gestartet in Zustand 1 5 Schritte
Eine Kette mit drei Zuständen, vollständig in Zustand 1 gestartet und über acht Schritte ausgeführt. Bestimmen Sie, wohin sie strebt und wie weit sie noch vom Ziel entfernt ist.
1. Ein Schritt ist ein Vektor-Matrix-Produkt: Die Wahrscheinlichkeit, als Nächstes in Zustand j zu sein, ist die Summe über i, sich jetzt in i zu befinden und von i → j zu wechseln.
  
  $p_{k + 1} = p_{k} P, p_{0} = (1, 0, 0)$
2. Acht solche Schritte ergeben die in der Anzeige dargestellte Verteilung. Auf Zustand 1 entfallen nach wie vor zwei Drittel der Wahrscheinlichkeit – viel, wenn man bedenkt, dass die Kette dort mit Sicherheit gestartet ist.
  
  $p_{8} = (0.65985, 0.218714, 0.121436)$
3. Das Ziel ist die stationäre Verteilung – jene, die durch einen Schritt unverändert bleibt. Das Lösen von πP = π mit der Bedingung, dass sich die Wahrscheinlichkeiten zu 1 aufsummieren, liefert exakte Brüche, Achtel und Dreizehntel, keine Dezimalbrüche.
  
  $π P = π, \sum π_{i} = 1 ⟹ π = (\frac{8}{13}, \frac{3}{13}, \frac{2}{13}) = (0.615385, 0.230769, 0.153846)$
4. Der Vergleich der beiden ergibt den von der Anzeige gemeldeten Abstand, und dieser ist nicht klein: Nach acht Schritten ist die Kette insgesamt noch etwa 0,089 entfernt.
  
  $∥ p_{8} - π ∥_{1} = 0.04447 + 0.01206 + 0.03241 = 0.08893$
5. Diese Lücke schrumpft geometrisch, bestimmt durch den zweitgrößten Eigenwert von P. Geometrischer Zerfall bedeutet, dass sie sich in einer festen Anzahl von Schritten halbiert und in endlich vielen Schritten niemals Null erreicht.
  
  $the gap shrinks like ∣ λ_{2} ∣^{k} — geometric, never zero$
Antwort

Das Werkzeug gibt nach acht Schritten 0,65985, 0,218714, 0,121436 aus, immer noch 0,08893 von der Stationarität entfernt. Die stationäre Verteilung lautet exakt (8/13, 3/13, 2/13), und festzuhalten bleibt, dass sie nicht davon abhängt, wo man gestartet ist: Dieselben drei Brüche bilden den Grenzwert für jede Startverteilung, was sie zu einer Eigenschaft der Übergangsmatrix und nicht dieses speziellen Durchlaufs macht. Diese Unabhängigkeit macht stationäre Verteilungen so nützlich: PageRank, MCMC-Stichprobenziehung und die Belegung von Warteschlangen beruhen alle darauf, dass das langfristige Ergebnis allein eine Eigenschaft der Übergangsregeln ist. Nur die Zeit, die benötigt wird, um dorthin zu gelangen, hängt vom Start ab.

$π = (\frac{8}{13}, \frac{3}{13}, \frac{2}{13}) is where it goes, and p_{0} does not matter$

Quellen (1)

The stationary distribution put to work on the whole web, damping factor and all: S. Brin & L. Page, “The anatomy of a large-scale hypertextual Web search engine.” Computer Networks and ISDN Systems 30, 107–117, 1998.

Vom 42Math-Team · Aktualisiert 2026-07-26

Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen. Redaktionsrichtlinie · Korrekturen

Alle Lektionen: Mathematik →

Beispielaufgaben

ergodische 3-Zustands-Kette - Nach acht Schritten steht auf der Anzeige immer noch ein L1-Abstand von 0,08893. Die stationäre Verteilung, auf die sich das System einpendelt – 0,615385, 0,230769, 0,153846 –, beträgt exakt 8/13, 3/13 und 2/13. Eine in Zehnteln geschriebene Matrix hat also einen Fixpunkt in Dreizehnteln, da sich π durch das Lösen von πP = π ergibt und nicht aus den von dir eingetippten Zahlen.
Wetter, 2 Zustände - 0,666667 und 0,333333, und bei einer Kette mit zwei Zuständen musst du dafür niemals iterieren. π ergibt sich aus den beiden vertauschten und normierten Wahrscheinlichkeiten abseits der Hauptdiagonalen: 0,4 / (0,2 + 0,4) = 2/3. Ausgehend von einem 50/50-Start weichst du nach zehn Schritten nur noch um 0,000035 davon ab.
langsam mischende 3-Zustands-Kette - Dreißig Schritte hinterlassen hier einen L1-Abstand von 0,081995. Das ist über zweitausendmal weiter von der Stationarität entfernt als der Wert, den die Wetter-Kette in zehn Schritten erreicht hat. Der Grund dafür liegt auf der Hauptdiagonalen: 0,97, 0,94 und 0,96. Die Kette verlässt ihren aktuellen Zustand also so gut wie nie. Im Gegensatz zu den 25 der Wetter-Kette waren hier 493 Potenziterationen nötig, und π ist 4/11, 4/11, 3/11.