Kurs:Lineare Algebra (Osnabrück 2017-2018)/Teil II/Vorlesung 54/latex
\setcounter{section}{54}
\zwischenueberschrift{Stochastische Matrizen}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Stochmatgraph.png} }
\end{center}
\bildtext {} }
\bildlizenz { Stochmatgraph.png } {} {NikelsenH} {Commons} {CC-by-sa 3.0} {}
\inputdefinition
{}
{
Eine reelle quadratische Matrix
\mavergleichskettedisp
{\vergleichskette
{M
}
{ =} { (a_{ij})_{1 \leq i,j \leq n}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
heißt
\definitionswort {spaltenstochastisch}{,}
wenn alle Einträge
\mavergleichskettedisp
{\vergleichskette
{ a_{ij}
}
{ \geq} { 0
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
sind und für jede Spaltensumme
\zusatzklammer {also jedes $j$} {} {}
\mavergleichskettedisp
{\vergleichskette
{ \sum_{i =1 }^n a_{ij}
}
{ =} {1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gilt.
}
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
\zusatzklammer {einer Verteilung, einer Gewichtung} {} {}
aufhalten kann. Eine solche Verteilung wird durch ein $n$-Tupel
\mathl{\begin{pmatrix} v_1 \\v_2\\ \vdots\\v_n \end{pmatrix}}{} mit reellen nichtnegativen Zahlen $v_i$ mit
\mavergleichskette
{\vergleichskette
{\sum_{i = 1}^n v_i
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
beschrieben. Man spricht von einem \stichwort {Verteilungsvektor} {.} Eine spaltenstochastische Matrix beschreibt die Übergangswahrscheinlichkeiten des gegebenen Netzwerks in einem bestimmten Zeitabschnitt. Der Eintrag
\mathl{a_{ij}}{} ist die Wahrscheinlichkeit, dass ein im Knoten $j$ befindliches Objekt
\zusatzklammer {ein Besucher der Netzseite $j$} {} {}
zur Position $i$ hinüberwechselt
\zusatzklammer {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 54.1.
Naheliegende Fragen sind, ob es Verteilungen gibt, die stationär sind
\zusatzklammer {\stichwort {stationäre Verteilung} {} oder \stichwort {Fixverteilung} {} oder \stichwort {Eigenverteilung} {}} {} {,}
also in sich selbst überführt werden, ob es periodische Verteilungen gibt, ob es bei \anfuehrung{unendlich vielen}{} Iterationen der Matrix Grenzverteilungen gibt, und wie man diese ausrechnen kann.
\inputbeispiel{}
{
Eine
\definitionsverweis {spaltenstochastische}{}{}
$2 \times 2$-\definitionsverweis {Matrix}{}{}
hat die Form
\mathdisp {\begin{pmatrix} p_1 & p_2 \\ 1-p_1 & 1-p_2 \end{pmatrix}} { }
mit
\mavergleichskettedisp
{\vergleichskette
{0
}
{ \leq} {p_1,p_2
}
{ \leq} {1
}
{ } {
}
{ } {
}
}
{}{}{.}
Das
\definitionsverweis {charakteristische Polynom}{}{}
ist
\mavergleichskettealigndrucklinks
{\vergleichskettealigndrucklinks
{(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)
}
{ } {
}
}
{}{}{.}
Eigenwerte sind also
\mathkor {} {1} {und} {p_1-p_2} {.}
Eine stationäre Verteilung ist
\zusatzklammer {der Fall \mathlk{p_1=1}{} und \mathlk{p_2=0}{} ist für die folgende Rechnung auszuschließen} {} {}
durch
\mathl{\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
\mavergleichskettealignhandlinks
{\vergleichskettealignhandlinks
{ \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}
}
{ } {
}
}
{}
{}{.}
}
\inputbeispiel{}
{
Die
\definitionsverweis {spaltenstochastische}{}{}
$2 \times 2$-\definitionsverweis {Matrix}{}{}
\mathdisp {\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}} { }
führt die Verteilung
\mathl{\begin{pmatrix} p \\1-p \end{pmatrix}}{} in die Verteilung
\mathl{\begin{pmatrix} 1-p \\p \end{pmatrix}}{} über. Die Verteilung
\mathl{\begin{pmatrix} { \frac{ 1 }{ 2 } } \\ { \frac{ 1 }{ 2 } } \end{pmatrix}}{} wird in sich selbst überführt, ist also eine stationäre Verteilung. Die Verteilung
\mathl{\begin{pmatrix} 1 \\0 \end{pmatrix}}{} wird in
\mathl{\begin{pmatrix} 0 \\1 \end{pmatrix}}{} überführt und umgekehrt, es handelt sich also um periodische Verteilungen der Periodenlänge $2$.
}
\inputbeispiel{}
{
Die
\definitionsverweis {spaltenstochastische}{}{}
$n \times n$-\definitionsverweis {Matrix}{}{}
\mathdisp {\begin{pmatrix} 1 & 1 & \cdots & 1 \\ 0 & 0 & \cdots & 0 \\ \vdots & \vdots & \cdots & \vdots \\ 0 & 0 & \cdots & 0 \end{pmatrix}} { }
führt die Verteilung
\mathl{\begin{pmatrix} v_1 \\ \vdots \\ v_n \end{pmatrix}}{} in die Verteilung
\mavergleichskettedisp
{\vergleichskette
{ \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
\mathbed {e_1-e_j} {}
{j \geq 2} {}
{} {} {} {,}
erzeugt und enthält keine Verteilungsvektoren.
}
\inputbeispiel{}
{
Es sei $N$ ein Netzwerk
\zusatzklammer {oder ein \anfuehrung{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
\mathl{j \in K}{} besteht ein Verbindungspfeil nach
\mathl{i \in K}{,} falls es auf der Internetseite $j$ einen Link auf die Seite $i$ gibt. Die Verlinkungsstruktur kann man durch die \stichwort {Adjazenzmatrix } {}
\mavergleichskettedisp
{\vergleichskette
{A
}
{ =} { { \left( a_{ij} \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ausdrücken, wobei
\mavergleichskettedisp
{\vergleichskette
{a_{ij}
}
{ \defeq} { \begin{cases} 1,\, \text{falls es einen Link von } j \text{ auf } i \text{ gibt}, \\ 0,\, \text{ sonst},\end{cases}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
festgelegt ist
\zusatzklammer {in der $j$-ten Spalte sind die von $j$ ausgehenden Links ablesbar} {} {,}
oder aber durch die
\definitionsverweis {spaltenstochastische Matrix}{}{}
\mavergleichskettedisp
{\vergleichskette
{B
}
{ =} { { \left( b_{ij} \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
wobei
\mavergleichskettedisp
{\vergleichskette
{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
\zusatzklammer {es sei vorausgesetzt, dass von jedem Knoten mindestens ein Link ausgeht} {} {.}
}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Tred-G.svg} }
\end{center}
\bildtext {} }
\bildlizenz { Tred-G.svg } {} {Dmitry_Dzhus} {Commons} {gemeinfrei} {}
Die Adjazenzmatrix und die spaltenstochastisch gemachte Adjazenzmatrix zum Graphen rechts
\zusatzklammer {wobei wir durchgängig Selbstlinks hinzunehmen} {} {}
sind
\mathdisp {\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}} { . }
\zwischenueberschrift{Potenzen von stochastischen Matrizen}
Wir untersuchen nun die Potenzen von stochastischen Matrizen mit Hilfe der Summennorm und den Ergebnissen der letzten Vorlesung.
\inputfaktbeweis
{Spaltenstochastische Matrix/Konvergenzeigenschaften/Fakt}
{Korollar}
{}
{
\faktsituation {Eine
\definitionsverweis {spaltenstochastische Matrix}{}{}}
\faktfolgerung {ist
\definitionsverweis {stabil}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Für einen beliebigen Vektor
\mathl{v \in V}{} ist
Wegen
\mavergleichskettealign
{\vergleichskettealign
{ \mid\mid\! {Mv} \! \mid \mid_{\operatorname{sum} }
}
{ =} { \sum_{ i = 1}^n \betrag { (Mv)_i }
}
{ =} { \sum_{ i = 1}^n \betrag { \sum_{j = 1}^n a_{ij} v_j }
}
{ \leq} { \sum_{ i = 1}^n { \left( \sum_{ j = 1}^n a_{ij} \betrag { v_j } \right) }
}
{ =} { \sum_{ j = 1}^n \betrag { v_j } { \left( \sum_{i = 1}^n a_{ij} \right) }
}
}
{
\vergleichskettefortsetzungalign
{ =} { \sum_{ j = 1}^n \betrag { v_j }
}
{ =} { \mid\mid\! {v} \! \mid \mid_{\operatorname{sum} }
}
{ } {}
{ } {}
}
{}{.}
Iterative Anwendung dieser Beobachtung zeigt, dass
Satz 53.10 (2)
erfüllt ist.
\inputfaktbeweis
{Spaltenstochastisch/Isometrisch bezüglich Summennorm/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei
\mavergleichskettedisp
{\vergleichskette
{M
}
{ =} { (a_{ij})_{1 \leq i,j \leq n}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
eine reelle quadratische Matrix mit nichtnegativen Einträgen.}
\faktfolgerung {Dann ist $M$ genau dann
\definitionsverweis {spaltenstochastisch}{}{,}
wenn $M$ für Vektoren mit nichtnegativen Einträgen isometrisch bezüglich der
\definitionsverweis {Summennorm}{}{}
ist, wenn also
\mavergleichskettedisp
{\vergleichskette
{ \Vert { M v } \Vert_{\rm sum}
}
{ =} { \Vert { v } \Vert_{\rm sum}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für alle
\mathl{v \in \R_{\geq 0}^n}{} gilt.}
\faktzusatz {}
\faktzusatz {}
}
{
Es sei $M$ eine spaltenstochastische Matrix und
\mavergleichskettedisp
{\vergleichskette
{v
}
{ =} { \begin{pmatrix} v_1 \\\vdots\\ v_n \end{pmatrix}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ein Vektor mit nichtnegativen Einträgen. Dann ist
\mavergleichskettealign
{\vergleichskettealign
{ \Vert { M v} \Vert_{\rm sum}
}
{ =} { \sum_{ i = 1}^n (Mv)_i
}
{ =} { \sum_{ i = 1}^n { \left( \sum_{j = 1}^n a_{ij} v_j \right) }
}
{ =} { \sum_{ j = 1}^n v_j { \left( \sum_{i = 1}^n a_{ij} \right) }
}
{ =} {\sum_{ j = 1}^n v_j
}
}
{
\vergleichskettefortsetzungalign
{ =} { \Vert { v} \Vert_{\rm sum}
}
{ } {}
{ } {}
{ } {}
}
{}{.}
Wenn umgekehrt die angegebene isometrische Eigenschaft gilt, so gilt insbesondere für die Bilder der Standardvektoren, dass ihre Summennorm gleich $1$ sein muss. Diese Bilder stehen in der entsprechenden Spalte der Matrix, alle Spaltensummen haben also den Wert $1$.
\inputfaktbeweis
{Spaltenstochastische Matrix/Positive Zeile/Eindimensionaler Eigenraum/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $M$ eine
\definitionsverweis {spaltenstochastische Matrix}{}{.}}
\faktuebergang {Dann gelten folgende Aussagen.}
\faktfolgerung {\aufzaehlungdrei{Es gibt
\definitionsverweis {Eigenvektoren}{}{}
zum
\definitionsverweis {Eigenwert}{}{}
$1$.
}{Wenn es eine Zeile gibt, in der alle Einträge positiv sind, so gilt für jeden Vektor
\mathl{v \in V}{,} der sowohl positive als auch negative Einträge besitzt, die Abschätzung
\mavergleichskettedisp
{\vergleichskette
{ \mid\mid\! { M v} \! \mid \mid_{\operatorname{sum} }
}
{ <} { \mid\mid\! { v} \! \mid \mid_{\operatorname{sum} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}{Wenn es eine Zeile gibt, in der alle Einträge positiv sind, so ist der Eigenraum zum Eigenwert $1$ eindimensional. Es gibt dann einen Eigenvektor, der nur nichtnegative Einträge hat und insbesondere eine eindeutig bestimmte
\definitionsverweis {stationäre Verteilung}{}{.}
}}
\faktzusatz {}
\faktzusatz {}
}
{
(1). Die
\definitionsverweis {transponierte Matrix}{}{}
ist
\definitionsverweis {zeilenstochastisch}{}{}
und besitzt daher den
\definitionsverweis {Eigenvektor}{}{}
\mathl{\begin{pmatrix} 1 \\1\\ \vdots\\1 \end{pmatrix}}{} zum Eigenwert $1$. Daher besitzt nach
Satz 23.2
das
\definitionsverweis {charakteristische Polynom}{}{}
der transponierten Matrix eine Nullstelle an der Stelle $1$ und dies gilt nach
Aufgabe 23.19
dann auch für die ursprüngliche Matrix. Daher besitzt $M$ einen Eigenvektor zum Eigenwert $1$.
(2). Es seien nun zusätzlich alle Einträge der $k$-ten Zeile positiv und
\mathl{v \in V}{} sei ein Vektor mit
\zusatzklammer {mindestens} {} {}
einem positiven und einem negativen Eintrag. Dann ist
\mavergleichskettealign
{\vergleichskettealign
{ \mid\mid\! {Mv} \! \mid \mid_{\operatorname{sum} }
}
{ =} { \sum_{ i = 1}^n \betrag { (Mv)_i }
}
{ =} { \sum_{ i = 1}^n \betrag { \sum_{j = 1}^n a_{ij} v_j }
}
{ =} { \sum_{ i \neq k} \betrag { \sum_{j = 1}^n a_{ij} v_j } + \betrag { \sum_{j = 1}^n a_{kj} v_j }
}
{ <} { \sum_{i \neq k} \sum_{ j = 1}^n a_{ij} \betrag { v_j } + \sum_{j = 1}^n \betrag { a_{kj} v_j }
}
}
{
\vergleichskettefortsetzungalign
{ =} { \sum_{i = 1}^n \sum_{j = 1}^n a_{ij} \betrag { v_j }
}
{ =} { \sum_{ j = 1}^n \betrag { v_j } { \left( \sum_{i = 1}^n a_{ij} \right) }
}
{ =} { \sum_{ j = 1}^n \betrag { v_j }
}
{ =} { \mid\mid\! {v} \! \mid \mid_{\operatorname{sum} }
}
}
{}{.}
(3). Wie im Beweis zu (2) seien alle Einträge der $k$-ten Zeile positiv. Für einen jeden Eigenvektor $v$ zum Eigenwert $1$ sind nach (2) entweder alle Einträge nichtnegativ oder nichtpositiv. Somit ist für einen solchen Vektor wegen
\mavergleichskette
{\vergleichskette
{Mv
}
{ = }{v
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
der $k$-te Eintrag ungleich $0$. Es seien $v,w$ solche Eigenvektoren. Dann gehört auch
\mathl{{ \frac{ w_k }{ v_k } } v-w}{} zum Fixraum. Allerdings ist die $k$-te Komponente davon gleich $0$ und daher ist es der Nullvektor. Das bedeutet, dass
\mathkor {} {v} {und} {w} {}
\definitionsverweis {linear abhängig}{}{}
sind. Somit ist dieser Eigenraum eindimensional. Wegen (2) gibt es einen Eigenvektor zum Eigenwert $1$ mit nichtnegativen Einträgen. Durch Normieren sieht man, dass es auch eine stationäre Verteilung gibt.
\inputbeispiel{}
{
Wir betrachten die
\definitionsverweis {spaltenstochastische}{}{}
$3 \times 3$-\definitionsverweis {Matrix}{}{}
\mathdisp {\begin{pmatrix} { \frac{ 1 }{ 3 } } & { \frac{ 1 }{ 3 } } & { \frac{ 1 }{ 3 } } \\ { \frac{ 1 }{ 2 } } & { \frac{ 2 }{ 3 } } & 0 \\ { \frac{ 1 }{ 6 } } & 0 & { \frac{ 2 }{ 3 } } \end{pmatrix}} { , }
bei der alle Einträge der ersten Zeile positiv sind. Nach
Lemma 54.8
gibt es eine eindeutige Eigenverteilung. Um diese zu bestimmen, berechnet man den Kern von
\mavergleichskettedisp
{\vergleichskette
{ \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\0 & 0 & 1 \end{pmatrix} - \begin{pmatrix} { \frac{ 1 }{ 3 } } & { \frac{ 1 }{ 3 } } & { \frac{ 1 }{ 3 } } \\ { \frac{ 1 }{ 2 } } & { \frac{ 2 }{ 3 } } & 0 \\ { \frac{ 1 }{ 6 } } & 0 & { \frac{ 2 }{ 3 } } \end{pmatrix}
}
{ =} { \begin{pmatrix} { \frac{ 2 }{ 3 } } & - { \frac{ 1 }{ 3 } } & - { \frac{ 1 }{ 3 } } \\ -{ \frac{ 1 }{ 2 } } & { \frac{ 1 }{ 3 } } & 0 \\ - { \frac{ 1 }{ 6 } } & 0 & { \frac{ 1 }{ 3 } } \end{pmatrix}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Dieser wird von
\mathl{\begin{pmatrix} 2 \\3\\ 1 \end{pmatrix}}{} erzeugt und die stationäre Verteilung ist
\mavergleichskettedisp
{\vergleichskette
{ \begin{pmatrix} { \frac{ 2 }{ 6 } } \\ { \frac{ 3 }{ 6 } }\\ { \frac{ 1 }{ 6 } } \end{pmatrix}
}
{ =} { \begin{pmatrix} { \frac{ 1 }{ 3 } } \\ { \frac{ 1 }{ 2 } }\\ { \frac{ 1 }{ 6 } } \end{pmatrix}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}
\inputbeispiel{}
{
Für die
\definitionsverweis {spaltenstochastische}{}{}
$3 \times 3$-\definitionsverweis {Matrix}{}{}
\mathdisp {\begin{pmatrix} 1 & 0 & { \frac{ 1 }{ 3 } } \\ 0 & 1 & { \frac{ 1 }{ 3 } } \\0 & 0 & { \frac{ 1 }{ 3 } } \end{pmatrix}} { }
ist der Eigenraum zum Eigenwert $1$ gleich
\mathl{\langle e_1 ,\, e_2 \rangle}{,} also zweidimensional. Die Aussage
Lemma 54.8
gilt also nicht, wenn es eine Spalte
\zusatzklammer {aber keine Zeile} {} {}
mit ausschließlich positiven Einträgen gibt.
}
\inputfaktbeweis
{Spaltenstochastische Matrix/Positive Zeile/Konvergenz/Fakt}
{Satz}
{}
{
\faktsituation {Es sei $M$ eine
\definitionsverweis {spaltenstochastische Matrix}{}{}}
\faktvoraussetzung {mit der Eigenschaft, dass es eine Zeile gibt, in der alle Einträge positiv sind.}
\faktfolgerung {Dann konvergiert zu jedem
\definitionsverweis {Verteilungsvektor}{}{}
\mathl{v \in \R_{\geq 0}^n}{} mit
\mavergleichskette
{\vergleichskette
{\sum_{i = 1}^n v_i
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Folge
\mathl{M^n v}{} gegen die eindeutig bestimmte
\definitionsverweis {stationäre Verteilung}{}{}
von $M$.}
\faktzusatz {}
\faktzusatz {}
}
{
Es sei
\mathl{w \in \R^n}{} die nach
Lemma 54.8 (3)
eindeutig bestimmte stationäre Verteilung und
\mavergleichskettedisp
{\vergleichskette
{U
}
{ =} { { \left\{ \begin{pmatrix} u_1 \\\vdots\\ u_n \end{pmatrix} \mid \sum_{i = 1}^n u_i = 0 \right\} }
}
{ \subseteq} { \R^n
}
{ } {
}
{ } {
}
}
{}{}{.}
Dies ist ein Untervektorraum von $\R^n$ der Dimension $n-1$. Nach
Lemma 54.8 (2)
hat $w$ ausschließlich nichtnegative Einträge und gehört damit nicht zu $U$. Wegen
\mavergleichskettealign
{\vergleichskettealign
{ \sum_{ i = 1}^n (Mu)_i
}
{ =} { \sum_{ i = 1}^n { \left( \sum_{j = 1}^n a_{ij} u_j \right) }
}
{ =} { \sum_{ j = 1}^n u_j { \left( \sum_{i = 1}^n a_{ij} \right) }
}
{ =} { \sum_{ j = 1}^n u_j
}
{ } {
}
}
{}
{}{}
ist $U$ invariant unter der Matrix $M$. Somit ist
\mavergleichskettedisp
{\vergleichskette
{V
}
{ =} { U \oplus \R w
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
eine
\definitionsverweis {direkte Summenzerlegung}{}{}
in invariante Untervektorräume. Für jedes
\mathl{u \in U}{} mit
\mavergleichskette
{\vergleichskette
{ \mid\mid\! {u} \! \mid \mid_{\operatorname{sum} }
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskettedisp
{\vergleichskette
{ \mid\mid\! { M u} \! \mid \mid_{\operatorname{sum} }
}
{ <} {1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
nach
Lemma 54.8 (2).
Da die Sphäre zum Radius $1$ bezüglich jeder Norm
\definitionsverweis {kompakt}{}{}
ist, ist die induzierte Maximumsnorm von $M{{|}}_U$ kleiner als $1$. Nach
Lemma 53.8
und
Satz 53.6
konvergiert daher die Folge
\mathl{M^n u}{} für jedes
\mathl{u \in U}{} gegen den Nullvektor.
Es sei nun
\mathl{v \in V}{} ein Verteilungsvektor, den wir wegen
\mavergleichskettedisp
{\vergleichskette
{ \sum_{i =1 }^n v_i
}
{ =} { 1
}
{ =} { \sum_{i =1 }^n w_i
}
{ } {
}
{ } {
}
}
{}{}{}
als
\mavergleichskettedisp
{\vergleichskette
{v
}
{ =} {w +u
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
mit
\mathl{u \in U}{} schreiben können. Wegen
\mavergleichskettedisp
{\vergleichskette
{M^nv
}
{ =} { M^n (w+u)
}
{ =} { M^n w +M^nu
}
{ =} { w +M^nu
}
{ } {
}
}
{}{}{}
und der Vorüberlegung konvergiert diese Folge gegen $w$.
\inputbemerkung
{}
{
In der Situation von Lemma 54.8 kann man die Eigenverteilung dadurch finden, dass man ein lineares Gleichungssystem löst. Wenn es sich um eine sehr große Matrix \zusatzklammer {man denke an $\geq 10^9$ Knoten} {} {} handelt, ist eine solche Rechnung sehr aufwändig. Häufig muss man die Eigenverteilung aber gar nicht genau kennen, sondern es reicht eine gute Approximation aus. Dann kann man zu einer beliebigen Startverteilung endlich viele Iterationen ausrechnen und weiß aufgrund von Satz 54.11, dass dieses Verfahren die Eigenverteilung beliebig gut approximiert. Eine Suchmaschine im Internet erstellt beispielsweise zu einem Suchbegriff eine Reihenfolge von Seiten, die diesen Begriff enthalten. Wie kommt diese Reihenfolge zustande? Die wahre Antwort ist, zumindest für die ersten Einträge, dass dies davon abhängt, wer am meisten dafür zahlt. Ansonsten ist ein natürlicher Ansatz, der auch Grundlage des Page ranks ist, die numerische Ordnung in der Eigenverteilung als ausschlaggebend anzusehen. Der oberste Eintrag ist derjenige, bei dem die meisten Leute \anfuehrung{schließlich}{} landen, wenn sie mit gleicher Wahrscheinlichkeit den möglichen Links folgen. Diese Wanderungsbewegung wird eben durch die stochastische Matrix, die man im Sinne von Beispiel 54.5
erhält, modelliert\zusatzfussnote {Unter \stichwort {Modellierung} {} versteht man in der \zusatzklammer {insbesondere angewandten} {} {} Mathematik den Vorgang, realweltliche Phänomene mathematisch zu erfassen, zu verstehen und zu beeinflussen. Mathematisch modelliert werden physikalische Prozesse, Wetterphänomene, Finanzaktionen, etc.
}
Den numerischen Unterschied zwischen dem exakten Lösen eines linearen Gleichungssystems zur Bestimmung eines Eigenvektors und der \stichwort {Potenzmethode} {} kann man folgendermaßen erfassen. Sei eine $n \times n$-Matrix gegeben. Das Gaussche Eliminationsverfahren braucht, um die erste Variable in $n-1$ Gleichungen zu eliminieren,
\mavergleichskette
{\vergleichskette
{ n(n-1)
}
{ \sim }{n^2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
Multiplikationen
\zusatzklammer {Additionen sind vom Rechenaufwand her einfacher und werden hier nicht berücksichtigt} {} {,}
die Größenordung der Multiplikationen der Gesamtelimination ist somit
\mavergleichskettedisp
{\vergleichskette
{n^2 + (n-1)^2 + (n-2)^2 + \cdots + 1
}
{ \sim} { { \frac{ 1 }{ 6 } } n^3
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Dagegen sind für die Auswertung der Matrix auf einen Vektor $n^2$ Multiplikationen nötig. Wenn man $k$ Iterationen berechnen möchte, braucht man also
\mathl{k n^2}{} Operationen. Wenn also $k$ deutlich kleiner als $n$ gewählt werden kann, so ist der Gesamtrechenaufwand deutlich kleiner.