Übergangsmatrix

In der Mathematik, besonders der Wahrscheinlichkeitstheorie und Statistik, bezeichnet eine Übergangsmatrix (auch Prozess- oder manchmal Stochastische Matrix) eine quadratische Matrix, deren Zeilen- oder Spaltensummen Eins betragen und deren Elemente zwischen Null und Eins liegen. Die Übergangswahrscheinlichkeiten einer diskreten Markow-Kette können durch eine Übergangsmatrix ausgedrückt werden.

Weitere Unterscheidung

• Eine Übergangsmatrix heißt zeilenstochastisch, wenn alle Einträge der Matrix zwischen 0 und 1 liegen und die Zeilensummen 1 ergeben.

• Eine Übergangsmatrix heißt spaltenstochastisch, wenn alle Einträge der Matrix zwischen 0 und 1 liegen und die Spaltensummen 1 ergeben.

• Eine Übergangsmatrix heißt doppelt-stochastisch, wenn sie sowohl zeilen- als auch spaltenstochastisch ist.

Teilweise werden Matrizen mit Einträgen zwischen 0 und 1, deren Zeilensummen (bzw. Spaltensummen) kleiner als 1 sind, auch als 'substochastisch' bezeichnet. In der Stochastik sind fast ausschließlich zeilenstochastische Matrizen gebräuchlich. Die Unterscheidung ist aber i. A. wenig gebräuchlich, da die Matrizen durch Transponierung ineinander übergehen.

Eigenwerten und Eigenvektoren

Den Eigenwerte und Eigenvektoren einer stochastischen Matrix kommt in der Stochastik eine besondere Rolle zu. Ist $v$ Eigenvektor zum Eigenwert $\lambda =1$ und hat der Eigenraum Dimension 1, so entspricht dies der stationären Verteilung der Markow-Kette (vgl. unten). Generell besitzt jede stochastische Matrix den Eigenwert 1. Ist z.B. $A$ zeilenstochastisch, so folgt mit der Zeilensummennorm, dass $\Vert A\Vert _{\infty }=1$. Da aber der Spektralradius einer Matrix immer kleiner als ihre Norm ist, müssen alle Eigenwerte betragsmäßig kleiner oder gleich 1 sein. Ist nun $\mathbf {1}$ ein Vektor, der nur 1 als Einträge hat, so gilt $A\mathbf {1} =\mathbf {1}$ und 1 ist Eigenwert von $A$. Der Beweis für spaltenstochastische Matrizen läuft analog, aber mit der Spaltensummennorm anstelle der Zeilensummennorm und der transponierten Matrix. Daraus folgt direkt, dass 1 auch immer betragsgrößter Eigenwert ist. Die Dimension des Eigenraumes lässt sich etwas schwerer berechnen. Mit dem Satz von Perron-Frobenius folgt

• Sind alle Einträge einer stochastischen Matrix echt größer als 0, so ist die Dimension des zum Eigenwert 1 gehörenden Eigenraumes gleich 1.

• Ist die stochastische Matrix irreduzibel, so ist die Dimension des zum Eigenwert 1 gehörenden Eigenraumes gleich 1.

Beispiel für eine Übergangsmatrix P

$P={\begin{bmatrix}0{,}5&0{,}3&0{,}2\\0{,}2&0{,}4&0{,}4\\0{,}3&0{,}3&0{,}4\end{bmatrix}}$

Das charakteristische Polynom einer $(3\times 3)$-Übergangsmatrix lässt sich sehr leicht berechnen.

Mit der Spur $S:=\operatorname {Spur} (P)$ und der Determinante $D:=\det(P)$ gilt:

${\begin{aligned}\chi _{A}(\lambda )&=\lambda ^{3}-S\cdot \lambda ^{2}+(S+D-1)\cdot \lambda -D\\&=(\lambda -1)\cdot (\lambda ^{2}-(S-1)\cdot \lambda +D)\end{aligned}}$

