Übergangsmatrix

In der Mathematik, besonders der Wahrscheinlichkeitstheorie und Statistik, dient eine Übergangsmatrix (auch Prozessmatrix oder stochastische Matrix) dazu, die Übergangswahrscheinlichkeiten von (diskreten und kontinuierlichen) Markow-Ketten auszudrücken. Dadurch lassen sich künftige Entwicklungen vorausberechnen. In der Theorie der Markow-Ketten werden auch unendlichdimensionale Übergangsmatrizen definiert. In diesem Artikel werden jedoch nur Matrizen im Sinne der Linearen Algebra behandelt.

Eine Übergangsmatrix ist eine quadratische Matrix, deren Zeilen- oder Spaltensummen Eins betragen und deren Elemente zwischen Null und Eins liegen.

Prozessmatrizen dienen ebenfalls zur künftigen Berechnung dynamischer Entwicklungen. Im Gegensatz zu stochastischen Matrizen müssen sie jedoch keine Zeilen- bzw. Spaltensummen von 1 haben. Sie sind jedoch wie die stochastische Matrix quadratisch.

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.

Äquivalent ist die folgende Definition: Eine Matrix heißt zeilen-(spalten-)stochastisch, wenn sie zeilen-(spalten-)weise aus Wahrscheinlichkeitsvektoren besteht.

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.

Eigenschaften

Eigenwerte und Eigenvektoren

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

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

Dies ist insbesondere der Fall, wenn die Einträge einer stochastischen Matrix echt größer als 0 sind.

Konvexität, Normen und Abgeschlossenheit

Die Menge der Übergangsmatrizen ist konvex. Sind also $P$ und $Q$ zeilen- bzw. spaltenstochastische Matrizen, so ist $\lambda P+(1-\lambda )Q$ wieder eine zeilen- bzw. spaltenstochastische Matrix für alle $\lambda \in [0,1]$.

Direkt aus der Definition folgt, dass die Zeilensummennorm einer zeilenstochastischen Matrix 1 ist, genauso wie die Spaltensummennorm einer spaltenstochastischen Matrix.

Außerdem sind Übergangsmatrizen abgeschlossen bezüglich der Matrixmultiplikation: Sind $A,B$ spalten- bzw. zeilenstochastische Matrizen, so ist $A\cdot B$ ebenfalls eine spalten- bzw. zeilenstochastische Matrix.

Beispiel

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

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, unabhängig von der Wahl der Koeffizienten von P. Die anderen beiden Eigenwerte lassen sich dann über die p-q-Formel errechnen.

Anwendung zur Charakterisierung diskreter Markow-Ketten

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

Die Einträge $p_{ij}$ der Matrix $P$ sind genau die Übergangswahrscheinlichkeiten vom Zustand $i$ in den Zustand $j$:

$p_{ij}:=P(X_{t+1}=j\mid X_{t}=i)$

Der Wahrscheinlichkeitsvektor $x_{0}=(a_{1},a_{2},\dotsc ,a_{n})$ (ein Zeilenvektor) beschreibt den Zustand des Systems zum Zeitpunkt 0 und wird manchmal Startvektor genannt. Dabei beschreibt $a_{i}$ die Wahrscheinlichkeit zum Zeitpunkt 0 im Zustand $i$ zu sein. Die Wahrscheinlichkeiten zum Zeitpunkt 1 ergeben sich durch Multiplikation der Matrix $P$ von links mit dem Zeilenvektor $x_{0}$:

$x_{0}\cdot P=x_{1}$

Allgemein ergeben sich die Wahrscheinlichkeiten zum Zeitpunkt $k+1$ durch Multiplikation der Matrix $P$ von links mit dem Zeilenvektor $x_{k}$:

$x_{k}\cdot P=x_{k+1}$

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

$x_{0}\cdot {P}^{k}=x_{k}$

Eine besondere Rolle kommt den Linkseigenvektoren der Matrix $P$ zum Eigenwert $\lambda =1$ zu, denn diese stellen die stationären Verteilungen der Markow-Kette dar.

Für spaltenstochastische Matrizen kann man analog vorgehen. Diese werden von rechts mit Spaltenvektoren multipliziert und man findet den gewöhnlichen Eigenvektor. Alternativ kann man auch die Matrix transponieren und das oben skizzierte Vorgehen nutzen.

