Übergangsmatrix einer Markow-Kette

Oberstufe

\vec{v}_{n+1} = A \cdot \vec{v}_n, \qquad \vec{v}_n = A^n \cdot \vec{v}_0

Voraussetzung: $a_{ij} \geq 0,$ $jede Spaltensumme von$ $A$ $ist$ $1$

$A$: Übergangsmatrix; a_ij ist die Wahrscheinlichkeit, in einem Schritt von Zustand j nach Zustand i zu wechseln
$a_{ij}$: Eintrag in Zeile i und Spalte j der Übergangsmatrix
$\vec{v}_n$: Zustandsvektor nach n Schritten, enthält die Wahrscheinlichkeiten (oder Anteile) der Zustände
$\vec{v}_0$: Startvektor
$n$: Anzahl der Schritte

Die Übergangsmatrix einer Markow-Kette berechnet aus der aktuellen Verteilung auf die Zustände die Verteilung nach dem nächsten Schritt.

Erklärung

Eine Markow-Kette beschreibt einen Vorgang, der sich schrittweise zwischen endlich vielen Zuständen bewegt, z.B. Kunden zwischen zwei Anbietern oder Wetterlagen von Tag zu Tag. Entscheidend ist die Markow-Eigenschaft: Die Wahrscheinlichkeit für den nächsten Zustand hängt nur vom aktuellen Zustand ab, nicht von der Vorgeschichte.

Die Übergangswahrscheinlichkeiten stehen in der Übergangsmatrix $A$ . In der hier verwendeten Schreibweise steht in Spalte $j$ , wohin man von Zustand $j$ aus wechselt. Deshalb ist jede Spaltensumme $1$ (stochastische Matrix). Der Zustandsvektor $\vec{v}_n$ enthält die Wahrscheinlichkeiten der Zustände nach $n$ Schritten. Ein Schritt ist eine Matrix-Vektor-Multiplikation, $n$ Schritte entsprechen der Matrixpotenz $A^n$ .

Der Eintrag $(A^n)_{ij}$ ist die Wahrscheinlichkeit, in $n$ Schritten von $j$ nach $i$ zu gelangen. Die Wahrscheinlichkeit eines bestimmten Pfades ist das Produkt der Übergangswahrscheinlichkeiten entlang des Pfades.

Hinweis: Viele Hochschulbücher schreiben die Wahrscheinlichkeiten in Zeilen und rechnen mit Zeilenvektoren, $\vec{v}_{n+1}^{\,T} = \vec{v}_n^{\,T} P$ . Dann ist $P = A^T$ , und die Zeilensummen sind $1$ .

Beispiele

Zwei Mobilfunkanbieter X und Y: Von den Kunden von X bleiben pro Jahr $80\,\%$ , $20\,\%$ wechseln zu Y. Von Y bleiben $70\,\%$ , $30\,\%$ wechseln zu X. Mit der Reihenfolge (X, Y):

A = \begin{pmatrix} 0{,}8 & 0{,}3 \\ 0{,}2 & 0{,}7 \end{pmatrix}

Zu Beginn haben beide je $50\,\%$ Marktanteil:

\vec{v}_1 = \begin{pmatrix} 0{,}8 & 0{,}3 \\ 0{,}2 & 0{,}7 \end{pmatrix} \begin{pmatrix} 0{,}5 \\ 0{,}5 \end{pmatrix} = \begin{pmatrix} 0{,}55 \\ 0{,}45 \end{pmatrix}, \qquad \vec{v}_2 = A \cdot \vec{v}_1 = \begin{pmatrix} 0{,}575 \\ 0{,}425 \end{pmatrix}

Dasselbe Ergebnis liefert $A^2 \cdot \vec{v}_0$ mit $A^2 = \begin{pmatrix} 0{,}7 & 0{,}45 \\ 0{,}3 & 0{,}55 \end{pmatrix}$ .

Ein Kunde von X wechselt im ersten Jahr zu Y, im zweiten zurück zu X und bleibt im dritten Jahr bei X. Die Wahrscheinlichkeit für genau diesen Pfad ist $0{,}2 \cdot 0{,}3 \cdot 0{,}8 = 0{,}048$ .

Typische Fehler

Zeilen und Spalten vertauschen. Bei der Spaltenschreibweise muss jede Spalte die Summe $1$ haben. Ist stattdessen jede Zeile $1$ , rechnet man mit Zeilenvektoren von links.
$A \cdot \vec{v}$ und $\vec{v} \cdot A$ verwechseln. Die Matrixmultiplikation ist nicht kommutativ.
$\vec{v}_n$ mit $n \cdot A \cdot \vec{v}_0$ statt $A^n \cdot \vec{v}_0$ berechnen.
Die Markow-Eigenschaft ohne Prüfung annehmen, obwohl der nächste Zustand auch von früheren Zuständen abhängt.

Übergangsmatrix einer Markow-Kette