%\section{Umkehrsatz und Anwendungen}
\subsection{Markov-Ketten*}

\begin{Bemerkungl}
  Hier  eine Anwendung des Banach'schen Fixpunktsatzes, die 
eigentlich eher in die lineare Algebra oder Wahrscheinlichkeitstheorie
geh"ort.
\end{Bemerkungl}
\begin{Bemerkungl}
Gegeben sei eine endliche Menge $E,$ deren Elemente 
\defnoind{Zust"ande}\index{Zustand!bei Markovkette}
hei"sen m"ogen.\index{Markovkette}
Gegeben sei weiter eine $(E\times E)$-Matrix $Q$ 
mit Eintr"agen in $[0,1]$ und Spaltensummen Eins, in Formeln
eine Abbildung 
$Q:E^2\ra [0,1],$ $(i,j)\mapsto Q_{ij}$ mit $\sum_{i}
Q_{ij} =1$ f"ur alle $j.$ 
Wir nennen $Q_{ij}$
die {\bf "Ubergangswahrscheinlichkeit\index{"Ubergangswahrscheinlichkeit} 
vom Zustand $j$ in den Zustand
$i$} und unsere Forderung $\sum_{i}
Q_{ij} =1$ f"ur alle $j$ bedeutet, da"s \glqq vom Zustand $j$ aus
im n"achsten Schritt
mit Wahrscheinlichkeit Eins wieder einer
unserer Zust"ande  erreicht werden soll\grqq.
Das Datum $(E,Q)$ nennen wir eine {\bf Markov-Kette}.\index{Markov-Kette} 
Beginnen wir mit einer Wahrscheinlichkeitsverteilung $p$ auf $E$, also
einer Abbildung $p:E \rightarrow \Bbb{R}_{\geq 0}$ mit $\sum_{i\in E}
p(i) =1,$ und fassen sie als einen Spaltenvektor auf, so stellt sich nach
einem Schritt die Verteilung $Q p$ ein 
und nach $n$ Schritten  die Verteilung $Q^n p$.
Wir stellen uns nun die Frage, 
unter welchen Umst"anden die Folge der
$Q^n p$ f"ur alle $p$ konvergiert, 
unter welchen Umst"anden ihr Grenzwert
zus"atzlich gar nicht von $p$ abh"angt, 
und wie schnell unsere Folge im Zweifelsfall
konvergiert.
\end{Bemerkungl}

\begin{Beispiel}
  Zu einem endlichen K"ocher im Sinne von \eref{DKo}{LA2} mit der
zus"atzlichen Eigenschaft, da"s von jeder seiner Ecken 
mindestens ein Pfeil 
ausgeht, erhalten wir die Markov-Kette der \glqq zuf"alligen Wanderungen 
in unserem K"ocher\grqq\  wie folgt: Als Zust"ande nehmen wir die Ecken des 
K"ochers und denken uns dabei, da"s sich ein Wanderer an besagter 
Ecke befinden m"oge. In jedem Zeitschritt sucht sich unser Wanderer dann
zuf"allig einen ausgehenden Pfeil aus und wandert auf diesem zur 
n"achsten Ecke. Verfeinern wir unsere Regel dadurch, da"s wir
jedem Pfeil $i\leftarrow j$ noch eine Wahrscheinlichkeit $ Q_{ij}$
zuordnen, mit der er von unserem Wanderer ausgesucht wird,
und fassen daf"ur alle mehrfachen Pfeile zwischen je zwei 
vorgegebenen Ecken zu einem einfachen Pfeil mit
entsprechend h"oherer Wahrscheinlichkeit zusammen, so 
sind wir auch schon wieder beim allgemeinen Fall gelandet. 
\end{Beispiel}




