Übergangsmatrizen

Eine Übergangsmatrix, auch Übergangsmatrix oder Markov-Matrix genannt, beschreibt die Wahrscheinlichkeiten, mit denen ein Prozess von einem Zustand in den nächsten wechselt. Für einen endlichen Zustandsraum S = {1, …, N} seien p_ij die Wahrscheinlichkeiten P(X_{t+1} = j | X_t = i). Dann ist P eine N×N-Matrix mit nicht-negativen Einträgen und Zeilenstochastizität: Die Summe der Einträge jeder Zeile ergibt 1. Die Konvention bevorzugt die Darstellung, bei der der Zustand i in der Zeile und der zukünftige Zustand j in der Spalte steht, sodass sich die Verteilung zu Zeitpunkt t durch p^{(t+1)} = p^{(t)} P ergibt, wobei p^{(t)} eine Zeilenverteilung ist.

Manche Lehrbücher verwenden stattdessen eine spaltenstochastische Matrix, bei der die Spalten die Wahrscheinlichkeiten summieren und die Verteilung durch p^{(t+1)} = P^T p^{(t)} entwickelt wird.

Eigenschaften und Konzepte: Ist P zeilenstochastisch, beschreibt p^{(t)} die Wahrscheinlichkeiten der Zustände nach t Schritten. Eine Stationärverteilung π erfüllt π = π P (bzw. P^T π = π) und ∑_i π_i = 1. Unter Irreduzibilität und Aperiodizität konvergiert P^n gegen eine Matrix, deren alle Zeilen gleich π. Die Stationärverteilung ist ein Eigenvektor der Eigenwert 1.

Beispiel: P = [[0.8, 0.2], [0.3, 0.7]]. Die Stationärverteilung ist π = (0.6, 0.4). Anwendungen finden sich in Markov-Ketten-Modellierung, Warteschlangen, Zuverlässigkeit und Ranking-Verfahren, wo die Entwicklung von Wahrscheinlichkeiten durch p^{(t)} = p^{(0)} P^t beschrieben wird.