Aus der letzten Zeile ergibt sich, dass $\lambda =1$ stets Eigenwert der Matrix P ist, d.h. unabhängig von der Wahl der Koeffizienten von P, die anderen beiden Eigenwerte lassen sich dann gegebenenfalls bequem über die p-q-Formel errechnen.

Hieraus folgt wiederum, dass die Matrix P zumindest einen stationären Zustand hat, sowie – falls dieser eindeutig ist – eine Grenzverteilung.

Anwendung zur Charakterisierung diskreter Markow-Ketten

Ist $A$ eine zeilenstochastische Matrix, so lässt sich damit auf folgende Weise eine zeitinvariante Markow-Kette mit endlichem Zustandsraum charakterisieren:

Die Einträge $a_{ij}$ der Matrix $A$ sind genau die Übergangswahrscheinlichkeiten vom Zustand $i$ in den Zustand $j$. Ist nun $x_{0}$ ein stochastischer Vektor (also ein Vektor mit Einträgen zwischen 0 und 1, die sich zu 1 aufsummieren), dann beschreibt $x_{0}$ den Zustand des Systems zum Zeitpunkt 0 (dabei ist der $i$te Eintrag von $x_{0}$ die Aufenthaltswahrscheinlichkeit zum Zeitpunkt 0 im Zustand $i$). Die Aufenthaltswahrscheinlichkeiten zum Zeitpunkt 1 ergeben sich durch Linksmultiplikation von $A$ mit $x_{0}$:

$x_{0}^{T}A=x_{1}^{T}$

Die Aufenthaltswahrscheinlichkeiten zu einem beliebigen Zeitpunkt $k$ in Abhängigkeit vom Startzustand $x_{0}$ sind dann

$x_{0}^{T}A^{k}=x_{k}^{T}$

Eine besondere Rolle kommt den Linkseigenvektoren der Matrix $A$ zum Eigenwert $\lambda =1$ zu, denn diese stellen die Grenzverteilung der Markow-Kette nach langer Zeit dar, wenn diese eine vom Anfangszustand unabhängige ergodische Verteilung besitzt.

Für spaltenstochastische Matrizen kann man analog vorgehen, bloß dass die Vektormultiplikation von rechts durchgeführt wird und der gewöhnliche Eigenvektor zum Eigenwert 1 berechnet wird. Alternativ kann man auch die Matrix transponieren und das oben skizzierte Vorgehen nutzen.

Beispiele

Die Ratte im Zimmer

Peter besitzt eine Ratte. Ist die Ratte nicht im Käfig eingesperrt, so befindet sie sich entweder unter dem Schreibtisch (Zustand 3), hinter dem Schrank (Zustand 2) oder ist im Käfig, um zu fressen (Zustand 1). Die Ratte wechselt alle 5 Minuten ihren Ort. Ist sie gerade im Käfig, so bleibt sie mit Wahrscheinlichkeit 0.05 dort, mit Wahrscheinlichkeit 0.4 geht sie hinter den Schrank und mit Wahrscheinlichkeit 0.55 unter den Schreibtisch. Ist sie hinter dem Schrank, so bleibt sie mit Wahrscheinlichkeit 0.7 dort, mit Wahrscheinlichkeit 0.2 geht sie unter den Schreibtisch und mit Wahrscheinlichkeit 0.1 geht sie in den Käfig. Ist sie unter dem Schreibtisch, so bleibt sie mit Wahrscheinlichkeit 0.1 dort, mit Wahrscheinlichkeit 0.1 geht sie in den Käfig und mit Wahrscheinlichkeit 0.8 flüchtet sie hinter den Schrank. Das Verhalten der Ratte wird durch die zeilenstochastische Matrix $P$ beschrieben:

$P={\begin{pmatrix}0.05&0.4&0.55\\0.1&0.7&0.2\\0.1&0.8&0.1\end{pmatrix}}$

Peter lässt nun seine Ratte frei und will wissen, mit welcher Wahrscheinlichkeit sich die Ratte nach 20 Minuten im Käfig befindet. Der Startzustand des Systems ist

