Markow-Kette — Übergangsmatrix & Anwendungen

Eine Markow-Kette ist ein Modell für ein System, das sich Schritt für Schritt zwischen Zuständen bewegt, zum Beispiel zwischen sonnig und regnerisch. Die zentrale Regel ist, dass der nächste Schritt nur vom aktuellen Zustand abhängt, sofern das für das System, das du modellierst, eine sinnvolle Annahme ist.

Diese Ein-Schritt-Wahrscheinlichkeiten werden in einer Übergangsmatrix gesammelt. Wenn sich der Prozess jetzt im Zustand $i$ befindet und als Nächstes mit Wahrscheinlichkeit $P_{ij}$ in den Zustand $j$ übergeht, dann gilt

$$P = (P_{ij})$$

Für eine endliche Markow-Kette ergibt jede Zeile von $P$ in der Summe $1$, weil der Prozess in einen der erlaubten Folgezustände übergehen muss.

Was die Markow-Eigenschaft bedeutet

Die formale Aussage ist

$$P(X_{n+1} = j \mid X_n = i, X_{n-1}, \ldots, X_0) = P(X_{n+1} = j \mid X_n = i)$$

Das bedeutet: Sobald du den aktuellen Zustand $X_n = i$ kennst, verändert die ältere Vorgeschichte im Modell die Wahrscheinlichkeit für den nächsten Schritt nicht mehr.

Diese Bedingung ist wichtig. Manche realen Systeme haben Gedächtnis, Trends oder verzögerte Effekte, daher passt eine Markow-Kette nur dann gut, wenn „der aktuelle Zustand reicht aus“ eine sinnvolle Näherung ist.

So liest man eine Übergangsmatrix

Angenommen, ein einfaches Wettermodell hat zwei Zustände:

• Sonnig
• Regnerisch

Verwende diese Übergangsmatrix:

$$P = \begin{bmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{bmatrix}$$

Lies jede Zeile als aktuellen Zustand und jede Spalte als nächsten Zustand.

Wenn heute also sonnig ist, sagt das Modell, dass es morgen mit Wahrscheinlichkeit $0.8$ sonnig und mit Wahrscheinlichkeit $0.2$ regnerisch ist. Wenn heute regnerisch ist, ist es morgen mit Wahrscheinlichkeit $0.4$ sonnig und mit Wahrscheinlichkeit $0.6$ regnerisch.

Durchgerechnetes Beispiel: Wetter über zwei Tage

Angenommen, die heutige Verteilung ist

$$\mathbf{v}_0 = \begin{bmatrix} 1 & 0 \end{bmatrix}$$

Das bedeutet, dass das Modell mit Wahrscheinlichkeit $1$ im Zustand Sonnig startet.

Die Verteilung für morgen ist

$$\mathbf{v}_1 = \mathbf{v}_0 P = \begin{bmatrix} 1 & 0 \end{bmatrix} \begin{bmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{bmatrix} = \begin{bmatrix} 0.8 & 0.2 \end{bmatrix}$$

Nach einem Schritt ergibt das Modell also eine Wahrscheinlichkeit von $80\%$ für Sonnig und $20\%$ für Regnerisch.

Nach einem weiteren Schritt gilt

$$\mathbf{v}_2 = \mathbf{v}_1 P = \begin{bmatrix} 0.8 & 0.2 \end{bmatrix} \begin{bmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{bmatrix} = \begin{bmatrix} 0.72 & 0.28 \end{bmatrix}$$

Jetzt beträgt die Wahrscheinlichkeit für Sonnig $0.72$ und für Regnerisch $0.28$.

Der Punkt ist nicht nur die Rechnung. Die Matrix aktualisiert die gesamte Wahrscheinlichkeitsverteilung Schritt für Schritt, und genau deshalb sind Markow-Ketten für wiederholte Prozesse nützlich.

Wo Markow-Ketten verwendet werden

Markow-Ketten sind nützlich, wenn sich ein System stufenweise verändert und du Wahrscheinlichkeiten dafür bestimmen möchtest, was als Nächstes passiert.

Häufige Beispiele sind Wettermodelle, Bewegungen in Brettspielen, Warteschlangenmodelle und vereinfachte Webnavigation. In jedem Fall hilft das Modell nur dann, wenn die Zustände gut gewählt sind und die Übergangswahrscheinlichkeiten realistisch sind.

Häufige Fehler bei Markow-Ketten

Jeden Zufallsprozess als Markow-Prozess behandeln

Ein Prozess ist nicht automatisch eine Markow-Kette, nur weil er zufällig ist. Das Modell setzt voraus, dass das Verhalten im nächsten Schritt durch den aktuellen Zustand bestimmt wird, so wie du die Zustände definiert hast.

Vergessen, was die Zeilen bedeuten

Zeilen und Spalten werden oft verwechselt. Du brauchst eine einheitliche Konvention. Auf dieser Seite sind die Zeilen die aktuellen Zustände und die Spalten die nächsten Zustände.

Ungültige Wahrscheinlichkeiten verwenden

Jeder Eintrag muss zwischen $0$ und $1$ liegen, und jede Zeile muss bei einer üblichen Übergangsmatrix einer endlichen Markow-Kette die Summe $1$ ergeben.

Annehmen, dass das Modell eine einzige sichere Zukunft vorhersagt

Eine Markow-Kette liefert in der Regel Wahrscheinlichkeiten, keine Gewissheit. Auch wenn ein Zustand wahrscheinlicher ist, können mehrere nächste Zustände weiterhin möglich sein.

Das Langzeitverhalten hängt von der Kette ab

Manche Markow-Ketten nähern sich einer stabilen Verteilung im langen Verlauf an, die oft stationäre Verteilung genannt wird. Das passiert aber nicht bei jeder Kette, und die Details hängen von Eigenschaften der Kette ab, etwa davon, wie Zustände miteinander kommunizieren und ob das Bewegungsmuster periodisch ist.

Deshalb ist es sinnvoll, die wiederholte Multiplikation mit $P$ als Methode zur Untersuchung des Langzeitverhaltens zu sehen, aber du solltest Konvergenz nicht ohne Prüfung der Bedingungen voraussetzen.

Wann eine Markow-Kette ein gutes Modell ist

Verwende eine Markow-Kette, wenn all das einigermaßen zutrifft:

• Der Prozess lässt sich durch eine überschaubare Menge von Zuständen beschreiben.
• Die Zeit verläuft in diskreten Schritten, oder du hast dich entschieden, sie so zu modellieren.
• Die Wahrscheinlichkeiten für den nächsten Schritt werden sinnvoll durch den aktuellen Zustand bestimmt.

Wenn diese Bedingungen nicht erfüllt sind, kann das Modell immer noch eine grobe Näherung sein, aber das solltest du ausdrücklich sagen.

Probiere deine eigene Version aus

Erstelle ein Modell mit drei Zuständen, zum Beispiel niedrige, mittlere und hohe Nachfrage. Wähle Zeilenwahrscheinlichkeiten, die jeweils die Summe $1$ ergeben, lege eine Anfangsverteilung fest und berechne den nächsten Schritt mit $\mathbf{v}_{n+1} = \mathbf{v}_n P$. Wenn du weitergehen möchtest, probiere eine zweite Aktualisierung aus und prüfe, ob sich die Verteilung auf ein Muster einzupendeln beginnt.