Ein anwendungsorientiertes Beispiel für diese Verwendung von Übergangsmatrizen ist die Berechnung des PageRank mittels der Google-Matrix. Jeder Zustand entspricht dort einer Webseite im World Wide Web, die Übergangswahrscheinlichkeiten geben an, mit welcher Wahrscheinlichkeit ein Nutzer auf einen Link klickt. Die Grenzverteilung ist dann die relative Häufigkeit, mit welcher der Nutzer auf eine Webseite stößt, und damit ein Maß für die Wichtigkeit dieser Seite.

Auch die Rechtseigenvektoren einer Übergangsmatrix zum Eigenwert 1 spielen eine Rolle bei der Untersuchung von Markow-Ketten. Bei passender Normierung sind diese genau die Absorptionswahrscheinlichkeiten in einem absorbierenden Zustand.

Des Weiteren finden sich auch viele Eigenschaften einer Markow-Kette in der Übergangsmatrix wieder:

• Existiert eine Zahl $n\in \mathbb {N}$, so dass $p_{ij}^{n}>0$ ist, dann ist der Zustand j vom Zustand i aus erreichbar.
• Gilt außerdem auch $p_{ji}^{m}>0$ für ein $m\in \mathbb {N}$, so kommunizieren die Zustände i und j.
• Im Fall einer homogenen Markow-Kette mit endlichem Zustandsraum ist der Begriff der irreduziblen Markow-Kette äquivalent zur Irreduzibilität der Übergangsmatrix.
• Ist $P^{n}>0$ für ein $n\in \mathbb {N}$, so ist die Markow-Kette irreduzibel und aperiodisch und konvergiert demnach gegen eine Grenzverteilung. Dieses Kriterium ist oft leichter zu überprüfen als die Irreduzibilität und Aperiodizität separat zu zeigen.
• Die Chapman-Kolmogorow-Gleichung lässt sich im Falle einer Übergangsmatrix als komponentenweise ausgeschriebene Matrixmultiplikation interpretieren.

Beispiele

In den folgenden drei Beispiele werden spaltenstochastische Übergangsmatrizen verwendet. Dabei bezeichnet ein Eintrag $p_{ij}$ in der $i$-ten Zeile und $j$-ten Spalte einer Übergangsmatrix Matrix $P$ die Übergangswahrscheinlichkeit vom Zustand $j$ in den Zustand $i$. (Im Unterschied dazu bezeichnet bei einer Modellierung mit zeilenstochastischen Übergangsmatrizen ein Eintrag $p_{ij}$ die Übergangswahrscheinlichkeit vom Zustand $i$ in den Zustand $j$.)

Würfelspiel Kniffel (Yahtzee)

Beim Würfelspiel Kniffel (Yahtzee) werden Punkte für verschiedene Kategorien erspielt. Im Folgenden wird nur eine Spielrunde und die wertvollste Kategorie betrachtet, die ebenfalls Kniffel oder Yahtzee genannt wird.

Bei der Kategorie Kniffel geht es darum, mit 5 Würfeln innerhalb von höchstens 3 Würfen 5 gleiche Augenzahlen zu erzielen. Beim ersten Wurf werden alle 5 Würfel geworfen. Beim zweiten und beim dritten Wurf können Würfel beliebig ausgewählt werden. Diese werden erneut geworfen.

Um mit möglichst großer Wahrscheinlichkeit einen Kniffel zu erzielen, ist folgende naheliegende Strategie optimal:

• Vor dem zweiten und vor dem dritten Wurf wird jeweils die oder eine der am häufigsten vorkommenden Augenzahlen bestimmt. Die Würfel, die diese Augenzahl zeigen, werden behalten. Alle anderen Würfel werden erneut geworfen.

Beispiele: Nach dem Wurf (1, 1, 1, 2, 2) werden also die drei Würfel mit der Augenzahl 1 behalten und die zwei Würfel mit der Augenzahl 2 erneut geworfen. Nach dem Wurf (4, 4, 5, 5, 6) werden die zwei Würfel mit der Augenzahl 4 behalten und die drei anderen Würfel erneut geworfen. Alternativ kann auch die Augenzahl 5 ausgewählt und die drei anderen Würfel erneut geworfen werden.

