Übersicht algebraische Strukturen

7 files changed, 196 insertions, 8 deletions

diff --git a/buch/chapters/80-wahrscheinlichkeit/google.tex b/buch/chapters/80-wahrscheinlichkeit/google.tex
index c1318fe..42cd0a1 100644
--- a/buch/chapters/80-wahrscheinlichkeit/google.tex
+++ b/buch/chapters/80-wahrscheinlichkeit/google.tex
@@ -401,9 +401,9 @@ A
 \]
 vereinfacht werden.
 
-\begin{definition}
+\begin{definition}[Google-Matrix]
 Die Matrix
-\[
+\begin{equation}
 G
 =
 \alpha H
@@ -416,7 +416,8 @@ G
 \alpha H
 +
 (1-\alpha)qU^t
-\]
+\label{buch:wahrscheinlichkeit:eqn:google-matrix}
+\end{equation}
 heisst die
 {\em Google-Matrix}.
 \index{Google-Matrix}%
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/Makefile b/buch/chapters/80-wahrscheinlichkeit/images/Makefile
index 8042eb1..24c0631 100644
--- a/buch/chapters/80-wahrscheinlichkeit/images/Makefile
+++ b/buch/chapters/80-wahrscheinlichkeit/images/Makefile
@@ -4,7 +4,8 @@
 # (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschulen
 #
 all:	dreieck.pdf trenn.pdf vergleich.pdf vergleich.jpg \
-	positiv.pdf positiv.jpg diffusion.png diffusion.pdf
+	positiv.pdf positiv.jpg diffusion.png diffusion.pdf \
+	konvex.pdf
 
 # Visualisierung diffusion in einer primitiven Matrix
 diffusion.pdf:	diffusion.tex diffusion.jpg
@@ -53,3 +54,7 @@ dreieck.pdf:	dreieck.tex drei.inc
 
 drei.inc:	dreieck.m
 	octave dreieck.m
+
+# Konvex
+konvex.pdf:	konvex.tex
+	pdflatex konvex.tex
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/konvex.pdf b/buch/chapters/80-wahrscheinlichkeit/images/konvex.pdf
new file mode 100644
index 0000000..f77cc62
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/konvex.pdf
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/konvex.tex b/buch/chapters/80-wahrscheinlichkeit/images/konvex.tex
new file mode 100644
index 0000000..05bbc60
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/konvex.tex
@@ -0,0 +1,75 @@
+%
+% konvex.tex -- template for standalon tikz images
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\documentclass[tikz]{standalone}
+\usepackage{amsmath}
+\usepackage{times}
+\usepackage{txfonts}
+\usepackage{pgfplots}
+\usepackage{csvsimple}
+\usetikzlibrary{arrows,intersections,math,calc,hobby}
+\begin{document}
+\def\skala{1}
+\begin{tikzpicture}[>=latex,thick,scale=\skala]
+
+\def\punkt#1{
+	\fill[color=white] #1 circle[radius=0.05];
+	\draw #1 circle[radius=0.05];
+}
+
+\begin{scope}[xshift=-3cm]
+\coordinate (O) at (0,0);
+\coordinate (A) at (-1,5);
+\coordinate (B) at (3,2);
+\draw[->] (O) -- (A);
+\draw[->] (O) -- (B);
+\begin{scope}
+\clip (-2,0) rectangle (4,6);
+\draw[color=red!40,line width=0.4pt] ($2*(B)-(A)$) -- ($2*(A)-(B)$);
+\end{scope}
+\draw[color=red,line width=1.5pt] (A) -- (B);
+\punkt{(O)}
+\punkt{(A)}
+\punkt{(B)}
+\node at (O) [below left] {$O$};
+\node at (A) [above right] {$A$};
+\node at (B) [above right] {$B$};
+\node at ($0.5*(A)$) [left] {$\vec{a}$};
+\node at ($0.5*(B)$) [below right] {$\vec{b}$};
+\fill[color=white] ($0.6*(A)+0.4*(B)$) circle[radius=0.05];
+\draw[color=red] ($0.6*(A)+0.4*(B)$) circle[radius=0.05];
+\node[color=red] at ($0.6*(A)+0.4*(B)$) [above right] {$t\vec{a}+(1-t)\vec{b}$};
+\end{scope}
+
+\begin{scope}[xshift=4cm]
+\coordinate (O) at (0,0);
+\coordinate (A) at (-1,3);
+\coordinate (B) at (2,5);
+\coordinate (C) at (4,1);
+\draw[->] (O) -- (A);
+\draw[->] (O) -- (B);
+\draw[->] (O) -- (C);
+\fill[color=red!50,opacity=0.5] (A) -- (B) -- (C) -- cycle;
+\draw[color=red,line width=1.5pt,opacity=0.7] (A) -- (B) -- (C) -- cycle;
+\punkt{(O)}
+\punkt{(A)}
+\punkt{(B)}
+\punkt{(C)}
+\node at (O) [below left] {$O$};
+\node at (A) [left] {$P_1$};
+\node at (B) [above] {$P_2$};
+\node at (C) [right] {$P_3$};
+\node at ($0.5*(A)$) [left] {$\vec{p}_1$};
+\node at ($0.3*(B)$) [right] {$\vec{p}_2$};
+\node at ($0.5*(C)$) [below] {$\vec{p}_3$};
+\fill[color=white] ($0.5*(C)+0.3*(A)+0.2*(B)$) circle[radius=0.05];
+\draw[color=red] ($0.5*(C)+0.3*(A)+0.2*(B)$) circle[radius=0.05];
+\node[color=red] at ($0.5*(C)+0.3*(A)+0.2*(B)$) [above] {$\displaystyle\sum_{t=1}^3 t_i\vec{p}_i$};
+\end{scope}
+
+
+\end{tikzpicture}
+\end{document}
+
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf
index bbcc95a..f065f76 100644
--- a/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf
+++ b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf
diff --git a/buch/chapters/80-wahrscheinlichkeit/markov.tex b/buch/chapters/80-wahrscheinlichkeit/markov.tex
index 0d77926..9df7e89 100644
--- a/buch/chapters/80-wahrscheinlichkeit/markov.tex
+++ b/buch/chapters/80-wahrscheinlichkeit/markov.tex
@@ -439,6 +439,17 @@ Das Problem, die stationären Verteilungen von $T$ zu finden, ist
 auf die Untermatrizen $T_i$ reduziert worden.
 
 \subsubsection{Die konvexe Menge der stationären Verteilungen}
