Übergangsmatrix

Grundidee und Definition

Eine Übergangsmatrix, auch Prozessmatrix oder stochastische Matrix genannt, beschreibt Übergangswahrscheinlichkeiten in Markow-Ketten. Eine Markow-Kette ist ein System, dessen zukünftiger Zustand – bezogen auf den nächsten Schritt – durch den aktuellen Zustand beschrieben wird. Mithilfe der Übergangsmatrix lassen sich künftige Entwicklungen und Wahrscheinlichkeitsverteilungen vorausberechnen.

Im Artikel werden nur quadratische Matrizen im Sinn der Linearen Algebra betrachtet. Eine Übergangsmatrix ist eine quadratische Matrix, deren Einträge zwischen 0 und 1 liegen und deren Zeilen- oder Spaltensummen Eins betragen. Prozessmatrizen dienen ebenfalls zur Berechnung dynamischer Entwicklungen, müssen aber keine Zeilen- beziehungsweise Spaltensummen von 1 besitzen.

In der Theorie der Markow-Ketten gibt es auch unendlichdimensionale Übergangsmatrizen; diese werden hier nicht behandelt.

Arten und grundlegende Eigenschaften

Man unterscheidet drei wichtige Formen:

• Eine Matrix ist zeilenstochastisch, wenn alle Einträge zwischen 0 und 1 liegen und jede Zeilensumme 1 ergibt.
• Eine Matrix ist spaltenstochastisch, wenn alle Einträge zwischen 0 und 1 liegen und jede Spaltensumme 1 ergibt.
• Eine Matrix ist doppelt-stochastisch, wenn sie sowohl zeilen- als auch spaltenstochastisch ist.

Äquivalent besteht eine zeilen- beziehungsweise spaltenstochastische Matrix zeilen- beziehungsweise spaltenweise aus Wahrscheinlichkeitsvektoren. Matrizen mit Einträgen zwischen 0 und 1, deren Zeilen- oder Spaltensummen kleiner als 1 sind, werden teilweise substochastisch genannt. In der Stochastik sind fast ausschließlich zeilenstochastische Matrizen gebräuchlich. Die Unterscheidung zwischen Zeilen- und Spaltenstochastik ist allgemein wenig gebräuchlich, weil beide Formen durch Transponierung ineinander übergehen.

Die Menge der Übergangsmatrizen ist konvex: Sind P und Q zeilen- beziehungsweise spaltenstochastisch, so ist λP + (1 − λ)Q für jedes λ ∈ [0,1] ebenfalls zeilen- beziehungsweise spaltenstochastisch. Für eine zeilenstochastische Matrix beträgt die Zeilensummennorm 1, für eine spaltenstochastische Matrix die Spaltensummennorm 1. Außerdem sind Übergangsmatrizen bezüglich der Matrixmultiplikation abgeschlossen: Sind A und B spalten- beziehungsweise zeilenstochastisch, so ist auch A · B eine spalten- beziehungsweise zeilenstochastische Matrix.

Eigenwerte und stationäre Verteilungen

Der Eigenwert 1 besitzt für stochastische Matrizen eine besondere Bedeutung. Ein Eigenvektor zum Eigenwert λ = 1 entspricht – bei der passenden Darstellung – einer stationären Verteilung der Markow-Kette. Eine stationäre Verteilung verändert sich durch einen weiteren Übergang nicht.

Für eine zeilenstochastische Matrix P gilt mit der Zeilensummennorm ||P||∞ = 1. Da der Spektralradius einer Matrix höchstens so groß wie ihre Norm ist, haben alle Eigenwerte einen Betrag von höchstens 1. Ist 1 der Einsvektor, also ein Vektor, dessen Einträge sämtlich 1 sind, dann gilt P1 = 1. Damit ist 1 stets ein Eigenwert und zugleich immer ein betragsgrößter Eigenwert. Der Eigenwert 1 ist außerdem stets halbeinfach.

Nach dem Satz von Perron-Frobenius gilt: Ist die stochastische Matrix irreduzibel, so ist die Dimension des zum Eigenwert 1 gehörenden Eigenraums gleich 1. Insbesondere gilt dies, wenn alle Einträge der stochastischen Matrix echt größer als 0 sind.

Für eine 3×3-Übergangsmatrix P mit der Spur S := Spur(P) und der Determinante D := det(P) lautet das charakteristische Polynom:

χA(λ) = λ³ − S·λ² + (S + D − 1)·λ − D = (λ − 1)·(λ² − (S − 1)·λ + D).