Die möglichen Variationen aus den Augenzahlen der 5 Würfel lassen sich in folgende 5 Klassen (Zustände) einteilen, wobei A, B, C, D, E jeweils verschiedene Augenzahlen darstellen:

• fünf verschiedene Augenzahlen (ABCDE)
• einmal oder zweimal 2 gleiche Augenzahlen (entweder AABCD oder AABBC)
• 3 gleiche Augenzahlen (entweder AAABC oder AAABB)
• 4 gleiche Augenzahlen (AAAAB)
• 5 gleiche Augenzahlen (AAAAA)

Die Wahrscheinlichkeiten, mit dem ersten Wurf eine Variation aus einer dieser 5 Klassen zu erzielen, können in dieser Reihenfolge als Startvektor dargestellt werden:

$x_{0}={\begin{pmatrix}{\tfrac {720}{7776}}\\{\tfrac {5400}{7776}}\\{\tfrac {1500}{7776}}\\{\tfrac {150}{7776}}\\{\tfrac {6}{7776}}\\\end{pmatrix}}$

Sie werden jeweils berechnet als Quotient aus der Anzahl der günstigen Variationen und der Anzahl 6⁵ = 7776 aller Variationen. Weil jede Augenzahl mehrfach vorkommen kann, sind es Variationen mit Wiederholung. Die Wahrscheinlichkeiten, nach dem Erzielen einer bestimmten gegebenen Variationsklasse eine bestimmte Variationsklasse mit dem zweiten Wurf zu erzielen, sind hier die Übergangswahrscheinlichkeiten $p_{i,j}$. Diese können als Übergangsmatrix

$P={\begin{pmatrix}{\tfrac {120}{1296}}&0&0&0&0\\{\tfrac {900}{1296}}&{\tfrac {120}{216}}&0&0&0\\{\tfrac {250}{1296}}&{\tfrac {80}{216}}&{\tfrac {25}{36}}&0&0\\{\tfrac {25}{1296}}&{\tfrac {15}{216}}&{\tfrac {10}{36}}&{\tfrac {5}{6}}&0\\{\tfrac {1}{1296}}&{\tfrac {1}{216}}&{\tfrac {1}{36}}&{\tfrac {1}{6}}&{\tfrac {1}{1}}\\\end{pmatrix}}$

dargestellt werden. Zum Beispiel ist $p_{2,1}={\tfrac {900}{1296}}$ die Wahrscheinlichkeit, nach dem gegebenem ersten Wurf mit fünf verschiedenen Augenzahlen (ABCDE) im zweiten Wurf einmal oder zweimal 2 gleiche Augenzahlen (entweder AABCD oder AABBC) zu erzielen. Zur Berechnung dieser Wahrscheinlichkeiten sind manchmal Fallunterscheidungen notwendig, denn die häufigste Augenzahl nach dem zweiten Wurf kann eine andere sein als die häufigste Augenzahl nach dem ersten Wurf. Dafür wird die oben beschriebene optimale Strategie für das Erzielen eines Kniffels zugrunde gelegt.

Daraus ergibt sich der Vektor für die Wahrscheinlichkeiten nach zwei Würfen, indem die Übergangsmatrix $P$ mit dem Startvektor $x_{0}$ multipliziert wird:

$x_{1}=P\cdot x_{0}$

Die gleichen Betrachtungen können für die Berechnung der Wahrscheinlichkeiten nach drei Würfen verwendet werden und man erhält den Vektor

$x_{2}=P^{2}\cdot x_{0}$

Als Verallgemeinerung erhält man den Vektor für die Wahrscheinlichkeiten nach $k$ Würfen:

$x_{k-1}=P^{k-1}\cdot x_{0}$

Das letzte Element von $x_{k-1}$ ist die Wahrscheinlichkeit für einen Kniffel nach $k$ Würfen. Die ausgerechneten Werte für die ersten 10 Würfe sind:

Anzahl der Würfe	Wahrscheinlichkeit für einen Kniffel (Yahtzee)
1	0,00077
2	0,01263
3	0,04603
4	0,10058
5	0,17051
6	0,24908
7	0,33050
8	0,41044
9	0,48601
10	0,55553

Nach dem zehnten Wurf ist die Wahrscheinlichkeit, einen Kniffel zu erzielen, also zum ersten Mal größer als ${\tfrac {1}{2}}$.

Die Ratte im Zimmer

Der Adjazenzgraph der stochastischen Matrix aus dem Beispiel und damit auch ein Übergangsgraph

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 spaltenstochastische Matrix $P$ beschrieben:

$P={\begin{pmatrix}0{,}05&0{,}1&0{,}1\\0{,}4&0{,}7&0{,}8\\0{,}55&0{,}2&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}={\begin{pmatrix}1\\0\\0\\\end{pmatrix}}$

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

$x_{4}=P^{4}\cdot x_{0}={\begin{pmatrix}0{,}0952\\0{,}6933\\0{,}2115\\\end{pmatrix}}$

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, dass sich das System im Gleichgewicht befindet. Gesucht ist daher ein Rechtseigenvektor von $P$ zum Eigenwert 1. Durch Nachrechnen ergibt sich für den Eigenvektor gerundet

$x={\begin{pmatrix}0{,}0952\\0{,}6926\\0{,}2121\\\end{pmatrix}}$

Peter sollte also zuerst hinter dem Schrank suchen.

Die Katze und die Maus

Gegeben seien fünf nebeneinander liegende Boxen, durchnummeriert von 1 bis 5, und in der ersten Box möge sich eine Katze und in der letzten eine Maus befinden. Nach einer festen Zeit 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 Box $i$ und die Maus in der Box $j$. 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) oder (4,4).

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

Die Übergangsmatrix $P$ dazu ist nun

$P={\begin{pmatrix}0&0&{\tfrac {1}{4}}&0&0\\0&0&{\tfrac {1}{4}}&0&0\\{\tfrac {1}{2}}&1&0&{\tfrac {1}{2}}&0\\0&0&{\tfrac {1}{4}}&0&0\\{\tfrac {1}{2}}&0&{\tfrac {1}{4}}&{\tfrac {1}{2}}&1\end{pmatrix}}$

Wenn wir beispielsweise wie zu Beginn im 2. Zustand $v={\begin{pmatrix}0\\1\\0\\0\\0\\\end{pmatrix}}$ sind, dann wechseln wir mit Sicherheit (Übergangswahrscheinlichkeit 1) in den 3. Zustand $v={\begin{pmatrix}0\\0\\1\\0\\0\\\end{pmatrix}}$, also Katze in der zweiten Box und Maus in der vierten Box. Daher ist $p_{3,2}=1$.

Von diesem Zustand ausgehend kommen wir nun aber mit Wahrscheinlichkeit ${\tfrac {1}{4}}$ in einen der anderen vier Zustände, daher sind die anderen vier Zeilen in der 3. Spalte gleich ${\tfrac {1}{4}}$. Mit Ausnahme von $p_{5,5}=1$ (Übergang von Spielende nach Spielende) sind alle Wahrscheinlichkeiten auf der Hauptdiagonalen gleich 0, weil vor dem Spielende der Zustand nicht derselbe bleiben kann.

Siehe auch

• Übergangstabelle

Literatur

• Franz-Josef Fritz, Bertram Huppert, Wolfgang Willems: Stochastische Matrizen. Springer, Berlin / Heidelberg 1979, ISBN 978-3-540-09126-4, doi:10.1007/978-3-642-67131-9 (E-Book-ISBN 978-3-642-67131-9). 
• 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 (= Springer-Lehrbuch). Springer, Berlin 2012, ISBN 978-3-642-32185-6. 

Einzelnachweise

Spezielle Matrizen in der Statistik

Datenmatrix | Produktsummenmatrix | Prädiktionsmatrix | residuenerzeugende Matrix | zentrierende Matrix | Kovarianzmatrix | Korrelationsmatrix | Präzisionsmatrix | Gewichtsmatrix | Restriktionsmatrix | Fisher-Informationsmatrix | Bernoulli-Matrix | Leslie-Matrix | Zufallsmatrix | Übergangsmatrix