+\begin{figure}
+\centering
+\includegraphics{chapters/80-wahrscheinlichkeit/images/konvex.pdf}
+\caption{Die Konvexe Kombination von Vektoren $\vec{p}_1,\dots,\vec{p}_n$ ist
+eine Summe der Form $\sum_{i=1}^n t_i\vec{p}_i$ wobei die $t_i\ge 0$
+sind mit $\sum_{i=1}^nt_i=1$.
+Für zwei Punkte bilden die konvexen Kombinationen die Verbindungsstrecke
+zwischen den Punkten, für drei Punkte in drei Dimensionen spannen die
+konvexen Kombinationen ein Dreieck auf.
+\label{buch:wahrscheinlichkeit:fig:konvex}}
+\end{figure}
 Die stationären Verteilungen
 \[
 \operatorname{Stat}(T)
@@ -674,6 +685,7 @@ E&R\\
 \right).
 \]
 Die Matrix $R$ beschreibt die Wahrscheinlichkeiten, mit denen man
+ausgehend von einem transienten Zustand
 in einem bestimmten absorbierenden Zustand landet.
 Die Matrix $Q$ beschreibt die Übergänge, bevor dies passiert.
 Die Potenzen von $T$ sind
@@ -698,7 +710,7 @@ E&R+RQ+RQ^2 \\
 \end{array}
 \right),
 \;
-\dots
+\dots,
 \;
 T^k
 =
@@ -740,9 +752,90 @@ Wenn der Prozess genau im Schritt $k$ zum ersten Mal Zustand $i$
 ankommt, dann ist $E(k)$ die mittlere Wartezeit.
 Der Prozess verbringt also zunächst $k-1$ Schritte in transienten
 Zuständen, bevor er in einen absorbierenden Zustand wechselt.