Daraus folgt erneut, dass λ = 1 unabhängig von der Wahl der Koeffizienten von P stets ein Eigenwert ist. Die beiden anderen Eigenwerte können mit der p-q-Formel berechnet werden.

Übergangsmatrizen bei Markow-Ketten

Eine zeilenstochastische Matrix P charakterisiert eine zeitinvariante Markow-Kette mit endlichem Zustandsraum. Der Eintrag pij ist die Übergangswahrscheinlichkeit vom Zustand i in den Zustand j:

pij := P(Xt+1 = j | Xt = i).

Der Wahrscheinlichkeitsvektor x0 = (a1, a2, …, an) ist ein Zeilenvektor und beschreibt die Wahrscheinlichkeiten der Zustände zum Zeitpunkt 0. Dabei ist ai die Wahrscheinlichkeit, sich zu diesem Zeitpunkt im Zustand i zu befinden. Die Entwicklung wird durch

x0 · P = x1,

xk · P = xk+1

beschrieben. Für einen beliebigen Zeitpunkt k gilt daher

x0 · Pᵏ = xk.

Die Linkseigenvektoren von P zum Eigenwert λ = 1 stellen die stationären Verteilungen dar. Bei spaltenstochastischen Matrizen verwendet man entsprechend Spaltenvektoren, die von rechts mit der Matrix multipliziert werden; dann erhält man gewöhnliche Eigenvektoren. Alternativ kann man die Matrix transponieren.

Die Übergangsmatrix enthält weitere Informationen über die Markow-Kette:

• Gilt pᵢⱼⁿ > 0 für ein n ∈ ℕ, dann ist der Zustand j vom Zustand i aus erreichbar.
• Gilt zusätzlich pⱼᵢᵐ > 0 für ein m ∈ ℕ, dann kommunizieren die Zustände i und j.
• Bei einer homogenen Markow-Kette mit endlichem Zustandsraum ist Irreduzibilität der Markow-Kette gleichbedeutend mit Irreduzibilität der Übergangsmatrix.
• Gilt Pⁿ > 0 für ein n ∈ ℕ, dann ist die Kette irreduzibel und aperiodisch und konvergiert gegen eine Grenzverteilung. Dieses Kriterium ist häufig leichter zu prüfen als Irreduzibilität und Aperiodizität getrennt.
• Die Chapman-Kolmogorow-Gleichung entspricht bei Übergangsmatrizen einer komponentenweise ausgeschriebenen Matrixmultiplikation.

Eine Anwendung ist der PageRank mithilfe der Google-Matrix. Zustände entsprechen Webseiten, und die Übergangswahrscheinlichkeiten geben an, mit welcher Wahrscheinlichkeit ein Nutzer auf einen Link klickt. Die Grenzverteilung beschreibt die relative Häufigkeit, mit der der Nutzer auf eine Webseite stößt, und dient damit als Maß für ihre Wichtigkeit. Rechtseigenvektoren zum Eigenwert 1 können bei passender Normierung außerdem Absorptionswahrscheinlichkeiten in einem absorbierenden Zustand darstellen.

Kniffel als Übergangsprozess

Beim Kniffel (Yahtzee) sollen mit 5 Würfeln innerhalb von höchstens 3 Würfen fünf gleiche Augenzahlen erzielt werden. Vor dem zweiten und dritten Wurf werden jeweils die Würfel mit einer oder der häufigsten Augenzahl behalten; alle anderen Würfel werden erneut geworfen. Diese Strategie ist optimal, um die Wahrscheinlichkeit für einen Kniffel zu maximieren.

Die möglichen Ergebnisse der fünf Würfel werden in fünf Zustandsklassen zusammengefasst, wobei A, B, C, D und E verschiedene Augenzahlen bedeuten:

• fünf verschiedene Augenzahlen: ABCDE;
• einmal oder zweimal zwei gleiche Augenzahlen: AABCD oder AABBC;
• drei gleiche Augenzahlen: AAABC oder AAABB;
• vier gleiche Augenzahlen: AAAAB;
• fünf gleiche Augenzahlen: AAAAA.

Der Startvektor nach dem ersten Wurf lautet in dieser Reihenfolge:

x0 = (720/7776, 5400/7776, 1500/7776, 150/7776, 6/7776)ᵀ.

Die Nennergebnisse beruhen auf insgesamt 6⁵ = 7776 möglichen Variationen mit Wiederholung. Die Übergangswahrscheinlichkeiten für den nächsten Wurf werden durch die spaltenstochastische Matrix

