Matrix/Stochastisch/Einführung/Textabschnitt

Die zugrunde liegende Interpretation für eine spaltenstochastische Matrix ist folgendermaßen: Man hat eine Menge von ${}n$ möglichen Plätzen, Positionen, Netzwerkknoten, Internetseiten oder ähnliches, in denen man sich mit einer gewissen Wahrscheinlichkeit (einer Verteilung, einer Gewichtung) aufhalten kann. Eine solche Verteilung wird durch ein ${}n$-Tupel ${}{\begin{pmatrix}v_{1}\\v_{2}\\\vdots \\v_{n}\end{pmatrix}}$ mit reellen nichtnegativen Zahlen ${}v_{i}$ mit ${}\sum _{i=1}^{n}v_{i}=1$ beschrieben. Man spricht von einem Verteilungsvektor. Eine spaltenstochastische Matrix beschreibt die Übergangswahrscheinlichkeiten des gegebenen Netzwerks in einem bestimmten Zeitabschnitt. Der Eintrag ${}a_{ij}$ ist die Wahrscheinlichkeit, dass ein im Knoten ${}j$ befindliches Objekt (ein Besucher der Netzseite ${}j$) zur Position ${}i$ hinüberwechselt (sich zur Netzseite ${}i$ weiterklickt). Der ${}j$-te Standardvektor entspricht der Verteilung, in der alles im ${}j$-ten Knotenpunkt konzentriert ist. Die ${}j$-te Spalte der Matrix beschreibt das Bild dieses Standardvektors unter der Matrix. Generell wird zu einer Verteilung ${}v$ durch Anwenden der Matrix die Bildverteilung ${}Mv$ ausgerechnet, siehe Aufgabe. Naheliegende Fragen sind, ob es Verteilungen gibt, die stationär sind (stationäre Verteilung oder Fixverteilung oder Eigenverteilung), also in sich selbst überführt werden, ob es periodische Verteilungen gibt, ob es bei „unendlich vielen“ Iterationen der Matrix Grenzverteilungen gibt, und wie man diese ausrechnen kann.

Definition

Eine reelle quadratische Matrix

${}M=(a_{ij})_{1\leq i,j\leq n}\,$

heißt spaltenstochastisch, wenn alle Einträge

${}a_{ij}\geq 0\,$

sind und für jede Spaltensumme (also jedes ${}j$)

${}\sum _{i=1}^{n}a_{ij}=1\,$

gilt.

Beispiel

Eine spaltenstochastische ${}2\times 2$-Matrix hat die Form

${\begin{pmatrix}p_{1}&p_{2}\\1-p_{1}&1-p_{2}\end{pmatrix}}$

mit

${}0\leq p_{1},p_{2}\leq 1\,.$

Das charakteristische Polynom ist

${}{\begin{aligned}(X-p_{1})(X-1+p_{2})-(1-p_{1})p_{2}&=X^{2}+(p_{2}-p_{1}-1)X+p_{1}(1-p_{2})-p_{2}(1-p_{1})\\&=X^{2}+(p_{2}-p_{1}-1)X+p_{1}-p_{2}\\&=(X-1)(X+p_{2}-p_{1}).\,\end{aligned}}$

Eigenwerte sind also ${}1$ und ${}p_{1}-p_{2}$. Eine stationäre Verteilung ist (der Fall $p_{1}=1$ und $p_{2}=0$ ist für die folgende Rechnung auszuschließen) durch ${}{\begin{pmatrix}{\frac {p_{2}}{p_{2}-p_{1}+1}}\\{\frac {1-p_{1}}{p_{2}-p_{1}+1}}\end{pmatrix}}$ gegeben, es ist ja

${}{\begin{aligned}{\begin{pmatrix}p_{1}&p_{2}\\1-p_{1}&1-p_{2}\end{pmatrix}}{\begin{pmatrix}{\frac {p_{2}}{p_{2}-p_{1}+1}}\\{\frac {1-p_{1}}{p_{2}-p_{1}+1}}\end{pmatrix}}&={\begin{pmatrix}p_{1}{\frac {p_{2}}{p_{2}-p_{1}+1}}+p_{2}{\frac {1-p_{1}}{p_{2}-p_{1}+1}}\\(1-p_{1}){\frac {p_{2}}{p_{2}-p_{1}+1}}+(1-p_{2}){\frac {1-p_{1}}{p_{2}-p_{1}+1}}\end{pmatrix}}\\&={\begin{pmatrix}{\frac {p_{1}p_{2}+p_{2}(1-p_{1})}{p_{2}-p_{1}+1}}\\{\frac {(1-p_{1})p_{2}+(1-p_{2})(1-p_{1})}{p_{2}-p_{1}+1}}\end{pmatrix}}\\&={\begin{pmatrix}{\frac {p_{2}}{p_{2}-p_{1}+1}}\\{\frac {1-p_{1}}{p_{2}-p_{1}+1}}\end{pmatrix}}.\end{aligned}}$