$x_{0}=(1,0,0)^{T}$

(die Ratte befindet sich mit Wahrscheinlichkeit 1 im Käfig). Der Zustand nach 20 Minuten (nach 4 Zeitschritten) ist dann

$x_{4}^{T}=x_{0}^{T}P^{4}=(0.0952,0.6933,0.2115)$

Die Ratte befindet sich also mit Wahrscheinlichkeit 0.0952 im Käfig.

Peter fährt über das Wochenende in den Urlaub und will danach seine Ratte wieder einfangen. Nun stellt sich die Frage, wo er am besten suchen soll. Da viel Zeit vergangen ist, seit die Ratte freigelassen wurde ist die Annahme gerechtfertigt, das sich das System im Gleichgewicht befindet. Gesucht ist daher ein Linkseigenvektor von $P$ bzw. ein Rechtseigenvektor von $P^{T}$ zum Eigenwert 1. Durch Nachrechnen ergibt sich für den Eigenvektor

$x=(0.0952,0.6926,0.2121)^{T}$

Peter sollte also zuerst hinter dem Schrank suchen.

Die Katze und die Maus

Wir stellen uns vor, wir hätten fünf nebeneinander liegende Boxen, durchnummeriert von eins bis fünf, und in der ersten Box möge sich die Katze und in der letzten die Maus befinden. Nach einer festen Rundenzeit wechseln die Tiere zufällig in eine Nachbarbox. Das makabre Spiel hat ein Ende, wenn die Katze in einer Box auf die Maus trifft. Wir bezeichnen die möglichen Zustände mit (i,j), d. h. die Katze ist in der i-ten und die Maus in der j-ten Box. Wir sehen sofort, dass wenn i gerade (ungerade) ist, j ebenfalls gerade (ungerade) sein muss. Sofort ist auch klar, dass $i\leq j$ gelten muss. Die Markow-Kette, die dieses Spiel beschreibt, hat also die folgenden fünf Zustände:

• (1,3)
• (1,5)
• (2,4)
• (3,5)
• Spielende (2,2), (3,3) und (4,4).

Der Vektor $v$ gebe an, welcher dieser fünf Zustände vorliegt. Beispielsweise steht $v=[1,0,0,0,0]$ für den ersten Zustand unserer Auflistung, also $(1,3)$, und $v=[0,0,0,0,1]$ für den letzten, also das Spielende (egal, in welcher Box).

Die Übergangsmatrix A dazu ist nun

$A={\begin{bmatrix}0&0&1/4&0&0\\0&0&1/4&0&0\\1/2&1&0&1/2&0\\0&0&1/4&0&0\\1/2&0&1/4&1/2&1\end{bmatrix}}.$

Wenn wir beispielsweise wie zu Beginn im 2. Zustand $v=[0,1,0,0,0]$ sind, dann wechseln wir mit Sicherheit in den 3. Zustand $v=[0,0,1,0,0]$, also Katze in der zweiten und Maus in der vierten Box. Daher ist in der Übergangsmatrix die Position in der 2. Spalte und 3. Zeile gleich eins.

Von diesem Zustand ausgehend kommen wir nun aber mit 25 % Wahrscheinlichkeit in einen der anderen vier Zustände, daher sind alle Zeilen in der 3. Spalte gleich 1/4 (außer die 3. Zeile – der Zustand kann nicht derselbe bleiben).

Siehe auch

• Übergangstabelle

Literatur

• Hans-Otto Georgii: Stochastik: Einführung in die Wahrscheinlichkeitstheorie und Statistik. 4. Auflage. de Gruyter Lehrbuch, Berlin 2009, ISBN 978-3-11-021526-7, Kap. 6.
• Peter Knabner, Wolf Barth: Lineare Algebra: Grundlagen und Anwendungen. 1. Auflage. Springer Spektrum, Berlin Heidelberg 2012, ISBN 978-3-642-32185-6.