P = ((120/1296, 0, 0, 0, 0), (900/1296, 120/216, 0, 0, 0), (250/1296, 80/216, 25/36, 0, 0), (25/1296, 15/216, 10/36, 5/6, 0), (1/1296, 1/216, 1/36, 1/6, 1))

dargestellt. Beispielsweise ist p₂,₁ = 900/1296 die Wahrscheinlichkeit, nach einem ersten Wurf mit fünf verschiedenen Augenzahlen im zweiten Wurf die Klasse AABCD oder AABBC zu erreichen. Bei den Berechnungen können Fallunterscheidungen nötig sein, weil die häufigste Augenzahl nach dem zweiten Wurf eine andere sein kann als nach dem ersten Wurf.

Nach zwei Würfen gilt x1 = P · x0, nach drei Würfen x2 = P² · x0. Allgemein ist der Vektor nach k Würfen xk−1 = Pᵏ⁻¹ · x0. Sein letztes Element ist die Wahrscheinlichkeit für einen Kniffel. Sie beträgt nach 1, 2, 3, 4, 5, 6, 7, 8, 9 und 10 Würfen jeweils 0,00077; 0,01263; 0,04603; 0,10058; 0,17051; 0,24908; 0,33050; 0,41044; 0,48601 und 0,55553. Nach dem zehnten Wurf ist sie erstmals größer als 1/2.

Ratte und Katze-Maus-Spiel

Bei der Ratte im Zimmer gibt es drei Zustände: Käfig (Zustand 1), hinter dem Schrank (Zustand 2) und unter dem Schreibtisch (Zustand 3). Alle 5 Minuten wechselt die Ratte ihren Ort. Die spaltenstochastische Übergangsmatrix lautet

P = ((0,05, 0,1, 0,1), (0,4, 0,7, 0,8), (0,55, 0,2, 0,1)).

Die Spalten beschreiben dabei den jeweiligen Ausgangszustand. Aus dem Käfig bleibt die Ratte mit Wahrscheinlichkeit 0,05 dort, geht mit Wahrscheinlichkeit 0,4 hinter den Schrank und mit Wahrscheinlichkeit 0,55 unter den Schreibtisch. Aus dem Zustand hinter dem Schrank gelten die Wahrscheinlichkeiten 0,7 für das Bleiben, 0,2 für den Weg unter den Schreibtisch und 0,1 für den Weg in den Käfig. Unter dem Schreibtisch bleibt sie mit Wahrscheinlichkeit 0,1, geht mit Wahrscheinlichkeit 0,1 in den Käfig und flüchtet mit Wahrscheinlichkeit 0,8 hinter den Schrank.

Startet die Ratte sicher im Käfig, ist x0 = (1, 0, 0)ᵀ. Nach 20 Minuten, also nach 4 Zeitschritten, ergibt sich gerundet

x4 = P⁴ · x0 = (0,0952, 0,6933, 0,2115)ᵀ.

Die Wahrscheinlichkeit, dass sie dann im Käfig ist, beträgt 0,0952. Nach längerer Zeit kann man das Gleichgewicht durch einen Rechtseigenvektor zum Eigenwert 1 beschreiben. Dieser lautet gerundet x = (0,0952, 0,6926, 0,2121)ᵀ. Daher sollte Peter zuerst hinter dem Schrank suchen.

Im Katze-Maus-Beispiel gibt es fünf nebeneinanderliegende Boxen. Die Katze startet in Box 1, die Maus in Box 5; beide wechseln nach einer festen Zeit zufällig in eine Nachbarbox. Das Spiel endet, sobald beide in derselben Box sind. Wegen der Bewegungsregeln sind die möglichen Zustände (1,3), (1,5), (2,4), (3,5) und das Spielende (2,2), (3,3) oder (4,4). Mit einer spaltenstochastischen Matrix werden Übergänge zwischen diesen fünf Zuständen beschrieben.

Beispiel: Vom Zustand (1,5) gelangt das System sicher in den Zustand (2,4), also gilt p₃,₂ = 1. Vom Zustand (2,4) führen vier mögliche Übergänge jeweils mit Wahrscheinlichkeit 1/4 in die anderen Zustände. Im Spielende bleibt das System mit p₅,₅ = 1. Alle übrigen Hauptdiagonal-Einträge sind 0, weil sich der Zustand vor dem Spielende nicht unverändert halten kann.