Beispiel

Die spaltenstochastische ${}2\times 2$-Matrix

${\begin{pmatrix}0&1\\1&0\end{pmatrix}}$

führt die Verteilung ${}{\begin{pmatrix}p\\1-p\end{pmatrix}}$ in die Verteilung ${}{\begin{pmatrix}1-p\\p\end{pmatrix}}$ über. Die Verteilung ${}{\begin{pmatrix}{\frac {1}{2}}\\{\frac {1}{2}}\end{pmatrix}}$ wird in sich selbst überführt, ist also eine stationäre Verteilung. Die Verteilung ${}{\begin{pmatrix}1\\0\end{pmatrix}}$ wird in ${}{\begin{pmatrix}0\\1\end{pmatrix}}$ überführt und umgekehrt, es handelt sich also um periodische Verteilungen der Periodenlänge ${}2$.

Beispiel

Die spaltenstochastische ${}n\times n$-Matrix

${\begin{pmatrix}1&1&\cdots &1\\0&0&\cdots &0\\\vdots &\vdots &\cdots &\vdots \\0&0&\cdots &0\end{pmatrix}}$

führt die Verteilung ${}{\begin{pmatrix}v_{1}\\\vdots \\v_{n}\end{pmatrix}}$ in die Verteilung

${}{\begin{pmatrix}1&1&\cdots &1\\0&0&\cdots &0\\\vdots &\vdots &\cdots &\vdots \\0&0&\cdots &0\end{pmatrix}}{\begin{pmatrix}v_{1}\\v_{2}\\\vdots \\v_{n}\end{pmatrix}}={\begin{pmatrix}\sum _{i=1}^{n}v_{i}\\0\\\vdots \\0\end{pmatrix}}={\begin{pmatrix}1\\0\\\vdots \\0\end{pmatrix}}\,$

über. Der erste Standardvektor ist ein Eigenvektor zum Eigenwert ${}1$, die weiteren Standardvektoren werden, wie jeder Verteilungsvektor, in den ersten Standardvektor überführt. Der Kern wird von den Vektoren ${}e_{1}-e_{j}$, ${}j\geq 2$, erzeugt und enthält keine Verteilungsvektoren.

Beispiel

Es sei ${}N$ ein Netzwerk (oder ein „gerichteter Graph“), bestehend aus einer Menge ${}K$ aus Knotenpunkten und einer Menge an gerichteten Verbindungen, die zwischen Knotenpunkten bestehen können. Beispielsweise ist ${}K$ die Menge aller Seiten im Internet und von der Seite ${}j\in K$ besteht ein Verbindungspfeil nach ${}i\in K$, falls es auf der Internetseite ${}j$ einen Link auf die Seite ${}i$ gibt. Die Verlinkungsstruktur kann man durch die Adjazenzmatrix

${}A={\left(a_{ij}\right)}\,$

ausdrücken, wobei

${}a_{ij}:={\begin{cases}1,\,{\text{falls es einen Link von }}j{\text{ auf }}i{\text{ gibt}},\\0,\,{\text{ sonst}},\end{cases}}\,$

festgelegt ist (in der ${}j$-ten Spalte sind die von ${}j$ ausgehenden Links ablesbar), oder aber durch die spaltenstochastische Matrix

${}B={\left(b_{ij}\right)}\,,$

wobei

${}b_{ij}={\frac {a_{ij}}{d_{j}}}\,$

und ${}d_{j}$ die Anzahl der Links angibt, die vom ${}j$-ten Knoten überhaupt ausgehen. Diese Division sichert, dass die Spaltensummennorm gleich ${}1$ wird (es sei vorausgesetzt, dass von jedem Knoten mindestens ein Link ausgeht).

Die Adjazenzmatrix und die spaltenstochastisch gemachte Adjazenzmatrix zum Graphen rechts (wobei wir durchgängig Selbstlinks hinzunehmen) sind

${\begin{pmatrix}1&0&0&0&0\\1&1&0&0&0\\1&0&1&0&0\\1&1&1&1&0\\1&0&1&1&1\end{pmatrix}}{\text{ und }}{\begin{pmatrix}{\frac {1}{5}}&0&0&0&0\\{\frac {1}{5}}&{\frac {1}{2}}&0&0&0\\{\frac {1}{5}}&0&{\frac {1}{3}}&0&0\\{\frac {1}{5}}&{\frac {1}{2}}&{\frac {1}{3}}&{\frac {1}{2}}&0\\{\frac {1}{5}}&0&{\frac {1}{3}}&{\frac {1}{2}}&1\end{pmatrix}}.$