\begin{Beispiel}[\textbf{Urnenmodell 
von Ehrenfest}]\index{Urnenmodell}\index{Ehrenfest!Urnenmodell}
In zwei durch ein Loch verbundenen Kammern befinden sich insgesamt
$N\geq 1$ nicht unterscheidbare 
Teilchen. Wir betrachten den Raum $E =\{0,1,\ldots, N\}$ aller
\glqq Zust"ande\grqq, wobei der Zustand $i$ bedeuten m"oge, da"s sich $i$ Teilchen
in der linken Kammer und die restlichen 
$N-i$ Teilchen in der rechten Kammer befinden. Als
"Ubergangswahrscheinlichkeiten w"ahlen wir
\begin{displaymath}
Q_{ij} = \left\{ \begin{array}{cl}
j/N & i=j-1;\\
(N-j)/N & i= j+1;\\
0 & \text{sonst}.
\end{array}\right.
\end{displaymath}
In jedem Zeitschritt wechselt also genau ein Teilchen die Kammer,
und die Wahrscheinlichkeit, da"s das ein Teilchen aus einer Kammer
mit $j$ Teilchen ist, betr"agt genau $j/N$.
In diesem Fall konvergiert die Folge $Q^n p$ nicht f"ur alle $p$, da sich
ja in jeder Kammer immer abwechselnd erst eine gerade und dann wieder eine
ungerade Anzahl von Teilchen befindet.
\end{Beispiel}

  \begin{Satz}[\textbf{Konvergenz endlicher Markov-Ketten}] 
    Ist bei einer endlichen Markov-Kette $(E,Q)$ 
die "Ubergangswahrscheinlichkeit
    zwischen je zwei Zust"anden positiv, in Formeln $Q_{ij} > 0 \;\forall
    i,j,$ so gibt es genau eine stabile Verteilung $s$ und f"ur jede
    Anfangsverteilung $p$ gilt\label{KEMa}
    \begin{equation*}
      \lim_{n \rightarrow \infty} Q^n p = s
    \end{equation*}
  \end{Satz}

 %  \begin{Bemerkunge}
%    Es reicht auch die sch"achere Annahme, da"s 
%   \end{Bemerkunge}


% \begin{Bemerkungl}
%   Ich w"u"ste gerne, ob und wenn ja
% wie die Beziehung zur Konvexgeometrie \ref{EWKK}
% pr"azisiert werden kann.
% \end{Bemerkungl}
\begin{Bemerkunge}[\textbf{Bewertung von Seiten im Netz}]
  Die Bewertung  von Seiten im Netz  durch Suchmaschinen 
baut auf der Vorstellung auf, da"s ein Surfer 
auf einer gegebenen Seite jeden der Verweise zu weiteren Seiten
 mit gleicher Wahrscheinlichkeit
 anklickt. 
Damit er nicht bei einer Seite h"angenbleiben kann, die auf gar keine weitere
Seite verweist, denkt man sich dabei auf jeder Seite zus"atzlich einen Verweis 
angebracht, der einen beim Daraufklicken zu einer zuf"allig ausgesuchten Seite 
schickt, und der mit derselben Wahrscheinlichkeit
 angeklickt wird wie alle anderen.
Die durch diese Markovkette bestimmte stabile Verteilung 
ist dann die gesuchte Bewertung von Seiten im Netz. Eine Seite ist damit
desto h"oher bewertet, je mehr Seiten darauf verweisen, wobei Verweise
von  Seiten, die ihrerseits h"oher bewertet sind,
entsprechend st"arker gewichtet werden.
  \end{Bemerkunge}
  \begin{proof}
    Sicher  beschreibt die Matrix
 $Q$ einen Endomorphismus von $\op{Ens}(E,\DR)$, der jeden Vektor der
    Standardbasis ins Innere des positiven Quadranten kippt und der die affine
    Hyperebene $ H= \{ (x_i)_{i \in E} \mid \sum x_i =1\} $ auf sich selbst
    abbildet.  Es scheint mir damit anschaulich klar, da"s $Q$ eine Kontraktion
    $Q :H \ra H$ definiert und da"s der Fixpunkt dieser Kontraktion,
dessen Existenz durch den Banach'schen Fixpunktsatz
\eref{BFS}{AN3} gesichert ist, im Innern
    des positiven Quadranten $\op{Ens}(E,\mathbb{R}_{>0})$ liegen mu"s.  Um
    das zu beweisen reicht es zu zeigen, da"s $Q$ bez"uglich irgendeiner Norm
    kontrahierend wirkt auf der linearen Hyperebene $L$, die gegeben wird durch
    die Gleichung $\sum x_i =0$.  Wir zeigen das bez"uglich der Norm $|x| =
    \sum |x_i|$.  Sei $\delta$ der kleinste Eintrag von $Q$. Schreiben wir $Q
    = \delta U +R$ f"ur $U$ die Matrix mit einer Eins in jedem Eintrag, so hat
    $R$ nur nichtnegative Eintr"age.  Damit erhalten wir f"ur $x\in L$ unschwer
    \begin{equation*}
      |Qx| = |Rx| = \sum_i \left|\sum_j R_{ij} x_j\right| 
      \leq \sum_{i,j} R_{ij} |x_j| = \lambda
      |x|
    \end{equation*}
    f"ur $\lambda = 1 -n \delta$ die Summe der Eintr"age von $R$ in einer und
    jeder Spalte.  Also ist $Q : H \ra H$ kontrahierend und hat genau einen
    Fixvektor $s,$ dessen Koordinaten alle positiv sein m"ussen.  Alle anderen
    Eigenwerte von $Q$ m"ussen auch Eigenwerte der Einschr"ankung auf die
    lineare Ebene $L$ mit der Gleichung 
$\sum x_i =0 $ sein und sind folglich im Absolutbetrag
    beschr"ankt durch unsere Kontraktionskonstante 
$\lambda=1 -n \delta$ . % , etwa nach %     \eref{SPRR}{AN3}
\end{proof}