-Die Wahrscheinlichkeit ausgehend vom transjenten Zustand $j$ in
-genau $k$ Schritten im absorbierenden Zustand zu landen ist
-das Matrix-Element $(i,j)$ der Matrix $RQ^{k-1}$.
+
+Wir brauchen die Wahrscheinlichkeit für einen Entwicklung des Zustandes
+ausgehend vom Zustand $j$, die nach $k-1$ Schritten im Zustand $l$
+landet, von wo er in den absorbierenden Zustand wechselt.
+Diese Wahrscheinlichkeit ist
+\[
+P(X_k = i\wedge X_{k-1} = l \wedge X_0=j)
+=
+\sum_{i_1,\dots,i_{k-2}}
+r_{il} q_{li_{k-2}} q_{i_{k-2}i_{k-3}}\dots q_{i_2i_1} q_{i_1j}
+\]
+Von den Pfaden, die zur Zeit $k-1$ im Zustand $l$ ankommen gibt es
+aber auch einige, die nicht absorbiert werden.
+Für die Berechnung der Wartezeit möchten wir nur die Wahrscheinlichkeit
+innerhalb der Menge der Pfade, die auch tatsächlich absorbiert werden,
+das ist die bedingte Wahrscheinlichkeit
+\begin{equation}
+\begin{aligned}
+P(X_k = i\wedge X_{k-1} = l \wedge X_0=j|X_k=i)
+&=
+\frac{
+P(X_k = i\wedge X_{k-1} = l \wedge X_0=j)
+}{
+P(X_k=i)
+}
+\\
+&=
+\sum_{i_1,\dots,i_{k-2}}
+q_{li_{k-2}} q_{i_{k-2}i_{k-3}}\dots q_{i_2i_1} q_{i_1j}.
+\end{aligned}
+\label{buch:wahrscheinlichkeit:eqn:ankunftswahrscheinlichkeit}
+\end{equation}
+Auf der rechten Seite steht das Matrixelement $(l,j)$ von $Q^{k-1}$.
+
+% XXX Differenz 
+
+Für die Berechnung der erwarteten Zeit ist müssen wir die
+Wahrscheinlichkeit mit $k$ multiplizieren und summieren:
+\begin{align}
+E(k)
+&=
+\sum_{k=0}^\infty
+k(
+q^{(k)}_{lj} 
+-
+q^{(k-1)}_{lj} 
+)
+\notag
+\\
+&=
+\dots
++
+(k+1)(
+q^{(k)}_{lj} 
+-
+q^{(k+1)}_{lj} 
+)
++
+k(
+q^{(k-1)}_{lj} 
+-
+q^{(k)}_{lj} 
+)
++
+\dots
+\label{buch:wahrscheinlichkeit:eqn:telescope}
+\\
+&=
+\dots
++
+q^{(k-1)}_{lj}
++
+\dots
+=
+\sum_{k} q^{(k)}_{lj}.
+\notag
+\end{align}
+In zwei benachbarten Termen in 
+\eqref{buch:wahrscheinlichkeit:eqn:telescope}
+heben sich die Summanden $kq^{(k)}_{lj}$ weg, man spricht von
+einer teleskopischen Reihe.
+Die verbleibenden Terme sind genau die Matrixelemente der Fundamentalmatrix $N$.
+Die Fundamentalmatrix enthält also im Eintrag $(l,j)$ die Wartezeit
+bis zur Absorption über den Zustand $l$.
 
 \subsubsection{Wartezeit}
 % XXX Mittlere Zeit bis zu einem bestimmten Zustand
diff --git a/buch/chapters/80-wahrscheinlichkeit/positiv.tex b/buch/chapters/80-wahrscheinlichkeit/positiv.tex
index c49ffd6..9f8f38f 100644
--- a/buch/chapters/80-wahrscheinlichkeit/positiv.tex
+++ b/buch/chapters/80-wahrscheinlichkeit/positiv.tex
@@ -689,6 +689,18 @@ Dann gibt es einen positiven Eigenvektor zum Eigenwert $\varrho(A)$,
 mit geometrischer und algebraischer Vielfachheit $1$.
 \end{satz}
 
+\begin{beispiel}
+In der Google-Matrix mit freiem Willen
+nach
+\eqref{buch:wahrscheinlichkeit:eqn:google-matrix}
+enthält den Term $((1-\alpha)/N)UU^t$.
+Die Matrix $UU^t$ ist eine Matrix aus lauter Einsen, der Term
+ist also für $\alpha < 1$ eine positive Matrix.
+Die Google-Matrix ist daher eine positive Matrix.
+Nach dem Satz von Perron-Frobenius ist die Grenzverteilung
+eindeutig bestimmt.
+\end{beispiel}
+
 Der Satz~\ref{buch:wahrscheinlichkeit:satz:perron-frobenius}
 von Perron-Frobenius kann auf primitive Matrizen verallgemeinert
 werden.
@@ -704,4 +716,6 @@ und er hat geometrische und algebraische Vielfachheit $1$.
 Nach Voraussetzung gibt es ein $n$ derart, dass $A^n>0$.
 Für $A^n$ gelten die Resultate von 
 Satz~\ref{buch:wahrscheinlichkeit:satz:perron-frobenius}.
+
+XXX TODO
 \end{proof}