aboutsummaryrefslogtreecommitdiffstats
path: root/buch/chapters/80-wahrscheinlichkeit
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/Makefile.inc1
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/chapter.tex1
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/google.tex86
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/Makefile79
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/diffusion.jpgbin0 -> 203856 bytes
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/diffusion.m33
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/diffusion.pdfbin0 -> 220008 bytes
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/diffusion.pngbin0 -> 265323 bytes
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/diffusion.pov87
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/diffusion.tex46
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/dreieck.m41
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/dreieck.pdfbin0 -> 23945 bytes
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/dreieck.tex90
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/internet.pdfbin0 -> 10681 bytes
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/internet.tex58
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/konvex.pdfbin0 -> 24033 bytes
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/konvex.tex75
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/markov.pdfbin0 -> 28921 bytes
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/markov.tex99
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/markov2.pdfbin0 -> 31027 bytes
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/markov2.tex113
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/markov3.pdfbin0 -> 30437 bytes
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/markov3.tex113
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/positiv.jpgbin0 -> 111361 bytes
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/positiv.m36
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/positiv.pdfbin0 -> 124093 bytes
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/positiv.pngbin0 -> 191808 bytes
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/positiv.pov137
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/positiv.tex51
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/spielB.pdfbin0 -> 9917 bytes
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/spielB.tex59
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/spielBtilde.pdfbin0 -> 14592 bytes
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/spielBtilde.tex59
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/trenn.pdfbin0 -> 13272 bytes
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/trenn.tex44
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/vergleich.jpgbin0 -> 105809 bytes
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdfbin0 -> 120558 bytes
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/vergleich.pngbin0 -> 223136 bytes
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/vergleich.pov203
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/images/vergleich.tex46
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/markov.tex914
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/parrondo.tex798
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/positiv.tex721
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/rechnungen/btilde.maxima103
44 files changed, 4031 insertions, 62 deletions
diff --git a/buch/chapters/80-wahrscheinlichkeit/Makefile.inc b/buch/chapters/80-wahrscheinlichkeit/Makefile.inc
index 6546e01..6fd104c 100644
--- a/buch/chapters/80-wahrscheinlichkeit/Makefile.inc
+++ b/buch/chapters/80-wahrscheinlichkeit/Makefile.inc
@@ -7,5 +7,6 @@
CHAPTERFILES = $(CHAPTERFILES) \
chapters/80-wahrscheinlichkeit/google.tex \
chapters/80-wahrscheinlichkeit/markov.tex \
+ chapters/80-wahrscheinlichkeit/positiv.tex \
chapters/80-wahrscheinlichkeit/parrondo.tex \
chapters/80-wahrscheinlichkeit/chapter.tex
diff --git a/buch/chapters/80-wahrscheinlichkeit/chapter.tex b/buch/chapters/80-wahrscheinlichkeit/chapter.tex
index e9e7531..85b6d8c 100644
--- a/buch/chapters/80-wahrscheinlichkeit/chapter.tex
+++ b/buch/chapters/80-wahrscheinlichkeit/chapter.tex
@@ -33,4 +33,5 @@ dargestellt.
\input{chapters/80-wahrscheinlichkeit/google.tex}
\input{chapters/80-wahrscheinlichkeit/markov.tex}
+\input{chapters/80-wahrscheinlichkeit/positiv.tex}
\input{chapters/80-wahrscheinlichkeit/parrondo.tex}
diff --git a/buch/chapters/80-wahrscheinlichkeit/google.tex b/buch/chapters/80-wahrscheinlichkeit/google.tex
index bb5597d..ca78b3d 100644
--- a/buch/chapters/80-wahrscheinlichkeit/google.tex
+++ b/buch/chapters/80-wahrscheinlichkeit/google.tex
@@ -6,57 +6,6 @@
\section{Google-Matrix
\label{buch:section:google-matrix}}
\rhead{Google-Matrix}
-
-%
-% Ein Modell für Webseitenbesucher
-%
-\subsection{Ein Modell für Webseitenbesucher
-\label{buch:subsection:modell-fuer-webseitenbesucher}}
-\begin{figure}
-\centering
-\begin{tikzpicture}[>=latex,thick]
-\foreach \x in {0,3,6,9}{
- \foreach \y in {0,3}{
- \fill[color=white] ({\x},{\y}) circle[radius=0.3];
- \draw ({\x},{\y}) circle[radius=0.3];
- }
-}
-\node at (0,3) {$1$};
-\node at (0,0) {$2$};
-\node at (3,3) {$3$};
-\node at (3,0) {$4$};
-\node at (6,3) {$5$};
-\node at (6,0) {$6$};
-\node at (9,3) {$7$};
-\node at (9,0) {$8$};
-% 1
-\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (0,3) -- (3,3);
-\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (0,3) -- (0,0);
-% 2
-\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (0,0) to[out=-20,in=-160] (3,0);
-% 3
-\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,3) -- (6,3);
-\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,3) -- (0,0);
-% 4
-\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,0) -- (6,3);
-\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,0) -- (6,0);
-\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,0) to[out=160,in=20] (0,0);
-% 5
-\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (6,3) -- (9,3);
-\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (6,3) -- (9,0);
-\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (6,3) -- (6,0);
-% 6
-\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (6,0) to[out=20,in=160] (9,0);
-% 7
-\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (9,3) .. controls (7.5,4) .. (6,4) -- (3,4) .. controls (1.5,4) .. (0,3);
-\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (9,3) to[out=-110,in=110] (9,0);
-% 8
-\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (9,0) to[out=-160,in=-20] (6,0);
-\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (9,0) to[out=70,in=-70] (9,3);
-\end{tikzpicture}
-\caption{Modell-Internet als Beispiel für die Link-Matrix und die Google-Matrix.
-\label{buch:figure:modellinternet}}
-\end{figure}
Das Internet besteht aus einer grossen Zahl von Websites, etwa 400~Millionen
aktiven Websites, jede besteht aus vielen einzelnen Seiten.
Es ist daher angemessen von $N\approx 10^9$ verschiedenen Seiten auszugehen.
@@ -84,6 +33,18 @@ bedeutet aber auch, dass nach Synonymen oder alternative Formen eines
Wortes separat gesucht werden muss, was die Übersichtlichkeit wieder
zerstört.
+%
+% Ein Modell für Webseitenbesucher
+%
+\subsection{Ein Modell für Webseitenbesucher
+\label{buch:subsection:modell-fuer-webseitenbesucher}}
+\begin{figure}
+\centering
+\includegraphics{chapters/80-wahrscheinlichkeit/images/internet.pdf}
+\caption{Modell-Internet als Beispiel für die Link-Matrix und die Google-Matrix.
+\label{buch:figure:modellinternet}}
+\end{figure}
+
Das kombinierte Vorkommen von Wörtern oder Begriffen alleine kann also
nicht ausreichen, um die Seiten zum Beispiel einem Fachgebiet zuzuordnen.
Dazu muss eine externe Informationsquelle angezapft werden.
@@ -358,7 +319,7 @@ Da sich die Wahrscheinlichkeiten im Vektor $p$ zu $1$ summieren, gilt
\begin{pmatrix}
1&1&\dots&1
\end{pmatrix}
-}_{\displaystyle = u^t}
+}_{\displaystyle = U^t}
\begin{pmatrix}
P(S_1)\\
P(S_2)\\
@@ -369,12 +330,12 @@ P(S_N)
P(S_1)+P(S_2)+\dots+P(S_N)=1.
\]
Man erhält also die Wirkung der gewünschte Matrix $A$, indem man $p$
-erst mit dem Zeilenvektor $u^t$ und das Resultat mit $q$ multipliziert.
+erst mit dem Zeilenvektor $U^t$ und das Resultat mit $q$ multipliziert.
Es gilt daher
\[
-Ap = qu^tp
+Ap = qU^tp
\qquad\Rightarrow\qquad
-A=qu^t.
+A=qU^t.
\]
Ausmultipliziert ist dies die Matrix
\[
@@ -385,11 +346,11 @@ q_2&q_2&\dots&q_2\\
q_N&q_N&\dots&q_N
\end{pmatrix}.
\]
-Im Fall $q=\frac1Nu$ kann dies zu
+Im Fall $q=\frac1NU$ kann dies zu
\[
A
=
-\frac1N uu^t
+\frac1N UU^t
=
\frac1N
\begin{pmatrix}
@@ -401,22 +362,23 @@ A
\]
vereinfacht werden.
-\begin{definition}
+\begin{definition}[Google-Matrix]
Die Matrix
-\[
+\begin{equation}
G
=
\alpha H
+
\frac{1-\alpha}{N}
-uu^t
+UU^t
\qquad\text{oder}\qquad
G
=
\alpha H
+
-(1-\alpha)qu^t
-\]
+(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
new file mode 100644
index 0000000..8d34217
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/Makefile
@@ -0,0 +1,79 @@
+#
+# Makefile
+#
+# (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 \
+ konvex.pdf internet.pdf markov.pdf markov2.pdf markov3.pdf \
+ spielB.pdf spielBtilde.pdf
+
+# Visualisierung diffusion in einer primitiven Matrix
+diffusion.pdf: diffusion.tex diffusion.jpg
+ pdflatex diffusion.tex
+
+diffusion.png: diffusion.pov vektoren.inc
+ povray +A0.1 +W1920 +H1080 -Odiffusion.png diffusion.pov
+
+diffusion.jpg: diffusion.png
+ convert diffusion.png -density 300 -units PixelsPerInch diffusion.jpg
+
+vektoren.inc: diffusion.m
+ octave diffusion.m
+
+# Visualizierung positive Matrix
+positiv.pdf: positiv.tex positiv.jpg
+ pdflatex positiv.tex
+
+positiv.png: positiv.pov quadrant.inc
+ povray +A0.1 +W1920 +H1080 -Opositiv.png positiv.pov
+
+positiv.jpg: positiv.png
+ convert positiv.png -density 300 -units PixelsPerInch positiv.jpg
+
+quadrant.inc: positiv.m
+ octave positiv.m
+
+# Visualiziserung Vergleichstrick
+vergleich.png: vergleich.pov
+ povray +A0.1 +W1920 +H1080 -Overgleich.png vergleich.pov
+
+vergleich.jpg: vergleich.png Makefile
+ convert -extract 1110x1080+180+0 vergleich.png \
+ -density 300 -units PixelsPerInch vergleich.jpg
+
+vergleich.pdf: vergleich.tex vergleich.jpg
+ pdflatex vergleich.tex
+
+# Darstellung zum Trenntrick
+trenn.pdf: trenn.tex
+ pdflatex trenn.tex
+
+# Darstellung zur Dreiecksungleichung
+dreieck.pdf: dreieck.tex drei.inc
+ pdflatex dreieck.tex
+
+drei.inc: dreieck.m
+ octave dreieck.m
+
+# Konvex
+konvex.pdf: konvex.tex
+ pdflatex konvex.tex
+
+internet.pdf: internet.tex
+ pdflatex internet.tex
+
+markov.pdf: markov.tex
+ pdflatex markov.tex
+
+markov2.pdf: markov2.tex
+ pdflatex markov2.tex
+
+markov3.pdf: markov3.tex
+ pdflatex markov3.tex
+
+spielB.pdf: spielB.tex
+ pdflatex spielB.tex
+
+spielBtilde.pdf: spielBtilde.tex
+ pdflatex spielBtilde.tex
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/diffusion.jpg b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.jpg
new file mode 100644
index 0000000..b79b07b
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.jpg
Binary files differ
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/diffusion.m b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.m
new file mode 100644
index 0000000..ad56fe5
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.m
@@ -0,0 +1,33 @@
+#
+# diffusion.m
+#
+# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+#
+e1 = [ 1; 0; 0; 0; 0; 0 ];
+A = 0.8*eye(6) + 0.1*shift(eye(6),1) + 0.1*shift(eye(6),-1);
+A(1,1) = 0.9;
+A(6,6) = 0.9;
+A(1,6) = 0;
+A(6,1) = 0;
+
+N = 30;
+b = zeros(6,N);
+b(:,1) = e1;
+for i = (2:N)
+ b(:,i) = A * b(:,i-1);
+end
+b
+
+f = fopen("vektoren.inc", "w");
+for i = (1:N)
+ fprintf(f, "vektor(%d,%.4f,%.4f,%.4f,%.4f,%.4f,%.4f)\n", i,
+ b(1,i), b(2,i), b(3,i), b(4,i), b(5,i), b(6,i))
+end
+fclose(f);
+
+A1=A
+A2=A*A
+A3=A*A2
+A4=A*A3
+A5=A*A4
+A6=A*A5
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/diffusion.pdf b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.pdf
new file mode 100644
index 0000000..ac4c0ff
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.pdf
Binary files differ
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/diffusion.png b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.png
new file mode 100644
index 0000000..f4c6294
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.png
Binary files differ
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/diffusion.pov b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.pov
new file mode 100644
index 0000000..9b385da
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.pov
@@ -0,0 +1,87 @@
+//
+// diffusion.pov
+//
+// (c) 2021 Prof Dr Andreas Müller, OST Ostscheizer Fachhochschule
+//
+#version 3.7;
+#include "colors.inc"
+
+global_settings {
+ assumed_gamma 1
+}
+
+#declare imagescale = 0.270;
+#declare N = 30;
+#declare vscale = 10;
+#declare r = 0.08;
+
+camera {
+ location <43, 20, -50>
+ look_at <N/2+2, vscale*0.49, 3>
+ right 16/9 * x * imagescale
+ up y * imagescale
+}
+
+light_source {
+ <-4, 20, -50> color White
+ area_light <1,0,0> <0,0,1>, 10, 10
+ adaptive 1
+ jitter
+}
+
+sky_sphere {
+ pigment {
+ color rgb<1,1,1>
+ }
+}
+
+#macro saeule(xx,yy,h)
+box { <xx+0.1,0,yy+0.1>, <xx+0.9,vscale*h,yy+0.9> }
+#end
+
+#macro vektor(xx,a,b,c,d,e,f)
+ saeule(xx,5,a)
+ saeule(xx,4,b)
+ saeule(xx,3,c)
+ saeule(xx,2,d)
+ saeule(xx,1,e)
+ saeule(xx,0,f)
+#end
+
+union {
+#include "vektoren.inc"
+ pigment {
+ color rgb<0.8,1,1>*0.6
+ }
+ finish {
+ specular 0.9
+ metallic
+ }
+}
+
+union {
+#declare xx = 1;
+#while (xx <= N+1)
+ cylinder { <xx, 0, 0>, <xx, 0, 6>, r }
+ #declare xx = xx + 1;
+#end
+#declare yy = 0;
+#while (yy <= 6)
+ cylinder { <1, 0, yy>, <N+1, 0, yy>, r }
+ #declare yy = yy + 1;
+#end
+ sphere { <1,0,0>, r }
+ sphere { <1,0,6>, r }
+ sphere { <N+1,0,0>, r }
+ sphere { <N+1,0,6>, r }
+ cylinder { <1,0,6>, <1,1.1*vscale,6>, r }
+ cylinder { <1,vscale-r/2,6>, <1,vscale+r/2,6>, 2*r }
+ cone { <1,1.1*vscale,6>, 2*r, <1,1.15*vscale,6>, 0 }
+ pigment {
+ color rgb<1,0.6,1>*0.6
+ }
+ finish {
+ specular 0.9
+ metallic
+ }
+}
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/diffusion.tex b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.tex
new file mode 100644
index 0000000..ff58659
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.tex
@@ -0,0 +1,46 @@
+%
+% diffusion.tex -- Diffusion unter der Wirkung der Matrix
+%
+% (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}
+\begin{document}
+\def\skala{1}
+\begin{tikzpicture}[>=latex,thick,scale=\skala]
+
+\node at (0,0) {\includegraphics[width=12cm]{diffusion.jpg}};
+
+\node at (-6.3,-1.2) [rotate=-10] {$k=6$};
+\node at (-5.15,-0.7) [rotate=-10] {$k=1$};
+
+\node at (5.8,-3.25) [rotate=-10] {$k=6$};
+\node at (6.3,-2.5) [rotate=-10] {$k=1$};
+
+\node at (-6.2,-1.7) [rotate=26] {$n=1$};
+\node at (4.8,-3.7) [rotate=53] {$n=30$};
+
+%\foreach \x in {-6,-5.9,...,6.01}{
+% \draw[line width=0.1pt] (\x,-3.5) -- (\x,3.5);
+%}
+%\foreach \x in {-6,...,6}{
+% \draw[line width=0.5pt] (\x,-3.5) -- (\x,3.5);
+% \node at (\x,-3.5) [below] {$\x$};
+%}
+%\foreach \y in {-3.5,-3.4,...,3.51}{
+% \draw[line width=0.1pt] (-6,\y) -- (6,\y);
+%}
+%\foreach \y in {-3,...,3}{
+% \draw[line width=0.5pt] (-6,\y) -- (6,\y);
+% \node at (-6,\y) [left] {$\y$};
+%}
+%\fill (0,0) circle[radius=0.05];
+
+\end{tikzpicture}
+\end{document}
+
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/dreieck.m b/buch/chapters/80-wahrscheinlichkeit/images/dreieck.m
new file mode 100644
index 0000000..cc9661b
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/dreieck.m
@@ -0,0 +1,41 @@
+#
+# dreieck.m
+#
+# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+#
+w = 12
+N = 10
+
+rand("seed", 1);
+
+angles = 80 * rand(1,N)
+radii = 2 * rand(1,N) + 0.4
+angle = 20
+
+radii = radii * w / (cosd(angle) * sum(radii))
+radius = sum(radii)
+radius * cosd(angle)
+
+points = zeros(2,N);
+ray = zeros(2,N);
+
+p = [ 0; 0 ];
+for i = (1:N)
+ p = p + radii(1,i) * [ cosd(angles(1,i)); sind(angles(1,i)) ];
+ points(:, i) = p;
+ ray(:, i) = sum(radii(1,1:i)) * [ cosd(angle); sind(angle) ];
+end
+
+points
+
+ray
+
+fn = fopen("drei.inc", "w");
+for i = (1:N)
+ fprintf(fn, "\\coordinate (A%d) at (%.4f,%.4f);\n", i,
+ points(1,i), points(2,i));
+ fprintf(fn, "\\coordinate (B%d) at (%.4f,%.4f);\n", i,
+ ray(1,i), ray(2,i));
+end
+fprintf(fn, "\\def\\r{%.4f}\n", radius);
+fclose(fn);
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/dreieck.pdf b/buch/chapters/80-wahrscheinlichkeit/images/dreieck.pdf
new file mode 100644
index 0000000..0cca2e1
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/dreieck.pdf
Binary files differ
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/dreieck.tex b/buch/chapters/80-wahrscheinlichkeit/images/dreieck.tex
new file mode 100644
index 0000000..0935992
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/dreieck.tex
@@ -0,0 +1,90 @@
+%
+% dreieck.tex -- verallgemeinerte Dreiecksungleichung
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\documentclass[tikz]{standalone}
+\usepackage{amsmath}
+\usepackage{times}
+\usepackage{txfonts}
+\usepackage{pgfplots}
+\usepackage{csvsimple}
+\usepackage{pgf}
+\usetikzlibrary{arrows,intersections,math,calc,hobby}
+\begin{document}
+\def\skala{1}
+\begin{tikzpicture}[>=latex,thick,scale=\skala]
+
+\coordinate (O) at (0,0);
+
+\input{drei.inc}
+
+\begin{scope}
+\clip (O) rectangle (12.3,8);
+\draw[color=red!40] (O) circle[radius=\r];
+\end{scope}
+
+\draw[->] (-0.1,0) -- (12.3,0) coordinate[label={$\Re z$}];
+\draw[->] (0,-0.1) -- (0,8.3) coordinate[label={right:$\Im z$}];
+
+\fill[color=blue] (A1) circle[radius=0.05];
+\fill[color=blue] (A2) circle[radius=0.05];
+\fill[color=blue] (A3) circle[radius=0.05];
+\fill[color=blue] (A4) circle[radius=0.05];
+\fill[color=blue] (A5) circle[radius=0.05];
+\fill[color=blue] (A6) circle[radius=0.05];
+\fill[color=blue] (A7) circle[radius=0.05];
+\fill[color=blue] (A8) circle[radius=0.05];
+\fill[color=blue] (A9) circle[radius=0.05];
+\fill[color=blue] (A10) circle[radius=0.05];
+\draw[color=blue] (O) -- (A1);
+\draw[color=blue] (A1) -- (A2);
+\draw[color=blue] (A2) -- (A3);
+\draw[color=blue] (A3) -- (A4);
+\draw[color=blue] (A4) -- (A5);
+\draw[color=blue] (A5) -- (A6);
+\draw[color=blue] (A6) -- (A7);
+\draw[color=blue] (A7) -- (A8);
+\draw[color=blue] (A8) -- (A9);
+\draw[color=blue] (A9) -- (A10);
+\draw[->,color=blue!40] (O) -- (A10);
+\node[color=blue] at ($0.5*(A1)$) [left] {$z_1$};
+\node[color=blue] at ($0.5*(A1)+0.5*(A2)$) [left] {$z_2$};
+\node[color=blue] at ($0.5*(A2)+0.5*(A3)$) [above] {$z_3$};
+\node[color=blue] at ($0.5*(A3)+0.5*(A4)$) [above] {$z_4$};
+\node[color=blue] at ($0.5*(A4)+0.5*(A5)$) [below right] {$z_5$};
+\node[color=blue] at ($0.5*(A5)+0.5*(A6)$) [left] {$z_6$};
+\node[color=blue] at ($0.5*(A6)+0.5*(A7)$) [left] {$z_7$};
+\node[color=blue] at ($0.5*(A7)+0.5*(A8)$) [above] {$z_8$};
+\node[color=blue] at ($0.5*(A8)+0.5*(A9)$) [left] {$z_9$};
+\node[color=blue] at ($0.5*(A9)+0.5*(A10)$) [above] {$z_{10}$};
+\node[color=blue] at ($0.8*(A10)$) [rotate=35,below] {$\displaystyle\sum_{i=1}^n z_i$};
+
+\draw[->,color=red] (O) -- (B10);
+\fill[color=red] (B1) circle[radius=0.05];
+\fill[color=red] (B2) circle[radius=0.05];
+\fill[color=red] (B3) circle[radius=0.05];
+\fill[color=red] (B4) circle[radius=0.05];
+\fill[color=red] (B5) circle[radius=0.05];
+\fill[color=red] (B6) circle[radius=0.05];
+\fill[color=red] (B7) circle[radius=0.05];
+\fill[color=red] (B8) circle[radius=0.05];
+\fill[color=red] (B9) circle[radius=0.05];
+\fill[color=red] (B10) circle[radius=0.05];
+
+\node[color=red] at ($0.5*(B1)$) [above] {$|z_1|c$};
+\node[color=red] at ($0.5*(B1)+0.5*(B2)$) [above] {$|z_2|c$};
+\node[color=red] at ($0.5*(B2)+0.5*(B3)$) [above] {$|z_3|c$};
+\node[color=red] at ($0.5*(B3)+0.5*(B4)$) [above] {$|z_4|c$};
+\node[color=red] at ($0.5*(B4)+0.5*(B5)$) [above] {$|z_5|c$};
+\node[color=red] at ($0.5*(B5)+0.5*(B6)$) [above] {$|z_6|c$};
+\node[color=red] at ($0.5*(B6)+0.5*(B7)$) [above] {$|z_7|c$};
+\node[color=red] at ($0.5*(B7)+0.5*(B8)$) [above] {$|z_8|c$};
+\node[color=red] at ($0.5*(B8)+0.5*(B9)$) [above] {$|z_9|c$};
+\node[color=red] at ($0.5*(B9)+0.5*(B10)$) [above] {$|z_{10}|c$};
+
+\node[color=red] at ($0.8*(B10)$) [rotate=20,below] {$\displaystyle c\sum_{i=1}^n |z_i|$};
+
+\end{tikzpicture}
+\end{document}
+
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/internet.pdf b/buch/chapters/80-wahrscheinlichkeit/images/internet.pdf
new file mode 100644
index 0000000..12eaf1e
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/internet.pdf
Binary files differ
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/internet.tex b/buch/chapters/80-wahrscheinlichkeit/images/internet.tex
new file mode 100644
index 0000000..1b384ad
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/internet.tex
@@ -0,0 +1,58 @@
+%
+% internet.tex -- Modellinternet
+%
+% (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}
+\begin{document}
+\def\skala{1}
+\begin{tikzpicture}[>=latex,thick,scale=\skala]
+
+\foreach \x in {0,3,6,9}{
+ \foreach \y in {0,3}{
+ \fill[color=white] ({\x},{\y}) circle[radius=0.3];
+ \draw ({\x},{\y}) circle[radius=0.3];
+ }
+}
+\node at (0,3) {$1$};
+\node at (0,0) {$2$};
+\node at (3,3) {$3$};
+\node at (3,0) {$4$};
+\node at (6,3) {$5$};
+\node at (6,0) {$6$};
+\node at (9,3) {$7$};
+\node at (9,0) {$8$};
+% 1
+\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (0,3) -- (3,3);
+\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (0,3) -- (0,0);
+% 2
+\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (0,0) to[out=-20,in=-160] (3,0);
+% 3
+\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,3) -- (6,3);
+\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,3) -- (0,0);
+% 4
+\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,0) -- (6,3);
+\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,0) -- (6,0);
+\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,0) to[out=160,in=20] (0,0);
+% 5
+\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (6,3) -- (9,3);
+\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (6,3) -- (9,0);
+\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (6,3) -- (6,0);
+% 6
+\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (6,0) to[out=20,in=160] (9,0);
+% 7
+\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (9,3) .. controls (7.5,4) .. (6,4) -- (3,4) .. controls (1.5,4) .. (0,3);
+\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (9,3) to[out=-110,in=110] (9,0);
+% 8
+\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (9,0) to[out=-160,in=-20] (6,0);
+\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (9,0) to[out=70,in=-70] (9,3);
+
+\end{tikzpicture}
+\end{document}
+
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
Binary files differ
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/markov.pdf b/buch/chapters/80-wahrscheinlichkeit/images/markov.pdf
new file mode 100644
index 0000000..fba9489
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/markov.pdf
Binary files differ
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/markov.tex b/buch/chapters/80-wahrscheinlichkeit/images/markov.tex
new file mode 100644
index 0000000..72f3b85
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/markov.tex
@@ -0,0 +1,99 @@
+%
+% markov2.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}
+\begin{document}
+\def\skala{1}
+\begin{tikzpicture}[>=latex,thick,scale=\skala]
+
+\def\punkt#1#2#3{
+ \fill[color=white] #1 circle[radius=0.10];
+ \fill[color=#2] #1 circle[radius=0.13];
+ \node[color=white] at #1 {$\scriptstyle #3$};
+}
+
+\def\xs{2.5}
+\def\ys{1}
+
+\foreach \x in {0,...,5}{
+ \draw[color=red,line width=0.5pt]
+ ({\x*\xs},{-0.7*\ys}) -- ({\x*\xs},{-6.5*\ys});
+}
+
+\def\dotradius{0.04}
+
+\def\dotrow#1#2{
+ \punkt{({#1*\xs},{-1*\ys})}{#2}{1}
+ \punkt{({#1*\xs},{-2*\ys})}{#2}{2}
+ \punkt{({#1*\xs},{-3*\ys})}{#2}{3}
+ \punkt{({#1*\xs},{-4*\ys})}{#2}{4}
+ \fill[color=#2] ({#1*\xs},{-5*\ys-0.3}) circle[radius=\dotradius];
+ \fill[color=#2] ({#1*\xs},{-5*\ys-0.15}) circle[radius=\dotradius];
+ \fill[color=#2] ({#1*\xs},{-5*\ys}) circle[radius=\dotradius];
+ \fill[color=#2] ({#1*\xs},{-5*\ys+0.15}) circle[radius=\dotradius];
+ \fill[color=#2] ({#1*\xs},{-5*\ys+0.3}) circle[radius=\dotradius];
+ \punkt{({#1*\xs},{-6*\ys})}{#2}{s}
+}
+
+\def\fan#1#2{
+ \foreach \x in {1,2,3,4,6}{
+ \foreach \y in {1,2,3,4,6}{
+ \draw[->,shorten >= 2mm,shorten <= 2mm,color=#2]
+ ({#1*\xs},{-\x*\ys})
+ --
+ ({(#1+1)*\xs},{-\y*\ys});
+ }
+ }
+}
+
+\begin{scope}
+\clip (-0.5,{-6.5*\ys}) rectangle ({5*\xs+0.5},-0.5);
+\fan{-1}{gray}
+\fan{0}{gray}
+\fan{1}{gray}
+\fan{2}{black}
+\fan{3}{gray}
+\fan{4}{gray}
+\fan{5}{gray}
+\end{scope}
+
+\dotrow{0}{gray}
+\dotrow{1}{gray}
+\dotrow{2}{black}
+\dotrow{3}{black}
+\dotrow{4}{gray}
+\dotrow{5}{gray}
+
+\def\ty{-0.5}
+\node[color=gray] at ({0.5*\xs},{\ty*\ys}) {$T(n-1,n-2)$};
+\node[color=gray] at ({1.5*\xs},{\ty*\ys}) {$T(n,n-1)$};
+\node[color=black] at ({2.5*\xs},{\ty*\ys}) {$T(n+1,n)$};
+\node[color=gray] at ({3.5*\xs},{\ty*\ys}) {$T(n+2,n+1)$};
+\node[color=gray] at ({4.5*\xs},{\ty*\ys}) {$T(n+3,n+2)$};
+
+\draw[->,color=red] (-0.7,{-6.5*\ys}) -- ({5*\xs+0.7},{-6.5*\ys}) coordinate[label={$t$}];
+
+\foreach \x in {0,...,5}{
+ \draw[color=red]
+ ({\x*\xs},{-6.5*\ys-0.05})
+ --
+ ({\x*\xs},{-6.5*\ys+0.05});
+}
+\node[color=red] at ({0*\xs},{-6.5*\ys}) [below] {$n-2\mathstrut$};
+\node[color=red] at ({1*\xs},{-6.5*\ys}) [below] {$n-1\mathstrut$};
+\node[color=red] at ({2*\xs},{-6.5*\ys}) [below] {$n\mathstrut$};
+\node[color=red] at ({3*\xs},{-6.5*\ys}) [below] {$n+1\mathstrut$};
+\node[color=red] at ({4*\xs},{-6.5*\ys}) [below] {$n+2\mathstrut$};
+\node[color=red] at ({5*\xs},{-6.5*\ys}) [below] {$n+3\mathstrut$};
+
+\end{tikzpicture}
+\end{document}
+
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/markov2.pdf b/buch/chapters/80-wahrscheinlichkeit/images/markov2.pdf
new file mode 100644
index 0000000..d534c8f
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/markov2.pdf
Binary files differ
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/markov2.tex b/buch/chapters/80-wahrscheinlichkeit/images/markov2.tex
new file mode 100644
index 0000000..c2fab2e
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/markov2.tex
@@ -0,0 +1,113 @@
+%
+% markov.tex -- Illustration markov-Kette
+%
+% (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}
+\begin{document}
+\def\skala{1}
+\begin{tikzpicture}[>=latex,thick,scale=\skala]
+
+\def\punkt#1#2#3{
+ \fill[color=white] #1 circle[radius=0.10];
+ \fill[color=#2] #1 circle[radius=0.13];
+ \node[color=white] at #1 {$\scriptstyle #3$};
+}
+
+\def\xs{2.5}
+\def\ys{1}
+
+\foreach \x in {0,...,5}{
+ \draw[color=red,line width=0.5pt]
+ ({\x*\xs},{-0.7*\ys}) -- ({\x*\xs},{-8.5*\ys});
+}
+
+\def\dotradius{0.04}
+
+\def\dotrow#1#2{
+ \punkt{({#1*\xs},{-1*\ys})}{#2}{1}
+ \punkt{({#1*\xs},{-2*\ys})}{#2}{2}
+ \fill[color=#2] ({#1*\xs},{-3*\ys-0.3}) circle[radius=\dotradius];
+ \fill[color=#2] ({#1*\xs},{-3*\ys-0.15}) circle[radius=\dotradius];
+ \fill[color=#2] ({#1*\xs},{-3*\ys}) circle[radius=\dotradius];
+ \fill[color=#2] ({#1*\xs},{-3*\ys+0.15}) circle[radius=\dotradius];
+ \fill[color=#2] ({#1*\xs},{-3*\ys+0.3}) circle[radius=\dotradius];
+ \punkt{({#1*\xs},{-4*\ys})}{#2}{7}
+ \punkt{({#1*\xs},{-5*\ys})}{#2}{8}
+ \punkt{({#1*\xs},{-6*\ys})}{#2}{9}
+ \fill[color=#2] ({#1*\xs},{-7*\ys-0.3}) circle[radius=\dotradius];
+ \fill[color=#2] ({#1*\xs},{-7*\ys-0.15}) circle[radius=\dotradius];
+ \fill[color=#2] ({#1*\xs},{-7*\ys}) circle[radius=\dotradius];
+ \fill[color=#2] ({#1*\xs},{-7*\ys+0.15}) circle[radius=\dotradius];
+ \fill[color=#2] ({#1*\xs},{-7*\ys+0.3}) circle[radius=\dotradius];
+ \punkt{({#1*\xs},{-8*\ys})}{#2}{s}
+}
+
+\def\fan#1#2{
+ \foreach \x in {1,2,4}{
+ \foreach \y in {1,2,4}{
+ \draw[->,shorten >= 2mm,shorten <= 2mm,color=#2]
+ ({#1*\xs},{-\x*\ys})
+ --
+ ({(#1+1)*\xs},{-\y*\ys});
+ }
+ }
+ \foreach \x in {5,6,8}{
+ \foreach \y in {5,6,8}{
+ \draw[->,shorten >= 2mm,shorten <= 2mm,color=#2]
+ ({#1*\xs},{-\x*\ys})
+ --
+ ({(#1+1)*\xs},{-\y*\ys});
+ }
+ }
+}
+
+\begin{scope}
+\clip (-0.5,{-8.5*\ys}) rectangle ({5*\xs+0.5},-0.5);
+\fan{-1}{gray}
+\fan{0}{gray}
+\fan{1}{gray}
+\fan{2}{black}
+\fan{3}{gray}
+\fan{4}{gray}
+\fan{5}{gray}
+\end{scope}
+
+\dotrow{0}{gray}
+\dotrow{1}{gray}
+\dotrow{2}{black}
+\dotrow{3}{black}
+\dotrow{4}{gray}
+\dotrow{5}{gray}
+
+\def\ty{-0.5}
+\node[color=gray] at ({0.5*\xs},{\ty*\ys}) {$T(n-1,n-2)$};
+\node[color=gray] at ({1.5*\xs},{\ty*\ys}) {$T(n,n-1)$};
+\node[color=black] at ({2.5*\xs},{\ty*\ys}) {$T(n+1,n)$};
+\node[color=gray] at ({3.5*\xs},{\ty*\ys}) {$T(n+2,n+1)$};
+\node[color=gray] at ({4.5*\xs},{\ty*\ys}) {$T(n+3,n+2)$};
+
+\draw[->,color=red] (-0.7,{-8.5*\ys}) -- ({5*\xs+0.7},{-8.5*\ys}) coordinate[label={$t$}];
+
+\foreach \x in {0,...,5}{
+ \draw[color=red]
+ ({\x*\xs},{-8.5*\ys-0.05})
+ --
+ ({\x*\xs},{-8.5*\ys+0.05});
+}
+\node[color=red] at ({0*\xs},{-8.5*\ys}) [below] {$n-2\mathstrut$};
+\node[color=red] at ({1*\xs},{-8.5*\ys}) [below] {$n-1\mathstrut$};
+\node[color=red] at ({2*\xs},{-8.5*\ys}) [below] {$n\mathstrut$};
+\node[color=red] at ({3*\xs},{-8.5*\ys}) [below] {$n+1\mathstrut$};
+\node[color=red] at ({4*\xs},{-8.5*\ys}) [below] {$n+2\mathstrut$};
+\node[color=red] at ({5*\xs},{-8.5*\ys}) [below] {$n+3\mathstrut$};
+
+\end{tikzpicture}
+\end{document}
+
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/markov3.pdf b/buch/chapters/80-wahrscheinlichkeit/images/markov3.pdf
new file mode 100644
index 0000000..61f4fe7
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/markov3.pdf
Binary files differ
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/markov3.tex b/buch/chapters/80-wahrscheinlichkeit/images/markov3.tex
new file mode 100644
index 0000000..0b99ef3
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/markov3.tex
@@ -0,0 +1,113 @@
+%
+% markov2.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}
+\begin{document}
+\def\skala{1}
+\begin{tikzpicture}[>=latex,thick,scale=\skala]
+
+\def\punkt#1#2#3{
+ \fill[color=white] #1 circle[radius=0.10];
+ \fill[color=#2] #1 circle[radius=0.13];
+ \node[color=white] at #1 {$\scriptstyle #3$};
+}
+
+\def\xs{2.5}
+\def\ys{1}
+
+\fill[color=blue!20]
+ (-0.5,{-3.3*\ys}) rectangle ({5*\xs+0.5},{-0.7*\ys});
+
+\foreach \x in {0,...,5}{
+ \draw[color=red,line width=0.5pt]
+ ({\x*\xs},{-0.7*\ys}) -- ({\x*\xs},{-7.5*\ys});
+}
+
+\def\dotradius{0.04}
+
+\def\dotrow#1#2{
+ \punkt{({#1*\xs},{-1*\ys})}{#2}{1}
+ \fill[color=#2] ({#1*\xs},{-2*\ys-0.3}) circle[radius=\dotradius];
+ \fill[color=#2] ({#1*\xs},{-2*\ys-0.15}) circle[radius=\dotradius];
+ \fill[color=#2] ({#1*\xs},{-2*\ys}) circle[radius=\dotradius];
+ \fill[color=#2] ({#1*\xs},{-2*\ys+0.15}) circle[radius=\dotradius];
+ \fill[color=#2] ({#1*\xs},{-2*\ys+0.3}) circle[radius=\dotradius];
+ \punkt{({#1*\xs},{-3*\ys})}{#2}{7}
+ \punkt{({#1*\xs},{-4*\ys})}{#2}{8}
+ \punkt{({#1*\xs},{-5*\ys})}{#2}{9}
+ \fill[color=#2] ({#1*\xs},{-6*\ys-0.3}) circle[radius=\dotradius];
+ \fill[color=#2] ({#1*\xs},{-6*\ys-0.15}) circle[radius=\dotradius];
+ \fill[color=#2] ({#1*\xs},{-6*\ys}) circle[radius=\dotradius];
+ \fill[color=#2] ({#1*\xs},{-6*\ys+0.15}) circle[radius=\dotradius];
+ \fill[color=#2] ({#1*\xs},{-6*\ys+0.3}) circle[radius=\dotradius];
+ \punkt{({#1*\xs},{-7*\ys})}{#2}{s}
+}
+
+\def\fan#1#2{
+ \foreach \x in {1,3}{
+ \draw[->,shorten >= 2mm,shorten <= 2mm,color=#2,line width=2pt]
+ ({#1*\xs},{-\x*\ys})
+ --
+ ({(#1+1)*\xs},{-\x*\ys});
+ }
+ \foreach \x in {4,5,7}{
+ \foreach \y in {1,3,4,5,7}{
+ \draw[->,shorten >= 2mm,shorten <= 2mm,color=#2]
+ ({#1*\xs},{-\x*\ys})
+ --
+ ({(#1+1)*\xs},{-\y*\ys});
+ }
+ }
+}
+
+\begin{scope}
+\clip (-0.5,{-7.5*\ys}) rectangle ({5*\xs+0.5},-0.5);
+\fan{-1}{gray}
+\fan{0}{gray}
+\fan{1}{gray}
+\fan{2}{black}
+\fan{3}{gray}
+\fan{4}{gray}
+\fan{5}{gray}
+\end{scope}
+
+\dotrow{0}{gray}
+\dotrow{1}{gray}
+\dotrow{2}{black}
+\dotrow{3}{black}
+\dotrow{4}{gray}
+\dotrow{5}{gray}
+
+\def\ty{-0.5}
+\node[color=gray] at ({0.5*\xs},{\ty*\ys}) {$T(n-1,n-2)$};
+\node[color=gray] at ({1.5*\xs},{\ty*\ys}) {$T(n,n-1)$};
+\node[color=black] at ({2.5*\xs},{\ty*\ys}) {$T(n+1,n)$};
+\node[color=gray] at ({3.5*\xs},{\ty*\ys}) {$T(n+2,n+1)$};
+\node[color=gray] at ({4.5*\xs},{\ty*\ys}) {$T(n+3,n+2)$};
+
+\draw[->,color=red] (-0.7,{-7.5*\ys}) -- ({5*\xs+0.7},{-7.5*\ys}) coordinate[label={$t$}];
+
+\foreach \x in {0,...,5}{
+ \draw[color=red]
+ ({\x*\xs},{-7.5*\ys-0.05})
+ --
+ ({\x*\xs},{-7.5*\ys+0.05});
+}
+\node[color=red] at ({0*\xs},{-7.5*\ys}) [below] {$n-2\mathstrut$};
+\node[color=red] at ({1*\xs},{-7.5*\ys}) [below] {$n-1\mathstrut$};
+\node[color=red] at ({2*\xs},{-7.5*\ys}) [below] {$n\mathstrut$};
+\node[color=red] at ({3*\xs},{-7.5*\ys}) [below] {$n+1\mathstrut$};
+\node[color=red] at ({4*\xs},{-7.5*\ys}) [below] {$n+2\mathstrut$};
+\node[color=red] at ({5*\xs},{-7.5*\ys}) [below] {$n+3\mathstrut$};
+
+\end{tikzpicture}
+\end{document}
+
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/positiv.jpg b/buch/chapters/80-wahrscheinlichkeit/images/positiv.jpg
new file mode 100644
index 0000000..53544cb
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/positiv.jpg
Binary files differ
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/positiv.m b/buch/chapters/80-wahrscheinlichkeit/images/positiv.m
new file mode 100644
index 0000000..4dca950
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/positiv.m
@@ -0,0 +1,36 @@
+#
+# positiv.m
+#
+# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+#
+N = 10;
+p = 0.2;
+
+A = eye(3) + p * rand(3,3);
+A = [
+ 1, 0.2, 0.2;
+ 0.1, 1, 0.1;
+ 0.05, 0.05, 1
+];
+B = eye(3);
+
+function retval = punkt(x)
+ retval = sprintf("<%.4f,%.4f,%.4f>", x(1), x(3), x(2));
+end
+
+fn = fopen("quadrant.inc", "w");
+for i = (1:N)
+ fprintf(fn, "quadrant(%s,%s,%s)\n",
+ punkt(B(:,1)), punkt(B(:,2)), punkt(B(:,3)))
+ B = B * A;
+end
+
+x = [ 1; 1; 1 ];
+for i = (1:100)
+ x = A * x;
+ x = x / norm(x);
+end
+fprintf(fn, "eigenvektor(<%.4f, %.4f, %.4f>)\n", x(1), x(3), x(2));
+
+
+fclose(fn);
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/positiv.pdf b/buch/chapters/80-wahrscheinlichkeit/images/positiv.pdf
new file mode 100644
index 0000000..39aa3cd
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/positiv.pdf
Binary files differ
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/positiv.png b/buch/chapters/80-wahrscheinlichkeit/images/positiv.png
new file mode 100644
index 0000000..a2bd9bf
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/positiv.png
Binary files differ
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/positiv.pov b/buch/chapters/80-wahrscheinlichkeit/images/positiv.pov
new file mode 100644
index 0000000..9197498
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/positiv.pov
@@ -0,0 +1,137 @@
+//
+// diffusion.pov
+//
+// (c) 2021 Prof Dr Andreas Müller, OST Ostscheizer Fachhochschule
+//
+#version 3.7;
+#include "colors.inc"
+
+global_settings {
+ assumed_gamma 1
+}
+
+#declare imagescale = 0.077;
+#declare N = 30;
+#declare vscale = 10;
+#declare r = 0.04;
+
+camera {
+ location <43, 20, -20>
+ look_at <1, 0.83, 2.5>
+ right 16/9 * x * imagescale
+ up y * imagescale
+}
+
+light_source {
+ <40, 20, -10> color White
+ area_light <1,0,0> <0,0,1>, 10, 10
+ adaptive 1
+ jitter
+}
+
+sky_sphere {
+ pigment {
+ color rgb<1,1,1>
+ }
+}
+
+//
+// draw an arrow from <from> to <to> with thickness <arrowthickness> with
+// color <c>
+//
+#macro arrow(from, to, arrowthickness, c)
+#declare arrowdirection = vnormalize(to - from);
+#declare arrowlength = vlength(to - from);
+union {
+ sphere {
+ from, 1.1 * arrowthickness
+ }
+ cylinder {
+ from,
+ from + (arrowlength - 5 * arrowthickness) * arrowdirection,
+ arrowthickness
+ }
+ cone {
+ from + (arrowlength - 5 * arrowthickness) * arrowdirection,
+ 2 * arrowthickness,
+ to,
+ 0
+ }
+ pigment {
+ color c
+ }
+ finish {
+ specular 0.9
+ metallic
+ }
+}
+#end
+
+arrow(<0,0,0>, <3,0,0>, r, White)
+arrow(<0,0,0>, <0,3,0>, r, White)
+arrow(<0,0,0>, <0,0,3>, r, White)
+
+#macro quadrant(A, B, C)
+intersection {
+ sphere { <0, 0, 0>, 1
+ matrix <A.x, A.y, A.z,
+ B.x, B.y, B.z,
+ C.x, C.y, C.z,
+ 0, 0, 0 >
+ }
+ plane { vnormalize(vcross(A, B)), 0 }
+ plane { vnormalize(vcross(B, C)), 0 }
+ plane { vnormalize(vcross(C, A)), 0 }
+ pigment {
+ //color rgbf<0.8,1,1,0.7>
+ color rgb<0.8,1,1>
+ }
+ finish {
+ specular 0.9
+ metallic
+ }
+}
+#end
+
+#macro eigenvektor(E)
+union {
+ cylinder { -E, 8 * E, r }
+ #declare r0 = 0.7 * r;
+
+ sphere { 3 * < 0, E.y, E.z >, r0 }
+ sphere { 3 * < E.x, 0, E.z >, r0 }
+ sphere { 3 * < E.x, E.y, 0 >, r0 }
+ sphere { 3 * E, r0 }
+
+ cylinder { 3*< E.x, 0, 0 >, 3*< E.x, 0, E.z >, r0 }
+ cylinder { 3*< E.x, 0, 0 >, 3*< E.x, E.y, 0 >, r0 }
+ cylinder { 3*< 0, E.y, 0 >, 3*< E.x, E.y, 0 >, r0 }
+ cylinder { 3*< 0, E.y, 0 >, 3*< 0, E.y, E.z >, r0 }
+ cylinder { 3*< 0, 0, E.z >, 3*< 0, E.y, E.z >, r0 }
+ cylinder { 3*< 0, 0, E.z >, 3*< E.x, 0, E.z >, r0 }
+
+ cylinder { 3*< E.x, E.y, 0 >, 3*E, r0 }
+ cylinder { 3*< 0, E.y, E.z >, 3*E, r0 }
+ cylinder { 3*< E.x, 0, E.z >, 3*E, r0 }
+ pigment {
+ color rgb<1,0.6,1>*0.6
+ }
+ finish {
+ specular 0.9
+ metallic
+ }
+}
+#end
+
+#include "quadrant.inc"
+
+//union {
+// pigment {
+// color rgb<0.8,1,1>*0.6
+// }
+// finish {
+// specular 0.9
+// metallic
+// }
+//}
+
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/positiv.tex b/buch/chapters/80-wahrscheinlichkeit/images/positiv.tex
new file mode 100644
index 0000000..911b599
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/positiv.tex
@@ -0,0 +1,51 @@
+%
+% positiv.tex
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\documentclass[tikz]{standalone}
+\usepackage{times}
+\usepackage{amsmath}
+\usepackage{txfonts}
+\usepackage[utf8]{inputenc}
+\usepackage{graphics}
+\usetikzlibrary{arrows,intersections,math}
+\usepackage{ifthen}
+\begin{document}
+
+\newboolean{showgrid}
+\setboolean{showgrid}{false}
+\def\breite{7}
+\def\hoehe{4}
+
+\begin{tikzpicture}[>=latex,thick]
+
+% Povray Bild
+\node at (0,0) {\includegraphics[width=14cm]{positiv.jpg}};
+
+% Gitter
+\ifthenelse{\boolean{showgrid}}{
+\draw[step=0.1,line width=0.1pt] (-\breite,-\hoehe) grid (\breite, \hoehe);
+\draw[step=0.5,line width=0.4pt] (-\breite,-\hoehe) grid (\breite, \hoehe);
+\draw (-\breite,-\hoehe) grid (\breite, \hoehe);
+\fill (0,0) circle[radius=0.05];
+}{}
+
+\node at (-2.6,-3.8) [right] {$x_1$};
+\node at (-5.4,3.8) [right] {$x_3$};
+
+\node[color=red] at (-4.5,-1.3) {$0$};
+\node[color=red] at (-4.15,-1.25) {$1$};
+\node[color=red] at (-3.75,-0.90) {$2$};
+\node[color=red] at (-3.22,-0.80) {$3$};
+\node[color=red] at (-2.6,-0.70) {$4$};
+\node[color=red] at (-1.8,-0.60) {$5$};
+\node[color=red] at (-0.9,-0.50) {$6$};
+\node[color=red] at (0.2,-0.40) {$7$};
+\node[color=red] at (1.6,-0.20) {$8$};
+\node[color=red] at (4.0,0.10) {$9$};
+
+\end{tikzpicture}
+
+\end{document}
+
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/spielB.pdf b/buch/chapters/80-wahrscheinlichkeit/images/spielB.pdf
new file mode 100644
index 0000000..466974d
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/spielB.pdf
Binary files differ
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/spielB.tex b/buch/chapters/80-wahrscheinlichkeit/images/spielB.tex
new file mode 100644
index 0000000..92989ed
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/spielB.tex
@@ -0,0 +1,59 @@
+%
+% spielB.tex -- Zutandsdiagramm für Spiel B
+%
+% (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}
+\begin{document}
+\def\skala{1}
+\begin{tikzpicture}[>=latex,thick,scale=\skala]
+
+\def\R{2}
+\def\r{0.5}
+\coordinate (A) at (0,\R);
+\coordinate (B) at ({\R*sqrt(3)/2},{-0.5*\R});
+\coordinate (C) at ({-\R*sqrt(3)/2},{-0.5*\R});
+
+\draw[->,shorten >= 0.5cm,shorten <= 0.5cm] (A) -- (B);
+\draw[->,shorten >= 0.5cm,shorten <= 0.5cm] (A) -- (C);
+\draw[->,shorten >= 0.5cm,shorten <= 0.5cm] (C) -- (B);
+
+\draw[->,shorten >= 0.5cm,shorten <= 0.5cm] (B) to[out=90,in=-30] (A);
+\draw[->,shorten >= 0.5cm,shorten <= 0.5cm] (C) to[out=90,in=-150] (A);
+\draw[->,shorten >= 0.5cm,shorten <= 0.5cm] (B) to[out=-150,in=-30] (C);
+
+\pgfmathparse{0.93*\R}
+\xdef\Rgross{\pgfmathresult}
+
+\node at (30:\Rgross) {$\frac34$};
+\node at (150:\Rgross) {$\frac14$};
+\node at (-90:\Rgross) {$\frac14$};
+
+\pgfmathparse{0.33*\R}
+\xdef\Rklein{\pgfmathresult}
+
+\node at (-90:\Rklein) {$\frac34$};
+\node at (30:\Rklein) {$\frac9{10}$};
+\node at (150:\Rklein) {$\frac1{10}$};
+
+\fill[color=white] (A) circle[radius=\r];
+\draw (A) circle[radius=\r];
+\node at (A) {$0$};
+
+\fill[color=white] (B) circle[radius=\r];
+\draw (B) circle[radius=\r];
+\node at (B) {$2$};
+
+\fill[color=white] (C) circle[radius=\r];
+\draw (C) circle[radius=\r];
+\node at (C) {$1$};
+
+\end{tikzpicture}
+\end{document}
+
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/spielBtilde.pdf b/buch/chapters/80-wahrscheinlichkeit/images/spielBtilde.pdf
new file mode 100644
index 0000000..7812c9c
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/spielBtilde.pdf
Binary files differ
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/spielBtilde.tex b/buch/chapters/80-wahrscheinlichkeit/images/spielBtilde.tex
new file mode 100644
index 0000000..b2d4b01
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/spielBtilde.tex
@@ -0,0 +1,59 @@
+%
+% spielBtilde.tex -- Zustandsdiagramm des modifzierten Spiels
+%
+% (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}
+\begin{document}
+\def\skala{1}
+\begin{tikzpicture}[>=latex,thick,scale=\skala]
+
+\def\R{2.5}
+\def\r{0.5}
+\coordinate (A) at (0,\R);
+\coordinate (B) at ({\R*sqrt(3)/2},{-0.5*\R});
+\coordinate (C) at ({-\R*sqrt(3)/2},{-0.5*\R});
+
+\draw[->,shorten >= 0.5cm,shorten <= 0.5cm] (A) -- (B);
+\draw[->,shorten >= 0.5cm,shorten <= 0.5cm] (A) -- (C);
+\draw[->,shorten >= 0.5cm,shorten <= 0.5cm] (C) -- (B);
+
+\draw[->,shorten >= 0.5cm,shorten <= 0.5cm] (B) to[out=90,in=-30] (A);
+\draw[->,shorten >= 0.5cm,shorten <= 0.5cm] (C) to[out=90,in=-150] (A);
+\draw[->,shorten >= 0.5cm,shorten <= 0.5cm] (B) to[out=-150,in=-30] (C);
+
+\pgfmathparse{0.93*\R}
+\xdef\Rgross{\pgfmathresult}
+
+\node at (30:\Rgross) {$\frac34-\varepsilon$};
+\node at (150:\Rgross) {$\frac14+\varepsilon$};
+\node at (-90:\Rgross) {$\frac14+\varepsilon$};
+
+\pgfmathparse{0.32*\R}
+\xdef\Rklein{\pgfmathresult}
+
+\node at (-90:\Rklein) {$\frac34-\varepsilon$};
+\node at (30:\Rklein) {$\frac9{10}+\varepsilon$};
+\node at (150:\Rklein) {$\frac1{10}-\varepsilon$};
+
+\fill[color=white] (A) circle[radius=\r];
+\draw (A) circle[radius=\r];
+\node at (A) {$0$};
+
+\fill[color=white] (B) circle[radius=\r];
+\draw (B) circle[radius=\r];
+\node at (B) {$2$};
+
+\fill[color=white] (C) circle[radius=\r];
+\draw (C) circle[radius=\r];
+\node at (C) {$1$};
+
+\end{tikzpicture}
+\end{document}
+
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/trenn.pdf b/buch/chapters/80-wahrscheinlichkeit/images/trenn.pdf
new file mode 100644
index 0000000..f4fa58f
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/trenn.pdf
Binary files differ
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/trenn.tex b/buch/chapters/80-wahrscheinlichkeit/images/trenn.tex
new file mode 100644
index 0000000..f34879c
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/trenn.tex
@@ -0,0 +1,44 @@
+%
+% trenn.tex -- Trenntrick graphische Darstellung
+%
+% (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}
+\begin{document}
+\def\skala{1}
+\begin{tikzpicture}[>=latex,thick,scale=\skala]
+
+\def\d{6}
+
+\coordinate (u) at (5,3);
+\coordinate (v) at (3,1);
+\coordinate (ve) at (5,1.666);
+
+\fill[color=gray!40] (0,0) rectangle (u);
+
+\begin{scope}
+\clip (0,0) rectangle (6.1,4.1);
+\draw[color=red] (0,0) -- (9,3);
+\end{scope}
+
+\draw[->] (-0.1,0) -- (6.3,0) coordinate[label={$x_1$}];
+\draw[->] (0,-0.1) -- (0,4.3) coordinate[label={right:$x_2$}];
+
+\fill (u) circle[radius=0.05];
+\node at (u) [above right] {$u$};
+
+\fill (v) circle[radius=0.05];
+\node at (v) [above right] {$v$};
+
+\fill[color=red] (ve) circle[radius=0.05];
+\node[color=red] at (ve) [above,rotate={atan(1/3)}] {$(1+\varepsilon)v$};
+
+\end{tikzpicture}
+\end{document}
+
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/vergleich.jpg b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.jpg
new file mode 100644
index 0000000..3274f42
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.jpg
Binary files differ
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf
new file mode 100644
index 0000000..b7215b4
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf
Binary files differ
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/vergleich.png b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.png
new file mode 100644
index 0000000..f20bd48
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.png
Binary files differ
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pov b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pov
new file mode 100644
index 0000000..e696481
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pov
@@ -0,0 +1,203 @@
+//
+// diffusion.pov
+//
+// (c) 2021 Prof Dr Andreas Müller, OST Ostscheizer Fachhochschule
+//
+#version 3.7;
+#include "colors.inc"
+#include "textures.inc"
+#include "transforms.inc"
+
+global_settings {
+ assumed_gamma 1
+}
+
+#declare imagescale = 0.077;
+#declare N = 30;
+#declare vscale = 10;
+#declare r = 0.04;
+
+camera {
+ location <43, 20, -20>
+ look_at <1, 0.83, 2.5>
+ right 16/9 * x * imagescale
+ up y * imagescale
+}
+
+light_source {
+ <20, 60, -80> color White
+ area_light <1,0,0> <0,0,1>, 40, 40
+ adaptive 1
+ jitter
+}
+
+sky_sphere {
+ pigment {
+ color rgb<1,1,1>
+ }
+}
+
+//
+// draw an arrow from <from> to <to> with thickness <arrowthickness> with
+// color <c>
+//
+#macro arrow(from, to, arrowthickness, c)
+#declare arrowdirection = vnormalize(to - from);
+#declare arrowlength = vlength(to - from);
+union {
+ sphere {
+ from, 1.1 * arrowthickness
+ }
+ cylinder {
+ from,
+ from + (arrowlength - 5 * arrowthickness) * arrowdirection,
+ arrowthickness
+ }
+ cone {
+ from + (arrowlength - 5 * arrowthickness) * arrowdirection,
+ 2 * arrowthickness,
+ to,
+ 0
+ }
+ pigment {
+ color c
+ }
+ finish {
+ specular 0.9
+ metallic
+ }
+}
+#end
+
+#declare O = <0,0,0>;
+#declare Ex = <1,0,0>;
+#declare Ey = <0,1,0>;
+#declare Ez = <0,0,1>;
+#declare s = 3;
+
+#declare A_transformation = Matrix_Trans(<1.0300,0.2050,0.1050>,<0.4100,1.0250,0.1100>,<0.4200,0.2200,1.0150>,<0,0,0>);
+//#declare A_transformation = Matrix_Trans(<1.0300,0.2050,0.1050>,<0.4100,1.0250,0.1100>,<0.4200,0.2200,0.5150>,<0,0,0>);
+
+arrow(O, s * Ex, r, rgb<0.6,0.2,0.4>)
+arrow(O, s * Ez, r, rgb<0.2,0.4,0.2>)
+arrow(O, s * Ey, r, rgb<0.2,0.2,0.4>)
+
+#declare A = vtransform(Ex, A_transformation);
+#declare B = vtransform(Ey, A_transformation);
+#declare C = vtransform(Ez, A_transformation);
+
+#macro quadrant(rad)
+intersection {
+ sphere { <0, 0, 0>, rad
+ //A_transformation
+ matrix <A.x, A.y, A.z,
+ B.x, B.y, B.z,
+ C.x, C.y, C.z,
+ 0, 0, 0 >
+ }
+ plane { vnormalize(-vcross(A, B)), 0 }
+ plane { vnormalize(-vcross(B, C)), 0 }
+ plane { vnormalize(-vcross(C, A)), 0 }
+ pigment {
+ color rgbf<0.8,1,1,0.5>
+ //color rgb<0.8,1,1>
+ }
+ finish {
+ specular 0.9
+ metallic
+ }
+}
+union {
+ cylinder { O, s*A, 0.3*r }
+ sphere { s*A, 0.3*r }
+ cylinder { O, s*B, 0.3*r }
+ sphere { s*B, 0.3*r }
+ cylinder { O, s*C, 0.3*r }
+ sphere { s*C, 0.3*r }
+ pigment {
+ color White
+ }
+ finish {
+ specular 0.9
+ metallic
+ }
+}
+#end
+
+#declare d = 3;
+//union {
+// plane { <0, 1, 0>, -d }
+// plane { <1, 0, 0>, -d }
+// pigment {
+// color Gray
+// }
+// finish {
+// specular 0.9
+// }
+//}
+
+quadrant(s)
+
+#declare V = < 1, 1, 0 >;
+#declare U = < 1.3, 2.5, 0 >;
+
+#declare VV = vtransform(V, A_transformation);
+#declare Vx = vtransform(<V.x, 0, 0>, A_transformation);
+#declare Vy = vtransform(<0, V.y, 0>, A_transformation);
+#declare UU = vtransform(U, A_transformation);
+#declare Ux = vtransform(<U.x, 0, 0>, A_transformation);
+#declare Uy = vtransform(<0, U.y, 0>, A_transformation);
+
+union {
+ sphere { V, r }
+ sphere { U, r }
+ cylinder { U, V, 0.5*r }
+ pigment {
+ color Red
+ }
+ finish {
+ specular 0.9
+ metallic
+ }
+}
+
+union {
+ cylinder { < U.x, 0, 0 >, < U.x, U.y, 0>, 0.3 * r }
+ cylinder { < V.x, 0, 0 >, < V.x, V.y, 0>, 0.3 * r }
+ cylinder { < 0, U.y, 0 >, < U.x, U.y, 0>, 0.3 * r }
+ cylinder { < 0, V.y, 0 >, < V.x, V.y, 0>, 0.3 * r }
+ pigment {
+ color rgb<1, 0.6, 1>
+ }
+ finish {
+ specular 0.9
+ metallic
+ }
+}
+
+union {
+ sphere { VV, r }
+ sphere { UU, r }
+ cylinder { UU, VV, 0.5*r }
+ pigment {
+ color Yellow
+ }
+ finish {
+ specular 0.9
+ metallic
+ }
+}
+
+union {
+ cylinder { Ux, UU, 0.3 * r }
+ cylinder { Uy, UU, 0.3 * r }
+ cylinder { Vx, VV, 0.3 * r }
+ cylinder { Vy, VV, 0.3 * r }
+ pigment {
+ color rgb<1, 1, 0.6>
+ }
+ finish {
+ specular 0.9
+ metallic
+ }
+}
diff --git a/buch/chapters/80-wahrscheinlichkeit/images/vergleich.tex b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.tex
new file mode 100644
index 0000000..23d7d66
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.tex
@@ -0,0 +1,46 @@
+%
+% vergleich.tex
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\documentclass[tikz]{standalone}
+\usepackage{times}
+\usepackage{amsmath}
+\usepackage{txfonts}
+\usepackage[utf8]{inputenc}
+\usepackage{graphics}
+\usetikzlibrary{arrows,intersections,math}
+\usepackage{ifthen}
+\begin{document}
+
+\newboolean{showgrid}
+\setboolean{showgrid}{false}
+\def\breite{5}
+\def\hoehe{5}
+
+\begin{tikzpicture}[>=latex,thick]
+
+% Povray Bild
+\node at (0,0) {\includegraphics[width=10cm]{vergleich.jpg}};
+
+\node at (-1.3,-4.8) [right] {$x_1$};
+\node[opacity=0.5] at (1.9,-0.9) [right] {$x_2$};
+\node at (-4.6,4.7) [right] {$x_3$};
+
+\node at (-3.2,2.6) [above] {$u$};
+\node at (-3.5,-0.7) [below left] {$v$};
+\node at (-1,2.8) [above] {$Au$};
+\node at (-2.6,-0.5) [below] {$Av$};
+
+% Gitter
+\ifthenelse{\boolean{showgrid}}{
+\draw[step=0.1,line width=0.1pt] (-\breite,-\hoehe) grid (\breite, \hoehe);
+\draw[step=0.5,line width=0.4pt] (-\breite,-\hoehe) grid (\breite, \hoehe);
+\draw (-\breite,-\hoehe) grid (\breite, \hoehe);
+\fill (0,0) circle[radius=0.05];
+}{}
+
+\end{tikzpicture}
+
+\end{document}
+
diff --git a/buch/chapters/80-wahrscheinlichkeit/markov.tex b/buch/chapters/80-wahrscheinlichkeit/markov.tex
index 5fb156a..0485714 100644
--- a/buch/chapters/80-wahrscheinlichkeit/markov.tex
+++ b/buch/chapters/80-wahrscheinlichkeit/markov.tex
@@ -6,5 +6,919 @@
\section{Diskrete Markov-Ketten und Wahrscheinlichkeitsmatrizen
\label{buch:section:diskrete-markov-ketten}}
\rhead{Diskrete Markov-Ketten}
+Die einführend im Abschnitt~\ref{buch:section:google-matrix}
+vorgestellte Google-Matrix ist nur ein Beispiel für ein
+Modell eines stochastischen Prozesses, der mit Hilfe von Matrizen
+modelliert werden kann.
+In diesem Abschnitt soll diese Art von Prozessen etwas formalisiert
+werden.
+
+%
+% Beschreibung der Markov-Eigenschaft
+%
+\subsection{Markov-Eigenschaft}
+% XXX Notation, Zustände, Übergangswahrscheinlichkeit
+Ein stochastischer Prozess ist eine Familie von Zustandsvariablen
+$X_t$ mit Werten in einer Menge $\mathcal{S}$ von Zuständen.
+Der Parameter $t$ wird üblicherweise als die Zeit interpretiert,
+er kann beliebige reelle Werte oder diskrete Werte annahmen, im letzten
+Fall spricht man von einem Prozess mit diskreter Zeit.
+
+Das Ereignis $\{X_t=x\}$ wird gelesen als ``zur Zeit $t$ befindet sich
+der Prozess im Zustand $x$''.
+Mit $P(X_t = x)$ wir die Wahrscheinlichkeit bezeichnet, dass sich
+der Prozess zur Zeit $t$ im Zustand $x$ befindet.
+Die Funktion $t\mapsto X_t$ beschreiben also den zeitlichen Ablauf
+der vom Prozess durchlaufenen Zustände.
+Dies ermöglicht, Fragen nach dem Einfluss früherer Zustände,
+also des Eintretens eines Ereignisses $\{X_{t_0}=x\}$ auf das Eintreten eines
+Zustands $s\in\mathcal{S}$ zu einem späteren Zeitpunkt $t_1>t_0$
+zu studieren.
+Das Ereignis $\{X_t = x\}$ kann man sich als abhängig von der Vorgeschichte
+vorstellen.
+Die Vorgeschichte besteht dabei aus dem Eintreten gewisser Ereignisse
+\[
+\{X_0=x_0\},
+\{X_1=x_1\},
+\{X_2=x_2\},
+\dots,
+\{X_n=x_n\}
+\]
+zu früheren Zeiten $t_0<t_1<\dots<t_n<t$.
+Die bedingte Wahrscheinlichkeit
+\begin{equation}
+P(X_t = x|
+X_{t_n}=x_n\wedge X_{t_{n-1}}=x_{n-1}\wedge\dots\wedge X_{t_1}=x_1\wedge
+X_{t_0}=x_0)
+\label{buch:wahrscheinlichkeit:eqn:historybedingt}
+\end{equation}
+ist die Wahrscheinlichkeit dafür, dass der Prozess zur Zeit $t$ den
+Zustand $x$ erreicht, wenn er zu den Zeitpunkten $t_0,t_1,\dots,t_n$
+die Zustände $x_0,x_1,\dots,x_n$ durchlaufen hat.
+
+\subsubsection{Gedächtnislosigkeit}
+% XXX Gedächtnislösigkeit, Markov-Eigenschaft
+In vielen Fällen ist nur der letzte durchlaufene Zustand wichtig.
+Die Zustände in den Zeitpunkten $t_0<\dots<t_{n-1}$ haben dann keinen
+Einfluss auf die Wahrscheinlichkeit.
+Auf die bedingte
+Wahrscheinlichkeit~\eqref{buch:wahrscheinlichkeit:eqn:historybedingt}
+sollten also die Ereignisse $\{X_{t_0}=x_0\}$ bis $\{X_{t_{n-1}}=x_{n-1}\}$
+keinen Einfluss haben.
+
+\begin{definition}
+Ein stochastischer Prozess erfüllt die Markov-Eigenschaft, wenn
+für jede Folge von früheren Zeitpunkten $t_0<t_1<\dots <t_n<t$ und Zuständen
+$x_0,\dots,x_n,x\in \mathcal{S}$ die
+Wahrscheinlichkeit~\eqref{buch:wahrscheinlichkeit:eqn:historybedingt}
+nicht von der Vorgeschichte abhängt, also
+\[
+P(X_t = x|
+X_{t_n}=x_n\wedge X_{t_{n-1}}=x_{n-1}\wedge\dots\wedge X_{t_1}=x_1\wedge
+X_{t_0}=x_0)
+=
+P(X_t = x|
+X_{t_n}=x_n).
+\]
+\index{Markov-Eigenschaft}
+\end{definition}
+
+Die Wahrscheinlichkeiten $P(X_t=x|X_s=y)$ mit $t>s$ bestimmen das
+zeitliche Verhalten der Wahrscheinlichkeiten vollständig.
+Wir schreiben daher auch
+\[
+p_{xy}(t, s)
+=
+P(X_t = x|X_s=y)
+\]
+für die sogenannte {\em transiente Übergangswahrscheinlichkeit}.
+Für eine endliche Menge von Zuständen, können die transienten
+Übergangswahrscheinlichkeiten auch als zeitabhängige
+quadratische Matrix $P(s,t)$ geschrieben werden, deren
+Einträge
+\[
+(P(s,t))_{xy}
+=
+p_{xy}(t,s)
+\]
+mit den Zuständen $x,y\in\mathcal{S}$ indiziert sind.
+
+\subsubsection{Die Chapman-Kolmogorov-Gleichung}
+% XXX Chapman-Kolmogorov-Gleichung
+Man beachte, dass in der Definition der Markov-Eigenschaft
+keine Voraussetzungen darüber gemacht werden, wie nahe
+am Zeitpunkt $t$ der letzte Zeitpunkt $t_n$ der Vorgeschichte liegt.
+Die transienten Übergangswahrscheinlichkeiten $p_{xy}(s,t)$ werden
+aber im allgemeinen davon abhängen, wie weit in der Vergangenheit
+der Zeitpunkt $s<t$ liegt.
+Für eine näheren Zeitpunkt $\tau$ mit $s<\tau <t$ muss es daher
+einen Zusammenhang zwischen den transienten Übergangswahrscheinlichkeiten
+$p_{xy}(s,\tau)$, $p_{xy}(\tau,t)$ und $p_{xy}(s,t)$ geben.
+
+\begin{satz}[Chapman-Kolmogorov]
+Hat der Prozess die Markov-Eigenschaft und ist $s<\tau <t$, dann gilt
+\[
+p_{xy}(t,s) = \sum_{z\in\mathcal{S}} p_{xz}(t,\tau) p_{zy}(\tau,s),
+\]
+was in Matrixform auch als
+\[
+P(t,s) = P(t,\tau)P(\tau,s)
+\]
+geschrieben werden kann.
+\end{satz}
+
+Auch hier spielt es keine Rolle, wie nahe an $t$ der Zwischenzeitpunkt
+$\tau$ liegt.
+Die Formel von Chapman-Kolmogoroff kann natürlich für zusätzliche
+Zwischenpunkte $s<t_1<t_2<\dots< t_n< t$ formuliert werden.
+In Matrix-Notation gilt
+\[
+P(t,s) = P(t,t_n)P(t_n,t_{n-1})\dots P(t_2,t_1)P(t_1,s),
+\]
+was ausgeschrieben zu
+\[
+p_{xy}(t,s)
+=
+\sum_{x_1,\dots,x_n\in\mathcal{S}}
+p_{xx_n}(t,t_n)
+p_{x_nx_{n-1}}(t_n,t_{n-1})
+\dots
+p_{x_2x_1}(t_2,t_1)
+p_{x_1y}(t_1,s)
+\]
+wird.
+Jeder Summand auf der rechten Seite beschreibt einen Weg des Prozesses
+derart, dass er zu den Zwischenzeitpunkten bestimmte
+Zwischenzustände durchläuft.
+
+% XXX Pfadwahrscheinlichkeit
+\begin{definition}
+Die Wahrscheinlichkeit, dass der stochastische Prozess zwischen Zeitpunkten
+$t_0$ und $t_n$ die Zwischenzustände $x_i$ zu Zeiten $t_i$ durchläuft ist
+das Produkt
+\[
+\sum_{x_1,\dots,x_n\in\mathcal{S}}
+p_{x_{n+1}x_n}(t_{n+1},t_n)
+p_{x_nx_{n-1}}(t_n,t_{n-1})
+\dots
+p_{x_2x_1}(t_2,t_1)
+p_{x_1x_0}(t_1,s)
+=
+\prod_{i=0}^{n}
+p_{x_{i+1}x_i}(t_{i+1}t_i)
+\]
+heisst die {\em Pfadwahrscheinlichkeit} für genannten Pfad.
+\index{Pfadwahrscheinlichkeit}%
+\end{definition}
+
+%
+% Diskrete Markov-Kette
+%
+\subsection{Diskrete Markov-Kette}
+% XXX Diskrete Zeit, Endliche Zustandsmenge
+Die Markov-Eigenschaft besagt, dass man keine Information verliert,
+wenn man die Vorgeschichte eines Zeitpunktes ignoriert.
+Insbesondere kann man eine Menge von geeigneten diskreten
+Zeitpunkten wählen, ohne viel Information über den Prozess zu
+verlieren.
+Eine {\em diskrete Markov-Kette} ist eine stochastischer Prozess,
+für den die Menge der Zeitpunkte $t$ diskret ist.
+Es ist üblich, für die Zeitpunkte ganze oder natürliche Zahlen zu
+verwenden.
+
+\begin{definition}
+Eine diskrete Markov-Kette ist ein stochastischer Prozess
+$(X_t)_{t\in\mathbb{N}}$ mit Werten in $\mathcal{S}$, der die
+Markov-Eigenschaft
+\[
+P(X_{n+1}=x_{n+1}|X_n=x_n\wedge\dots X_0=x_0)
+=
+P(X_{n+1}=x_{n+1}|X_n=x_n)
+\]
+hat.
+\end{definition}
+
+\begin{figure}
+\centering
+\includegraphics{chapters/80-wahrscheinlichkeit/images/markov.pdf}
+\caption{Diskrete Markovkette mit Zuständen $\mathcal{S}=\{1,2,3,\dots,s\}$
+und Übergangsmatrizen $T(n+1,n)$.
+\label{buch:wahrscheinlichkeit:fig:diskretemarkovkette}}
+\end{figure}
+
+Die transienten Übergangswahrscheinlichkeiten zwischen aufeinanderfolgenden
+Zeitpunkten stellen jetzt die vollständige Information über die
+zeitliche Entwicklung dar
+(Abbildung~\ref{buch:wahrscheinlichkeit:fig:diskretemarkovkette}).
+Aus der Matrix
+\[
+T(n+1,n)
+=
+\begin{pmatrix}
+p_{11}(n+1,n) & \dots & p_{1s}(n+1,n)\\
+\vdots & \ddots & \vdots \\
+p_{11}(n+1,n) & \dots & p_{1s}(n+1,n)
+\end{pmatrix},
+\]
+auch die $1$-Schritt Übergangswahrscheinlichkeit genannt, kann man jetzt
+auch die Matrix der Überganswahrscheinlichkeiten für mehrere Schritte
+\[
+T(n+m,n)
+=
+T(n+m,n+m-1)
+T(n+m-1,n+m-2)
+\dots
+T(n+1,n)
+\]
+mit der Chapman-Komogorov-Formel bestimmen.
+Die Markov-Eigenschaft stellt also sicher, dass man nur die
+$1$-Schritt-Übergangswahrscheinlichkeiten kennen muss.
+
+Eine Matrix $T$ kann als Matrix der Übergangswahrscheinlichkeiten
+verwendet werden, wenn sie zwei Bedingungen erfüllt:
+\begin{enumerate}
+\item Die Einträge von $T$ müssen als Wahrscheinlichkeiten interpretiert
+werden können, sie müssen also alle zwischen $0$ und $1$ sein:
+$0\le t_{ij}\le 1$ für $i,j\in\mathcal{S}$
+\item Die Matrix muss alle möglichen Fälle erfassen.
+Dazu ist notwendig, dass sich die Wahrscheinlichkeiten aller Übergänge
+aus einem Zustand $j$ zu $1$ summieren, also
+\[
+\sum_{i\in\mathcal{S}} p_{ij} = 1.
+\]
+Die Summe der Elemente einer Spalte
+\end{enumerate}
+
+\begin{beispiel}
+Die Permutationsmatrix einer Permutation $\sigma\in S_n$
+(Abschnitt~\label{buch:section:permutationsmatrizen})
+ist eine Matrix mit Einträgen $0$ und $1$, so dass die erste Bedingung
+erfüllt ist.
+In jeder Zeile oder Spalte kommt genau eine $1$ vor, so dass auch die
+zweite Bedingung erfüllt ist.
+Eine Permutationsmatrix beschreibt einen stochastischen Prozess, dessen
+Übergänge deterministisch sind.
+\end{beispiel}
+
+\subsubsection{Zustandswahrscheinlichkeiten}
+% XXX Zustandswahrscheinlichkeit
+Die Wahrscheinlichkeit, mit der sich der Prozess zum Zeitpunkt $n$
+im Zustand $i\in\mathcal{S}$ befindet, wird
+\[
+p_i(n)
+=
+P(X_i=n)
+\]
+geschrieben, die auch in einem Vektor $p(n)$ zusammengefasst
+werden können.
+Die Matrix der Übergangswahrscheinlichkeiten erlaubt, die Verteilung
+$p(n+1)$ aus der Verteilung $p(n)$ zu berechnen.
+Nach dem Satz von der totalen Wahrscheinlichkeit ist nämlich
+\[
+P(X_{n+1}=x)
+=
+\sum_{y\in\mathcal{S}}
+P(X_{n+1}=x|X_n=y) P(X_n=y)
+\qquad\text{oder}\qquad
+p^{(n+1)} = T(n+1,n) p^{(n)}
+\]
+in Matrixform.
+Die Zeitentwicklung kann also durch Multiplikation mit der Übergangsmatrix
+berechnet werden.
+
+\subsubsection{Zeitunabhängige Übergangswahrscheinlichkeiten}
+% XXX Übergangswahrscheinlichkeit
+Besonderes einfach wird die Situation, wenn die Übergangsmatrix $T(n+1,n)$
+nicht von der Zeit abhängt.
+In diesem Fall ist $T(n+1,n) = T$ für alle $n$.
+Eine solche Markov-Kette heisst {\em homogen}.
+\index{homogene Markov-Kette}%
+Die Mehrschritt-Übergangswahrscheinlichkeiten sind dann gegeben
+durch die Matrix-Potenzen $T(n+m,n)=T^m$.
+Im Folgenden gehen wir immer von einer homogenen Markov-Kette aus.
+
+\subsubsection{Stationäre Verteilung}
+% XXX stationäre Verteilung
+Im Beispiel der Google-Matrix erwarten wir intuitiv, dass sich mit
+der Zeit eine Verteilung einstellt, die sich über die Zeit nicht
+mehr ändert.
+Ein solche Verteilung heisst stationär.
+
+\begin{definition}
+Eine Verteilungsvektor $p$ heisst {\em stationär} für die
+homogene Markov-Kette mit Übergangsmatrix $T$, wenn $Tp=p$.
+\index{stationäre Verteilung}%
+\end{definition}
+
+Eine stationäre Verteilung ist offenbar ein Eigenvektor der Matrix
+$T$ zum Eigenwert $1$.
+Gefunden werden kann er als Lösung des Gleichungssystems $Tp=p$.
+Dazu muss die Matrix $T-E$ singulär sein.
+Die Summe einer Spalte von $T$ ist aber immer ein, da $E$ in jeder Spalte
+genau eine $1$ enthält, ist die Summe der Einträge einer Spalte von
+$T-E$ folglich $0$.
+Die Summe aller Zeilen von $T-E$ ist also $0$, die Matrix $T-E$
+ist singulär.
+Dies garantiert aber noch nicht, dass alle Einträge in diesem
+Eigenvektor auch tatsächlich nichtnegativ sind.
+Die Perron-Frobienus-Theorie von
+Abschnitt~\ref{buch:section:positive-vektoren-und-matrizen}
+beweist, dass sich immer ein Eigenvektor mit nichtnegativen
+Einträgen finden lässt.
+
+Es ist aber nicht garantiert, dass eine stationäre Verteilung
+auch eindeutig bestimmt ist.
+Dieser Fall tritt immer ein, wenn die geometrische Vielfachheit
+des Eigenwerts $1$ grösser ist als $1$.
+In Abschnitt~\ref{buch:subsection:elementare-eigenschaften}
+werden Bedingungen an eine Matrix $T$ untersucht, die garantieren,
+dass der Eigenraum zum Eigenvektor $1$ einedeutig bestimmt ist.
+
+\begin{beispiel}
+Als Beispiel dafür betrachten wir eine Permutation $\sigma\in S_n$
+und die zugehörige Permutationsmatrix $P$,
+wie sie in Abschnitt~\label{buch:section:permutationsmatrizen}
+beschrieben worden ist.
+Wir verwenden die
+Zyklenzerlegung (Abschnitt~\ref{buch:subsection:zyklenzerlegung})
+\(
+[n] = \{ Z_1, Z_2,\dots \}
+\)
+der Permutation $\sigma$, ist ist also $\sigma(Z_i) = Z_i$ für alle
+Zyklen.
+
+Jede Verteilung $p$, die auf jedem Zyklus konstant ist, ist eine
+stationäre Verteilung.
+Ist nämlich $i\in Z_k$, dann ist natürlich auch $\sigma(i)\in Z_k$,
+und damit ist $p_{\sigma(i)}=p_i$.
+
+Für jede Wahl von nichtnegativen Zahlen $z_i$ für $i=1,\dots,k$
+mit der Eigenschaft $z_1+\dots+z_k=1$ kann man eine stationäre
+Verteilung $p(z)$ konstruieren, indem man
+\[
+p_i(z)
+=
+\frac{z_i}{|Z_r|}
+\qquad\text{wenn}\quad i\in Z_r
+\]
+setzt.
+Die Konstruktion stellt sicher, dass sich die Komponenten zu $1$
+summieren.
+Wir können aus dem Beispiel auch ableiten, dass die geometrische
+Vielfachheit des Eigenvektors $1$ mindestens so gross ist wie die
+Anzahl der Zyklen der Permutation $\sigma$.
+\end{beispiel}
+
+\subsubsection{Irreduzible Markov-Ketten}
+Die Zyklen-Zerlegung einer Permutation bilden voneinander isolierte
+Mengen von Zuständen, es gibt keine Möglichkeit eines Übergangs zu
+einem anderen Zyklus.
+Die Zyklen können daher unabhängig voneinander studiert werden.
+Diese Idee kann auf allgemeine Markov-Ketten verallgemeinert werden.
+
+\begin{definition}
+Zwei Zustände $i,j\in\mathcal{S}$ kommunizieren, wenn die
+Übergangswahrscheinlichkeiten $T_{ij}(n) \ne 0$ und $T_{ij}(n)\ne 0$ sind
+für $n$ gross genug.
+\end{definition}
+
+Die Zustände, die zu verschiedenen Zyklen einer Permutation gehören,
+kommunizieren nicht.
+Gerade deshalb waren auch die verschiedenen stationären Verteilungen
+möglich.
+Eine eindeutige stationäre Verteilung können wir also nur erwarten,
+wenn alle Zustände miteinander kommunizieren.
+
+% XXX irreduzible Markov-Ketten
+\begin{definition}
+Eine homogene Markov-Kette heisst {\em irreduzibel}, alle Zustände miteinander
+kommunizieren.
+\index{irreduzible Markov-Kette}
+\end{definition}
+
+\begin{figure}
+\centering
+\includegraphics{chapters/80-wahrscheinlichkeit/images/markov2.pdf}
+\caption{Diese Markov-Kette zerfällt in verschiedene irreduzible
+Markov-Ketten, dere Zustandsmengen nicht miteinander kommunizieren.
+Solche Markov-Ketten können unabhängig voneinander studiert werden.
+\label{buch:wahrscheinlichkeit:fig:markovzerfall}}
+\end{figure}
+
+Die Bedingung der Irreduzibilität ist gleichbedeutend damit,
+dass für genügend grosses $n$ alle Matrixelemente von $T^n$ positiv sind.
+Solche Matrizen nennt man positiv,
+in Abschnitt~\ref{buch:section:positive-vektoren-und-matrizen}
+wird gezeigt, dass positive Matrizen immer eine eindeutige
+stationäre Verteilung haben.
+In Abbildung~\ref{buch:wahrscheinlichkeit:fig:markovzerfall}
+ist eine reduzible Markov-Kette dargestellt, die Zustandsmenge
+zerfällt in zwei Teilmengen von Zuständen, die nicht miteinander
+kommunizieren.
+Ein irreduzible Markov-Kette liegt vor, wenn sich ähnlich wie
+in Abbildung~\ref{buch:wahrscheinlichkeit:fig:diskretemarkovkette}
+jeder Zustand von jedem anderen aus erreichen lässt.
+
+Wenn sich der Vektorraum $\mathbb{R}^n$ in zwei unter $T$ invariante
+Unterräme zerlegen lässt, dann hat nach Wahl von Basen in den Unterräumen
+die Matrix $T$ die Form
+\[
+\left(
+\begin{array}{c|c}
+T_1&0\\
+\hline
+0&T_2
+\end{array}
+\right).
+\]
+Insbesondere kann man stationäre Verteilungen von $T_1$ und $T_2$
+unabhängig voneinander suchen.
+Ist $p_i$ eine stationäre Verteilung von $T_i$, dann ist
+\[
+T
+\left(
+\begin{array}{c}
+g_1p_1\\
+\hline g_2p_2
+\end{array}
+\right)
+=
+\left(
+\begin{array}{c}
+g_1T_1p_1\\
+\hline
+g_2T_2p_2
+\end{array}
+\right)
+=
+\left(
+\begin{array}{c}
+g_1p_1\\
+\hline
+g_2p_2
+\end{array}
+\right),\qquad
+\text{ für $g_i\in\mathbb{R}$.}
+\]
+Durch Wahl der Gewichte $g_i\ge 0$ mit $g_1+g_2=1$ lassen sich so
+die stationären Verteilungen für $T$ aus den stationären Verteilungen
+der $T_i$ ermitteln.
+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)
+=
+\{
+p\in\mathbb R_+^n\;|\; \text{$Tp=p $ und $\|p\|_1=1$}
+\}
+\]
+bilden was man eine konvexe Menge nennt.
+Sind nämlich $p$ und $q$ stationäre Verteilungen, dann gilt zunächst
+$Tp=p$ und $Tq=q$.
+Wegen der Linearität gilt aber auch $T(tp+(1-t)q)=tTp + (1-t)Tq
+=tp+(1-t)q$.
+Jede Verteilung auf der ``Verbindungsstrecke'' zwischen den beiden
+Verteilungen ist auch wieder stationär.
+
+\begin{definition}
+Eine {\em konvexe Kombination} von Vektoren $v_1,\dots,v_k\in\mathbb{R^n}$
+ist ein Vektor der Form
+\[
+v=t_1v_1+\dots + t_kv_k
+\qquad\text{mit}\quad
+t_i\ge 0\;\text{und}\;
+t_1+\dots+t_n = 1.
+\]
+\index{konvexe Kombination}%
+Eine Teilmenge $M\subset \mathbb{R}^n$ heisst konvex, wenn zu
+zwei Vektoren $x,y\in M$ auch jede konvexe Kombination von $x$ und $y$
+wieder in $M$ ist.
+\index{konvex}%
+\end{definition}
+
+Die konvexen Kombinationen der Vektoren sind Linearkombination
+mit nichtnegativen Koeffizienten. Sie bilden im Allgemeinen
+einen $(k-1)$-Simplex in $\mathbb{R}^n$.
+Für zwei Punkte $x$ und $y$ bilden die konvexen Kombination
+$tx+(1-t)y$ für $t\in[0,1]$ die Verbindungsstrecke der beiden
+Vektoren.
+Eine Menge ist also konvex, wenn sie mit zwei Punkten immer auch
+ihre Verbindungsstrecke enthält
+% XXX Bild für Konvexe Menge
+
+
+
+% XXX Grenzverteilung
+\subsubsection{Grenzverteilung}
+Im Beispiel der Google-Matrix wurde ein iterativer Algorithmus
+zur Berechnung des Pagerank verwendet.
+Es stellt sich daher die Frage, ob diese Methode für andere homogene
+Markov-Ketten auch funkioniert.
+Man beginnt also mit einer beliebigen Verteilung $p(0)$ und wendet
+die Übergangsmatrix $T$ wiederholt an.
+Es entsteht somit eine Folge $p(n) = T^np(0)$.
+
+\begin{definition}
+Falls die Folge $p(n) = T^np(0)$ konvergiert, heisst der Grenzwert
+\[
+p(\infty) = \lim_{n\to\infty} p(n)
+\]
+eine {\em Grenzverteilung} von $T$.
+\index{Grenzverteilung}%
+\end{definition}
+
+Falls eine Grenzverteilung existiert, dann ist sie eine stationäre
+Verteilung.
+Für eine stationäre Verteilung $p(0)$ ist die Folge $p(n)$ eine
+konstante Folge, sie konvergiert also gegen $p(0)$.
+Stationäre Verteilungen sind also automatisch Grenzverteilungen.
+Falls der Raum der stationären Verteilungen mehrdimensional sind,
+dann ist auch die Grenzverteilung nicht eindeutig bestimmt, selbst
+wenn sie existiert.
+Aber nicht einmal die Existenz einer Grenzverteilung ist garantiert,
+wie das folgende Beispiel zeigt.
+
+\begin{beispiel}
+Sei $T$ die Permutationsmatrix der zyklischen Verteilung von drei
+Elementen in $S_3$, also die Matrix
+\[
+T=\begin{pmatrix}
+0&0&1\\
+1&0&0\\
+0&1&0
+\end{pmatrix}.
+\]
+Die konstante Verteilung $\frac13U$ ist offensichtlich eine
+stationäre Verteilung.
+In Abschnitt~\ref{buch:section:positive-vektoren-und-matrizen}
+wird gezeigt, dass es die einzige ist.
+Sei jetzt $p(0)$ eine beliebiger Vektor in $\mathbb{R}^3$ mit
+nichtnegativen Einträgen, die sich zu $1$ summieren.
+Dann bilden die Vektoren $p(n)=T^np(0)$ einen Dreierzyklus
+\begin{align*}
+p(0)&=p(3)=p(6)=\dots =\begin{pmatrix}p_1(0)\\p_2(0)\\p_3(0)\end{pmatrix},
+\\
+p(1)&=p(4)=p(7)=\dots =\begin{pmatrix}p_2(0)\\p_3(0)\\p_1(0)\end{pmatrix},
+\\
+p(2)&=p(5)=p(8)=\dots =\begin{pmatrix}p_3(0)\\p_1(0)\\p_2(0)\end{pmatrix}.
+\end{align*}
+Die Folge $p(n)$ kann also nur dann konvergieren, wenn die drei
+Komponenten gleich sind.
+\end{beispiel}
+
+\subsubsection{Erwartungswert und Varianz}
+% XXX Erwartungswert und Varianz für eine Grenzverteilung
+Wenn sich im Laufe der Zeit eine Grenzverteilung einstellen soll, dann
+muss es auch möglich sein, Erwartungswert und Varianz dieser Verteilung
+zu berechnen.
+Dazu muss jedem Zustand ein Zahlenwert zugeordnet werden.
+Sei also
+\(
+g: \mathcal{S}\to R
+\)
+eine Funktion, die einem Zustand eine reelle Zahl zuordnet.
+Aus der Zufallsvariable $X_n$ des Zustands zur Zeit $n$ wird daraus
+die Zufallsvariable $Y_n=g(X_n)$ des Wertes zur Zeit $n$.
+Die Abbildung $g$ kann auch als Vektor mit der Komponenten $g_i$
+für $i\in\mathcal{S}$ betrachtet werden, wir verwenden für diesen
+Vektor wieder die Schreibweise $g$.
+
+Für die Verteilung $p(n)$ kann man jetzt auch Erwartungswert und
+Varianz berechnen.
+Der Erwartungswert ist
+\[
+E(Y)
+=
+\sum_{i\in\mathcal{S}} g_i p_i(n)
+=
+g^t p(n).
+\]
+Für die Varianz muss $g_i$ durch $g_i^2$ ersetzt werden.
+Dies kann am einfachsten mit dem Hadamard-Produkt geschrieben werden:
+\begin{align*}
+E(Y^2)
+&=
+\sum_{i\in\mathcal{S}} g_i p_i(n)
+=
+(g\odot g)^t p(n)
+\\
+E(Y^k)
+&=
+(g^{\odot k})^t p(n),
+\end{align*}
+wobei wir die Hadamard-Potenz $A^{\odot k}$ einer Matrix $A$ rekursiv
+durch
+\[
+A^{\odot 0}=E
+\qquad\text{und}\qquad
+A^{\odot k} = A\odot A^{\odot (k-1)}
+\]
+definieren.
+
+\subsubsection{Erwartungswert von Werten auf Übergängen}
+% XXX Erwartungswert für Zufallsvariablen, die von den Übergängen abhängen
+In Abschnitt~\ref{buch:section:paradoxon-von-parrondo} wird ein Spiel
+vorgestellt, in dem der Gewinn davon abhängt, welcher Übergang stattfindet,
+nicht welcher Zustand erreicht wird.
+Es git daher eine Matrix $G$ von Gewinnen, der Eintrag $g_{ij}$ ist
+der Gewinn, der bei einem Übergang von Zustand $j$ in den Zustand $i$
+ausgezahlt wird.
+Mit dieser Matrix lassen sich jetzt viele verschiedene Fragen beantworten:
+
+\begin{frage}
+\label{buch:wahrscheinlichkeit:frage1}
+Mit welchem Gewinn kann man in Runde $n$ des Spiels rechnen,
+wenn $p(n-1)$ die Verteilung zur Zeit $n-1$ ist?
+\end{frage}
+
+Der Erwartungswert ist
+\begin{align*}
+E(Y)
+&=
+\sum_{i,j\in\mathcal{S}}
+g_{ji} t_{ji} p_i(n-1)
+\intertext{oder in Matrixform}
+&=
+U^t
+(G\odot T)
+p(n-1).
+\end{align*}
+
+\begin{frage}
+Mit welchen Gewinnen kann man rechnen, wenn der Prozess sich zu Beginn
+einer Spielrunde im Zustand $i$ befindet?
+\end{frage}
+
+Dies ist der Spezialfall der Frage~\ref{buch:wahrscheinlichkeit:frage1}
+für die Verteilung $p_j(n-1) = \delta_{ij}$.
+Der Erwartungswert ist die Summe der Spalte $j$ der Matrix $G\odot T$.
+Man kann das Produkt $U^t(G\odot T)$ also auch als eine Zeilenvektor
+von Gewinnerwartungen unter der Vorbedingung $X_{n-1}=j$ betrachten.
+\[
+\begin{pmatrix}
+E(Y|X_{n-1}=1)
+&\dots&
+E(Y|X_{n-1}=n)
+\end{pmatrix}
+=
+U^t (G\odot T).
+\]
+Indem man $G$ durch $G^{\odot k}$ ersetzt, kann man beliebige höhere
+Momente berechnen.
+
+\subsection{Absorbierende Zustände}
+% XXX Definition
+Eine Grenzverteilung beschreibt die relative Häufigkeit, mit der
+der Prozess in den verschiedenen Zuständen vorbeikommt.
+In einem Spiel, in dem der Spieler ruiniert werden kann, gibt es
+aus dem Ruin-Zustand keinen Weg zurück.
+Der Spieler bleibt in diesem Zustand.
+
+\begin{definition}
+Ein Zustand $i$ einer homogenen Markov-Kette mit Übergangsmatrix $T$
+heisst {\em absorbierend}, wenn $T_{ii}=1$ ist.
+\index{absorbierender Zustand}%
+Eine Markov-Kette mit mindestens einem absorbierenden Zustand heisst
+{\em absorbierende Markov-Kette}.
+\index{absorbierende Markov-Kette}%
+Nicht absorbierende Zustände heissen {\em transient}
+\index{transienter Zustand}%
+\end{definition}
+
+\begin{figure}
+\centering
+\includegraphics{chapters/80-wahrscheinlichkeit/images/markov3.pdf}
+\caption{Markov-Kette mit absorbierenden Zuständen (blau hinterlegt).
+Erreicht die Markov-Kette einen absorbierenden Zustand, dann verbleibt
+sie für alle zukünftigen Zustände in diesem Zustand.
+\label{buch:wahrscheinlichkeit:fig:abs}}
+\end{figure}
+
+Eine Markov-Kette kann mehrere absorbierende Zustände haben, wie in
+Abbildung~\ref{buch:wahrscheinlichkeit:fig:abs} dargestellt.
+Indem man die absorbierenden Zustände zuerst auflistet, bekommt die
+Übergangsmatrix die Form
+\[
+T=
+\left(
+\begin{array}{c|c}
+E&R\\
+\hline
+0&Q
+\end{array}
+\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
+\[
+T^2
+=
+\left(
+\begin{array}{c|c}
+E&R+RQ \\
+\hline
+0&Q^2
+\end{array}
+\right),
+\quad
+T^3
+=
+\left(
+\begin{array}{c|c}
+E&R+RQ+RQ^2 \\
+\hline
+0&Q^3
+\end{array}
+\right),
+\;
+\dots,
+\;
+T^k
+=
+\left(
+\begin{array}{c|c}
+E&\displaystyle R\sum_{l=0}^{k-1} Q^l \\
+\hline
+0&Q^k
+\end{array}
+\right).
+\]
+Da man früher oder später in einem absorbierenden Zustand landet,
+muss $\lim_{k\to\infty} Q^k=0$ sein.
+Die Summe in der rechten oberen Teilmatrix kann man als geometrische
+Reihe summieren, man erhält die Matrix
+\[
+\sum_{l=0}^{k-1} Q^l = (E-Q)^{-1}(E-Q^k),
+\]
+die für $k\to\infty$ gegen
+\[
+N
+=
+\lim_{k\to\infty} \sum_{l=0}^{k-1} Q^l
+=
+(E-Q)^{-1}
+\]
+konvergiert.
+Die Matrix $N$ heisst die {\em Fundamentalmatrix} der absorbierenden
+Markov-Kette.
+\index{Fundamental-Matrix}%
+
+\subsubsection{Absorbtionszeit}
+% XXX Absorptionszeit
+Wie lange dauert es im Mittel, bis der Prozess in einem
+Absorptionszustand $i$ stecken bleibt?
+Die Fundamentalmatrix $N$ der Markov-Kette beantwortet diese
+Frage.
+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.
+
+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
+Die mittlere Wartezeit bis zum Erreichen eines Zustands kann mit der
+Theorie zur Berechnung der Absorptionszeit berechnet werden.
+Dazu modifiziert man den Prozess dahingehend, dass der Zielzustand
+ein absorbierender Zustand wird.
+Der Einfachheit halber gehen wir davon aus, dass der Zustand $1$
+der Zielzustand ist.
+Wir ersetzen die Übergangsmatrix $T$ durch die Matrix
+\[
+\tilde{T}
+=
+\left(
+\begin{array}{c|ccc}
+1 &t_{12}&\dots &t_{1n}\\
+\hline
+0 &t_{22}&\dots &t_{2n}\\
+\vdots&\dots &\ddots&\vdots\\
+0 &t_{n2}&\dots &t_{nn}
+\end{array}\right).
+\]
+$\tilde{T}$ hat den Zustand $1$ als absorbierenden Zustand.
+Die $Q$ und $R$ sind
+\[
+\tilde{R}
+=
+\begin{pmatrix}t_{12}&\dots&t_{1n}\end{pmatrix},
+\quad
+\tilde{Q}
+=
+\begin{pmatrix}
+t_{22}&\dots &t_{2n}\\
+\vdots&\ddots&\vdots\\
+t_{n2}&\dots &t_{nn}
+\end{pmatrix}.
+\]
+Die Wartezeit bis zum Erreichen des Zustands $i$ ausgehend von einem
+Zustand $n$ kann jetzt aus der Absorbtionszeit der Markov-Kette
+im Zustand $1$ mit Hilfe der Fundamentalmatrix
+\[
+\tilde{N}
+=
+(E-\tilde{Q})^{-1}
+\]
+berechnet werden.
diff --git a/buch/chapters/80-wahrscheinlichkeit/parrondo.tex b/buch/chapters/80-wahrscheinlichkeit/parrondo.tex
index ac4163e..a62d813 100644
--- a/buch/chapters/80-wahrscheinlichkeit/parrondo.tex
+++ b/buch/chapters/80-wahrscheinlichkeit/parrondo.tex
@@ -6,3 +6,801 @@
\section{Das Paradoxon von Parrondo
\label{buch:section:paradoxon-von-parrondo}}
\rhead{Das Paradoxon von Parrondo}
+Das Paradoxon von Parrondo ist ein der Intuition widersprechendes
+Beispiel für eine Kombination von Spielen mit negativer Gewinnerwartung,
+deren Kombination zu einem Spiel mit positiver Gewinnerwartung führt.
+Die Theorie der Markov-Ketten und der zugehörigen Matrizen ermöglicht
+eine sehr einfache Analyse.
+
+%
+% Parrondo Teilspiele
+%
+\subsection{Die beiden Teilspiele
+\label{buch:subsection:teilspiele}}
+
+\subsubsection{Das Spiel $A$}
+Das Spiel $A$ besteht darin, eine Münze zu werfen.
+Je nach Ausgang gewinnt oder verliert der Spieler eine Einheit.
+Sei $X$ die Zufallsvariable, die den gewonnen Betrag beschreibt.
+Für eine faire Münze ist die Gewinnerwartung in diesem Spiel natürlich
+$E(X)=0$.
+Wenn die Wahrscheinlichkeit für einen Gewinn $1+e$ ist, dann muss
+die Wahrscheinlichkeit für einen Verlust $1-e$ sein, und die
+Gewinnerwartung ist
+\(
+E(X)
+=
+1\cdot P(X=1) + (-1)\cdot P(X=-1)
+=
+1+e + (-1)(1-e)
+=
+2e.
+\)
+Die Gewinnerwartung ist also genau dann negativ, wenn $e<0$ ist.
+
+\subsubsection{Das Spiel $B$}
+Das zweite Spiel $B$ ist etwas komplizierter, da der Spielablauf vom
+aktuellen Kapital $K$ des Spielers abhängt.
+Wieder gewinnt oder verliert der Spieler eine Einheit,
+die Gewinnwahrscheinlichkeit hängt aber vom Dreierrest des Kapitals ab.
+Sei $Y$ die Zufallsvariable, die den Gewinn beschreibt.
+Ist $K$ durch drei teilbar, ist die Gewinnwahrscheinlichkeit $\frac1{10}$,
+andernfalls ist sie $\frac34$.
+Formell ist
+\begin{equation}
+\begin{aligned}
+P(Y=1|\text{$K$ durch $3$ teilbar}) &= \frac{1}{10}
+\\
+P(Y=1|\text{$K$ nicht durch $3$ teilbar}) &= \frac{3}{4}
+\end{aligned}
+\label{buch:wahrscheinlichkeit:eqn:Bwahrscheinlichkeiten}
+\end{equation}
+Insbesondere ist die Wahrscheinlichkeit für einen Gewinn in zwei der
+Fälle recht gross, in einem Fall aber sehr klein.
+
+\subsubsection{Übergangsmatrix im Spiel $B$}
+\begin{figure}
+\centering
+\includegraphics{chapters/80-wahrscheinlichkeit/images/spielB.pdf}
+\caption{Zustandsdiagramm für das Spiel $B$, Zustände sind die
+Dreierreste des Kapitals.
+\label{buch:wahrscheinlichkeit:fig:spielB}}
+\end{figure}%
+Für den Verlauf des Spiels spielt nur der Dreierrest des Kapitals
+eine Rolle.
+Es gibt daher drei mögliche Zustände $0$, $1$ und $2$.
+In einem Spielzug finde ein Übergang in einen anderen Zustand
+statt, der Eintrag $b_{ij}$ ist die Wahrscheinlichkeit
+\[
+b_{ij}
+=
+P(K\equiv i|K\equiv j),
+\]
+dass ein Übergang vom Zustand $j$ in den Zustand $i$ stattfindet.
+Die Matrix ist
+\[
+B=
+\begin{pmatrix}
+0 &\frac14 &\frac34\\
+\frac1{10} &0 &\frac14\\
+\frac9{10} &\frac34 &0
+\end{pmatrix}.
+\]
+
+\subsubsection{Gewinnerwartung in einem Einzelspiel $B$}
+Die Gewinnerwartung einer einzelnen Runde des Spiels $B$ hängt natürlich
+ebenfalls vom Ausgangskapital ab.
+Mit den Wahrscheinlichkeiten von
+\eqref{buch:wahrscheinlichkeit:eqn:Bwahrscheinlichkeiten}
+findet man die Gewinnerwartung
+\begin{equation}
+\begin{aligned}
+E(Y| \text{$K$ durch $3$ teilbar})
+&=
+1\cdot P(Y=1|K\equiv 0\mod 3)
++
+(-1)\cdot P(Y=-1|K\equiv 0\mod 3)
+\\
+&=
+\frac1{10}
+-
+\frac{9}{10}
+=
+-\frac{8}{10}
+\\
+E(Y| \text{$K$ nicht durch $3$ teilbar})
+&=
+1\cdot P(Y=1|K\not\equiv 0\mod 3)
++
+(-1)\cdot P(Y=-1|K\not\equiv 0\mod 3)
+\\
+&=
+\frac34-\frac14
+=
+\frac12.
+\end{aligned}
+\label{buch:wahrscheinlichkeit:eqn:Berwartungen}
+\end{equation}
+Falls $K$ durch drei teilbar ist, muss der Spieler
+also mit einem grossen Verlust rechnen, andernfalls mit einem
+moderaten Gewinn.
+
+Ohne weiteres Wissen über das Anfangskapital ist es zulässig anzunehmen,
+dass die drei möglichen Reste die gleiche Wahrscheinlichkeit haben.
+Die Gewinnerwartung in diesem Fall ist dann
+\begin{align}
+E(Y)
+&=
+E(Y|\text{$K$ durch $3$ teilbar}) \cdot \frac13
++
+E(Y|\text{$K$ nicht durch $3$ teilbar}) \cdot \frac23
+\notag
+\\
+&=
+-\frac{8}{10}\cdot\frac{1}{3}
++
+\frac{1}{2}\cdot\frac{2}{3}
+=
+-\frac{8}{30}+\frac{10}{30}
+=
+\frac{2}{30}
+=
+\frac{1}{15}.
+\label{buch:wahrscheinlichkeit:eqn:Beinzelerwartung}
+\end{align}
+Unter der Annahme, dass alle Reste die gleiche Wahrscheinlichkeit haben,
+ist das Spiel also ein Gewinnspiel.
+
+Die Berechnung der Gewinnerwartung in einem Einzelspiel kann man
+wie folgt formalisieren.
+Die Matrix $B$ gibt die Übergangswahrscheinlichkeiten zwischen
+verschiedenen Zuständen.
+Die Matrix
+\[
+G=\begin{pmatrix}
+ 0&-1& 1\\
+ 1& 0&-1\\
+-1& 1& 0
+\end{pmatrix}
+\]
+gibt die Gewinne an, die bei einem Übergang anfallen.
+Die Matrixelemente $g_{ij}b_{ij}$ des Hadamard-Produktes
+$G\odot B$
+von $G$ mit $B$ enthält in den Spalten die Gewinnerwartungen
+für die einzelnen Übergänge aus einem Zustand.
+Die Summe der Elemente der Spalte $j$ enthält die Gewinnerwartung
+\[
+E(Y|K\equiv j)
+=
+\sum_{i=0}^2 g_{ij}b_{ij}
+\]
+für einen Übergang aus dem Zustand $j$.
+Man kann dies auch als einen Zeilenvektor schreiben, der durch Multiplikation
+der Matrix $G\odot B$ mit dem Zeilenvektor
+$U^t=\begin{pmatrix}1&1&1\end{pmatrix}$
+entsteht:
+\[
+\begin{pmatrix}
+E(Y|K\equiv 0)&
+E(Y|K\equiv 1)&
+E(Y|K\equiv 2)
+\end{pmatrix}
+=
+U^t
+G\odot B.
+\]
+Die Gewinnerwartung ist dann das Produkt
+\[
+E(Y)
+=
+\sum_{i=0}^2
+E(Y|K\equiv i) p_i
+=
+U^t
+(G\odot B)p.
+\]
+Tatsächlich ist
+\[
+G\odot B
+=
+\begin{pmatrix}
+ 0 &-\frac14 & \frac34\\
+ \frac1{10} & 0 &-\frac14\\
+-\frac9{10} & \frac34 & 0
+\end{pmatrix}
+\quad\text{und}\quad
+U^t G\odot B
+=
+\begin{pmatrix}-\frac{8}{10}&\frac12&\frac12\end{pmatrix}.
+\]
+Dies stimmt mit den Erwartungswerten in
+\eqref{buch:wahrscheinlichkeit:eqn:Berwartungen}
+überein.
+Die gesamte Geinnerwartung ist dann
+\begin{equation}
+(G\odot B)
+\begin{pmatrix}\frac13\\\frac13\\\frac13\end{pmatrix}
+=
+\begin{pmatrix}-\frac{8}{10}&\frac12&\frac12\end{pmatrix}
+\frac13U
+=
+\frac13\biggl(-\frac{8}{10}+\frac12+\frac12\biggr)
+=
+\frac13\cdot\frac{2}{10}
+=
+\frac{1}{15},
+\label{buch:wahrscheinlichkeit:eqn:BodotEinzelerwartung}
+\end{equation}
+dies stimmt mit \eqref{buch:wahrscheinlichkeit:eqn:Beinzelerwartung}
+überrein.
+
+\subsubsection{Das wiederholte Spiel $B$}
+Natürlich spielt man das Spiel nicht nur einmal, sondern man wiederholt es.
+Es ist verlockend anzunehmen, dass die Dreierreste $0$, $1$ und $2$ des
+Kapitals immer noch gleich wahrscheinlich sind.
+Dies braucht jedoch nicht so zu sein.
+Wir prüfen die Hypothese daher, indem wir die Wahrscheinlichkeit
+für die verschiedenen Dreierreste des Kapitals in einem interierten
+Spiels ausrechnen.
+
+Das Spiel kennt die Dreierreste als die drei für das Spiel ausschlaggebenden
+Zuständen.
+Das Zustandsdiagramm~\ref{buch:wahrscheinlichkeit:fig:spielB} zeigt
+die möglichen Übergänge und ihre Wahrscheinlichkeiten, die zugehörige
+Matrix ist
+\[
+B
+=
+\begin{pmatrix}
+0 &\frac14 &\frac34\\
+\frac1{10} &0 &\frac14\\
+\frac9{10} &\frac34 &0
+\end{pmatrix}
+\]
+Die Matrix $B$ ist nicht negativ und man kann nachrechnen, dass $B^2>0$ ist.
+Damit ist die Perron-Frobenius-Theorie von
+Abschnitt~\ref{buch:section:positive-vektoren-und-matrizen}
+anwendbar.
+
+Ein Eigenvektor zum Eigenwert $1$ kann mit Hilfe des Gauss-Algorithmus
+gefunden werden:
+\begin{align*}
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
+\hline
+-1 &\frac14 &\frac34 \\
+\frac1{10} &-1 &\frac14 \\
+\frac9{10} &\frac34 &-1 \\
+\hline
+\end{tabular}
+&\rightarrow
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
+\hline
+1 &-\frac14 &-\frac34 \\
+0 &-\frac{39}{40} & \frac{13}{40} \\
+0 & \frac{39}{40} &-\frac{13}{40} \\
+\hline
+\end{tabular}
+\rightarrow
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
+\hline
+1 &-\frac14 &-\frac34 \\
+0 & 1 &-\frac13 \\
+0 & 0 & 0 \\
+\hline
+\end{tabular}
+\rightarrow
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
+\hline
+1 & 0 &-\frac56 \\
+0 & 1 &-\frac13 \\
+0 & 0 & 0 \\
+\hline
+\end{tabular}
+\end{align*}
+Daraus liest man einen möglichen Lösungsvektor mit den Komponenten
+$5$, $2$ und $6$ ab.
+Wir suchen aber einen Eigenvektor, der als Wahrscheinlichkeitsverteilung
+dienen kann.
+Dazu müssen sich die Komponente zu $1$ summieren, was man durch normieren
+in der $l^1$-Norm erreichen kann:
+\begin{equation}
+p
+=
+\begin{pmatrix}
+P(K\equiv 0)\\
+P(K\equiv 1)\\
+P(K\equiv 2)
+\end{pmatrix}
+=
+\frac{1}{5+2+6}
+\begin{pmatrix}
+5\\2\\6
+\end{pmatrix}
+=
+\frac{1}{13}
+\begin{pmatrix}
+5\\2\\6
+\end{pmatrix}
+\approx
+\begin{pmatrix}
+ 0.3846 \\
+ 0.1538 \\
+ 0.4615
+\end{pmatrix}.
+\label{buch:wahrscheinlichkeit:spielBP}
+\end{equation}
+Die Hypothese, dass die drei Reste gleich wahrscheinlich sind, ist
+also nicht zutreffend.
+
+Die Perron-Frobenius-Theorie sagt, dass sich die
+Verteilung~\ref{buch:wahrscheinlichkeit:spielBP} nach einiger Zeit
+einstellt.
+Wir können jetzt auch die Gewinnerwartung in einer einzelnen
+Runde des Spiels ausgehend von dieser Verteilung der Reste des Kapitals
+berechnen.
+Dazu brauchen wir zunächst die Wahrscheinlichkeiten für Gewinn oder
+Verlust, die wir mit dem Satz über die totale Wahrscheinlichkeit
+nach
+\begin{align*}
+P(Y=+1)
+&=
+P(Y=+1|K\equiv 0) \cdot P(K\equiv 0)
++
+P(Y=+1|K\equiv 1) \cdot P(K\equiv 1)
++
+P(Y=+1|K\equiv 2) \cdot P(K\equiv 2)
+\\
+&=
+\frac{1}{10}\cdot\frac{5}{13}
++
+\frac{3}{4} \cdot\frac{2}{13}
++
+\frac{3}{4} \cdot\frac{6}{13}
+\\
+&=
+\frac1{13}\biggl(
+\frac{1}{2}+\frac{3}{2}+\frac{9}{2}
+\biggr)
+=
+\frac{13}{26}
+=
+\frac12
+\\
+P(Y=-1)
+&=
+P(Y=-1|K\equiv 0) \cdot P(K\equiv 0)
++
+P(Y=-1|K\equiv 1) \cdot P(K\equiv 1)
++
+P(Y=-1|K\equiv 2) \cdot P(K\equiv 2)
+\\
+&=
+\frac{9}{10}\cdot\frac{5}{13}
++
+\frac{1}{4} \cdot\frac{2}{13}
++
+\frac{1}{4} \cdot\frac{6}{13}
+\\
+&=
+\frac{1}{13}\biggl(
+\frac{9}{2} + \frac{1}{2} + \frac{3}{2}
+\biggr)
+=
+\frac{1}{2}
+\end{align*}
+berechnen können.
+Gewinn und Verlust sind also gleich wahrscheinlich, das Spiel $B$ ist also
+ebenfalls fair.
+
+Auch diese Gewinnwahrscheinlichkeit kann etwas formeller mit dem
+Hadamard-Produkt berechnet werden:
+\[
+U^t (G\odot B) p
+=
+\begin{pmatrix}-\frac{8}{10}&\frac12&\frac12\end{pmatrix}
+\frac{1}{13}
+\begin{pmatrix}
+5\\2\\6
+\end{pmatrix}
+=
+-\frac{8}{10}\cdot\frac{5}{13}
++\frac{1}{2} \cdot\frac{2}{13}
++\frac{1}{2} \cdot\frac{6}{13}
+=
+\frac{1}{26}(-8 + 2+ 6)
+=
+0,
+\]
+wie erwartet.
+
+\subsubsection{Das modifizierte Spiel $\tilde{B}$}
+\begin{figure}
+\centering
+\includegraphics{chapters/80-wahrscheinlichkeit/images/spielBtilde.pdf}
+\caption{Zustandsdiagramm für das modifizerte Spiel $\tilde{B}$,
+Zustände sind die Dreierreste des Kapitals.
+Gegenüber dem Spiel $B$
+(Abbildung~\ref{buch:wahrscheinlichkeit:fig:spielB})
+sind die Wahrscheinlichkeiten für Verlust
+um $\varepsilon$ vergrössert und die Wahrscheinlichkeiten für Gewinn um
+$\varepsilon$ verkleinert worden.
+\label{buch:wahrscheinlichkeit:fig:spielBtile}}
+\end{figure}
+%
+Wir modifizieren jetzt das Spiel $B$ derart, dass die Wahrscheinlichkeiten
+für Gewinn um $\varepsilon$ verringert werden und die Wahrscheinlichkeiten
+für Verlust um $\varepsilon$ vergrössert werden.
+Die Übergangsmatrix des modifzierten Spiels $\tilde{B}$ ist
+\[
+\tilde{B}
+=
+\begin{pmatrix}
+ 0 & \frac{1}{4}+\varepsilon & \frac{3}{4}-\varepsilon \\
+\frac{1}{10}-\varepsilon & 0 & \frac{1}{4}+\varepsilon \\
+\frac{9}{10}+\varepsilon & \frac{3}{4}-\varepsilon & 0
+\end{pmatrix}
+=
+B
++
+\varepsilon
+\underbrace{
+\begin{pmatrix}
+ 0& 1&-1\\
+-1& 0& 1\\
+ 1&-1& 0
+\end{pmatrix}
+}_{\displaystyle F}
+\]
+Wir wissen bereits, dass der Vektor $p$
+von \eqref{buch:wahrscheinlichkeit:spielBP}
+als stationäre Verteilung
+Eigenvektor zum Eigenwert
+$B$ ist, wir versuchen jetzt in erster Näherung die modifizierte
+stationäre Verteilung $p_{\varepsilon}=p+\varepsilon p_1$ des modifizierten
+Spiels zu bestimmen.
+
+\subsubsection{Gewinnerwartung im modifizierten Einzelspiel}
+Die Gewinnerwartung aus den verschiedenen Ausgangszuständen kann mit Hilfe
+des Hadamard-Produktes berechnet werden.
+Wir berechnen dazu zunächst
+\[
+G\odot \tilde{B}
+=
+G\odot (B+\varepsilon F)
+=
+G\odot B + \varepsilon G\odot F
+\quad\text{mit}\quad
+G\odot F = \begin{pmatrix}
+0&1&1\\
+1&0&1\\
+1&1&0
+\end{pmatrix}.
+\]
+Nach der früher dafür gefundenen Formel ist
+\begin{align*}
+\begin{pmatrix}
+E(Y|K\equiv 0)&
+E(Y|K\equiv 1)&
+E(Y|K\equiv 2)
+\end{pmatrix}
+&=
+U^t (G\odot \tilde{B})
+\\
+&=
+U^t (G\odot B)
++
+\varepsilon
+U^t (G\odot F)
+\\
+&=
+\begin{pmatrix} -\frac{8}{10}&\frac12&\frac12 \end{pmatrix}
++
+2\varepsilon U^t
+\\
+&=
+\begin{pmatrix} -\frac{8}{10}+2\varepsilon&\frac12+2\varepsilon&\frac12+2\varepsilon \end{pmatrix}.
+\end{align*}
+Unter der Annahme gleicher Wahrscheinlichkeiten für die Ausgangszustände,
+erhält man die Gewinnerwartung
+\begin{align*}
+E(Y)
+&=
+U^t(G\odot \tilde{B})
+\begin{pmatrix}
+\frac13\\
+\frac13\\
+\frac13
+\end{pmatrix}
+\\
+&=
+U^t
+(G\odot B)
+\frac13 U
++
+\varepsilon
+U^t
+(G\odot F)
+\frac13 U
+\\
+&=
+\frac1{15}
++
+2\varepsilon
+\end{align*}
+unter Verwendung der in
+\eqref{buch:wahrscheinlichkeit:eqn:BodotEinzelerwartung}
+berechneten Gewinnerwartung für das Spiel $B$.
+
+\subsubsection{Iteration des modifizierten Spiels}
+Der Gaussalgorithmus liefert nach einiger Rechnung, die man am besten
+mit einem Computeralgebrasystem durchführt,
+\[
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
+\hline
+-1 & \frac{1}{4}+\varepsilon & \frac{3}{4}-\varepsilon \\
+\frac{1}{10}-\varepsilon & -1 & \frac{1}{4}+\varepsilon \\
+\frac{9}{10}+\varepsilon & \frac{3}{4}-\varepsilon & -1 \\
+\hline
+\end{tabular}
+\rightarrow
+% [ 2 ]
+% [ 80 epsilon + 12 epsilon + 78 ]
+%(%o15) Col 1 = [ ]
+% [ 0 ]
+% [ ]
+% [ 0 ]
+% [ 0 ]
+% [ ]
+% Col 2 = [ 2 ]
+% [ 80 epsilon + 12 epsilon + 78 ]
+% [ ]
+% [ 0 ]
+% [ 2 ]
+% [ (- 80 epsilon ) + 40 epsilon - 65 ]
+% [ ]
+% Col 3 = [ 2 ]
+% [ (- 80 epsilon ) - 12 epsilon - 26 ]
+% [ ]
+% [ 0 ]
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
+\hline
+1&0&-\frac{65-40\varepsilon+80\varepsilon^2}{78+12\varepsilon+80\varepsilon^2}\\
+0&0&-\frac{26+12\varepsilon+80\varepsilon^2}{78+12\varepsilon+80\varepsilon^2}\\
+0&0&0\\
+\hline
+\end{tabular},
+\]
+woraus man die Lösung
+\[
+p
+=
+\begin{pmatrix}
+65-40\varepsilon+80\varepsilon^2\\
+26+12\varepsilon+80\varepsilon^2\\
+78+12\varepsilon+80\varepsilon^2\\
+\end{pmatrix}
+\]
+ablesen kann.
+Allerdings ist dies keine Wahrscheinlichkeitsverteilung,
+wir müssen dazu wieder normieren.
+Die Summe der Komponenten ist
+\[
+\|p\|_1
+=
+169 - 16 \varepsilon + 240 \varepsilon^2.
+\]
+Damit bekommen wir für die Lösung bis zur ersten Ordnung
+\[
+p_\varepsilon
+=
+\frac{1}{ 169 - 16 \varepsilon + 240 \varepsilon^2}
+\begin{pmatrix}
+65-40\varepsilon+80\varepsilon^2\\
+26+12\varepsilon+80\varepsilon^2\\
+78+12\varepsilon+80\varepsilon^2\\
+\end{pmatrix}
+=
+% [ 2 3 ]
+% [ 5 440 epsilon 34080 epsilon 17301120 epsilon ]
+% [ -- - ----------- - -------------- + ----------------- + . . . ]
+% [ 13 2197 371293 62748517 ]
+% [ ]
+% [ 2 3 ]
+%(%o19)/T/ [ 2 188 epsilon 97648 epsilon 6062912 epsilon ]
+% [ -- + ----------- + -------------- - ---------------- + . . . ]
+% [ 13 2197 371293 62748517 ]
+% [ ]
+% [ 2 3 ]
+% [ 6 252 epsilon 63568 epsilon 11238208 epsilon ]
+% [ -- + ----------- - -------------- - ----------------- + . . . ]
+% [ 13 2197 371293 62748517 ]
+\frac{1}{13}
+\begin{pmatrix} 5\\2\\6 \end{pmatrix}
++
+\frac{\varepsilon}{2197}
+\begin{pmatrix}
+-440\\188\\252
+\end{pmatrix}
++
+O(\varepsilon^2).
+\]
+Man beachte, dass der konstante Vektor der ursprüngliche Vektor $p$
+für das Spiel $B$ ist.
+Der lineare Term ist ein Vektor, dessen Komponenten sich zu $1$ summieren,
+in erster Ordnung ist also die $l^1$-Norm des Vektors wieder
+$\|p_\varepsilon\|_1=0+O(\varepsilon^2)$.
+
+Mit den bekannten Wahrscheinlichkeiten kann man jetzt die
+Gewinnerwartung in einem einzeln Spiel ausgehend von der Verteilung
+$p_{\varepsilon}$ berechnen.
+Dazu braucht man das Hadamard-Produkt
+\[
+G\odot \tilde{B}
+=
+G=\begin{pmatrix}
+ 0&-1& 1\\
+ 1& 0&-1\\
+-1& 1& 0
+\end{pmatrix}
+\odot
+\begin{pmatrix}
+0 &\frac14+\varepsilon & \frac34-\varepsilon \\
+\frac{1}{10}-\varepsilon & 0 & \frac14+\varepsilon \\
+\frac{9}{10}+\varepsilon &\frac34-\varepsilon & 0
+\end{pmatrix}
+=
+\begin{pmatrix}
+ 0 &-\frac14-\varepsilon & \frac34-\varepsilon \\
+ \frac{1}{10}-\varepsilon & 0 &-\frac14-\varepsilon \\
+-\frac{9}{10}-\varepsilon & \frac34-\varepsilon & 0
+\end{pmatrix}
+\]
+Wie früher ist der erwartete Gewinn
+\begin{align*}
+E(Y)
+&=
+U^t (G\odot \tilde{B}) p_{\varepsilon}
+\\
+&=
+\begin{pmatrix}
+-\frac{3}{10}-2\varepsilon & \frac12-2\varepsilon & \frac12-2\varepsilon
+\end{pmatrix}
+p_{\varepsilon}
+\\
+% 3 2
+% 480 epsilon - 48 epsilon + 294 epsilon
+%(%o50) - ----------------------------------------
+% 2
+% 240 epsilon - 16 epsilon + 169
+&=
+-
+\varepsilon\cdot
+\frac{
+294-48\varepsilon+480\varepsilon^2
+}{
+169-16\varepsilon+240\varepsilon^2
+}
+=
+-\frac{294}{169}\varepsilon + O(\varepsilon^2).
+\end{align*}
+Insbesondere ist also die Gewinnerwartung negativ für nicht zu grosse
+$\varepsilon>0$.
+Das Spiel ist also ein Verlustspiel.
+
+%
+% Die Kombination
+%
+\subsection{Kombination der Spiele
+\label{buch:subsection:kombination}}
+Jetzt werden die beiden Spiele $A$ und $B$ zu einem neuen
+Spiel kombiniert.
+Für das Spiel $A$ haben wir bis jetzt keine Übergansmatrix aufgestellt,
+da das Kapital darin keine Rolle spielt.
+Um die beiden Spiele kombinieren zu können brauchen wir aber die Übergansmatrix
+für die drei Zustände $K\equiv 0,1,2$.
+Sie ist
+\[
+A=\begin{pmatrix}
+0&\frac12&\frac12\\
+\frac12&0&\frac12\\
+\frac12&\frac12&0
+\end{pmatrix}.
+\]
+
+\subsubsection{Das Spiel $C$}
+In jeder Durchführung des Spiels wird mit einem Münzwurf entschieden,
+ob Spiel $A$ oder Spiel $B$ gespielt werden soll.
+Mit je Wahrscheinlichkeit $\frac12$ werden also die Übergansmatrizen
+$A$ oder $B$ verwendet:
+\[
+P(K\equiv i|K\equiv j)
+=
+A\cdot P(\text{Münzwurf Kopf})
++
+B\cdot P(\text{Münzwurf Kopf})
+=
+\frac12(A+B)
+=
+\begin{pmatrix}
+0 & \frac{3}{8} & \frac{5}{8} \\
+\frac{3}{10} & 0 & \frac{3}{8} \\
+\frac{7}{10} & \frac{5}{8} & 0
+\end{pmatrix}
+\]
+Die Gewinnerwartung in einem Einzelspiel ist
+\begin{align*}
+E(Y)
+&=
+U^t
+(G\odot C)
+\frac13U
+\\
+&=
+U^t
+\begin{pmatrix}
+ 0 &-\frac{3}{8} & \frac{5}{8} \\
+ \frac{3}{10} & 0 &-\frac{3}{8} \\
+-\frac{7}{10} & \frac{5}{8} & 0
+\end{pmatrix}
+\frac13U
+\\
+&=
+\begin{pmatrix}
+-\frac{2}{5} & \frac{1}{4} & \frac{1}{4}
+\end{pmatrix}
+\frac13U
+=
+\frac13\biggl(-\frac{2}{5}+\frac{1}{4}+\frac{1}{4}\biggr)
+=
+-\frac{1}{30}
+\end{align*}
+Das Einzelspiel ist also ein Verlustspiel.
+
+\subsubsection{Das iterierte Spiel $C$}
+Für das iterierte Spiel muss man wieder den Eigenvektor von $C$ zum
+Eigenwert $1$ finden, die Rechnung mit dem Gauss-Algorithmus liefert
+\[
+p=
+\frac{1}{709}
+\begin{pmatrix}
+245\\180\\84
+\end{pmatrix}.
+\]
+Damit kann man jetzt die Gewinnwahrscheinlichkeit im iterierten Spiel
+berechnen, es ist
+\begin{align*}
+E(Y)
+&=
+U^t
+(G\odot C) p
+\\
+&=
+\begin{pmatrix}
+-\frac{2}{5} & \frac{1}{4} & \frac{1}{4}
+\end{pmatrix}
+\frac{1}{709}
+\begin{pmatrix}
+245\\180\\84
+\end{pmatrix}
+\\
+&=
+\frac{
+-2\cdot 49 + 45 + 71
+}{709}
+=
+\frac{18}{709},
+\end{align*}
+Das iteriert Spiel $B$ ist also ein Gewinnspiel!
+Obwohl die Spiele $A$ und $B$ für sich alleine in der iterierten Form
+keine Gewinnspiele sind, ist das kombinierte Spiel, wo man zufällig
+die beiden Spiel verbindet immer ein Gewinnspiel.
+
+Man kann statt des Spiels $B$ auch das modifizierte Spiel $\tilde{B}$
+verwenden, welches für kleine $\varepsilon>0$ ein Verlustspiel ist.
+Die Analyse lässt sich in der gleichen Weise durchführen und liefert
+wieder, dass für nicht zu grosses $\varepsilon$ das kombinierte Spiel
+ein Gewinnspiel ist.
+
+
+
+
diff --git a/buch/chapters/80-wahrscheinlichkeit/positiv.tex b/buch/chapters/80-wahrscheinlichkeit/positiv.tex
new file mode 100644
index 0000000..9f8f38f
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/positiv.tex
@@ -0,0 +1,721 @@
+%
+% positiv.tex
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\section{Positive Vektoren und Matrizen
+\label{buch:section:positive-vektoren-und-matrizen}}
+\rhead{Positive Vektoren und Matrizen}
+Die Google-Matrix und die Matrizen, die wir in Markov-Ketten angetroffen
+haben, zeichnen sich dadurch aus, dass alle ihre Einträge positiv oder
+mindestens nicht negativ sind.
+Die Perron-Frobenius-Theorie, die in diesem Abschnitt entwickelt
+werden soll, zeigt, dass Positivität einer Matrix nützliche
+Konsequenzen für Eigenwerte und Eigenvektoren hat.
+Das wichtigste Resultat ist die Tatsache, dass postive Matrizen immer
+einen einzigen einfachen Eigenwert mit Betrag $\varrho(A)$ haben,
+was zum Beispiel die Konvergenz des Pagerank-Algorithmus garantiert.
+Dies wird im Satz von Perron-Frobenius in
+Abschnitt~\ref{buch:subsection:der-satz-von-perron-frobenius}
+erklärt.
+
+%
+% Elementare Definitionen und Eigenschaften
+%
+\subsection{Elementare Eigenschaften
+\label{buch:subsection:elementare-eigenschaften}}
+In diesem Abschnitt betrachten wir ausschliesslich reelle Vektoren
+und Matrizen.
+Die Komponenten sind somit immer mit miteinander vergleichbar, daraus
+lässt sich auch eine Vergleichsrelation zwischen Vektoren
+ableiten.
+
+\begin{definition}
+Ein Vektor $v\in\mathbb{R}^n$ heisst {\em positiv}, geschrieben
+$v>0$, wenn alle seine Komponenten positiv sind: $v_i>0\forall i$.
+Ein Vektor $v\in\mathbb{R}^n$ heisst {\em nichtnegativ}, in Formeln
+$v\ge 0$, wenn alle
+seine Komponenten nicht negativ sind: $v_i\ge 0\forall i$.
+\index{positiver Vektor}%
+\index{nichtnegativer Vektor}%
+\end{definition}
+
+Geometrisch kann man sich die Menge der positven Vektoren in zwei Dimensionen
+als die Punkte des ersten Quadranten oder in drei Dimensionen als die
+Vektoren im ersten Oktanten vorstellen.
+
+Aus der Positivität eines Vektors lässt sich jetzt eine Vergleichsrelation
+für beliebige Vektoren ableiten.
+Mit der folgenden Definition wird erreicht, das mit Ungleichungen für Vektoren
+auf die gleiche Art und Weise gerechnet werden kann, wie man sich
+dies von Ungleichungen zwischen Zahlen gewohnt ist.
+
+\begin{definition}
+Für zwei Vektoren $u,v\in\mathbb{R}^n$ ist genau dann $u>v$, wenn
+$u-v > 0$ ist.
+Ebenso ist $u\ge v$ genau dann, wenn $u-v\ge 0$.
+\end{definition}
+
+Ungleichungen zwischen Vektoren kann man daher auch so interpretieren,
+dass sie für jede Komponente einzeln gelten müssen.
+Die Definition funktionieren analog auch für Matrizen:
+
+\begin{definition}
+Eine Matrix $A\in M_{m\times n}(\mathbb{R})$ heisst {\em positiv},
+wenn alle ihre Einträge $a_{ij}$ positiv sind: $a_{ij}>0\forall i,j$.
+Eine Matrix $A\in M_{m\times n}(\mathbb{R})$ heisst {\em nichtnegativ},
+wenn alle ihre Einträge $a_{ij}$ nichtnegativ sind: $a_{ij}\ge 0\forall i,j$.
+\index{positive Matrix}%
+\index{nichtnegative Matrix}%
+Man schreibt $A>B$ bzw.~$A\ge B$ wenn $A-B>0$ bzw.~$A-B\ge 0$.
+\end{definition}
+
+Die Permutationsmatrizen sind Beispiele von nichtnegativen Matrizen,
+deren Produkte wieder nichtnegativ sind.
+Dies ist aber ein sehr spezieller Fall, wie das folgende Beispiel
+zeigt.
+
+\begin{beispiel}
+Wir betrachten die Matrix
+\begin{equation}
+A=
+\begin{pmatrix}
+0.9&0.1& & & & \\
+0.1&0.8&0.1& & & \\
+ &0.1&0.8&0.1& & \\
+ & &0.1&0.8&0.1& \\
+ & & &0.1&0.8&0.1\\
+ & & & &0.1&0.9
+\end{pmatrix}
+\label{buch:wahrscheinlichkeit:eqn:diffusion}
+\end{equation}
+Die Multiplikation eines Vektors mit dieser Matrix bewirkt, dass die
+Komponenten des Vektors auf benachbarte Komponenten ``verschmiert'' werden.
+Wendet man $A$ wiederholt auf den ersten Standardbasisvektor $v_1=e_1$ an,
+erhält man nacheinander die Vektoren $v_2=Av_1$, $v_n = Av_{n-1}$.
+\begin{figure}
+\centering
+\includegraphics{chapters/80-wahrscheinlichkeit/images/diffusion.pdf}
+\caption{Die sechs Komponenten für $k=1$ bis $k=6$ der Vektoren $A^{n-1}e_1$
+für die Matrix $A$ in \eqref{buch:wahrscheinlichkeit:eqn:diffusion}
+sind als Säulen dargestellt.
+Sie zeigen, dass für genügend grosses $n$, alle Komponenten
+des Vektors $A^{n-1}e_1$ positiv werden.
+\label{buch:wahrscheinlichkeit:fig:diffusion}}
+\end{figure}
+In Abbildung~\ref{buch:wahrscheinlichkeit:fig:diffusion} sind die Komponenten
+als Säulen dargestellt.
+Man kann erkennen, dass für genügend grosse $n$ alle Komponenten
+der Vektoren positiv werden.
+
+Man kann auch direkt die Potenzen $A^n$ ausrechen und sehen, dass
+\[
+A^5
+=
+\begin{pmatrix}
+ 0.65658& 0.27690& 0.05925& 0.00685& 0.00041& 0.00001\\
+ 0.27690& 0.43893& 0.22450& 0.05281& 0.00645& 0.00041\\
+ 0.05925& 0.22450& 0.43249& 0.22410& 0.05281& 0.00685\\
+ 0.00685& 0.05281& 0.22410& 0.43249& 0.22450& 0.05925\\
+ 0.00041& 0.00645& 0.05281& 0.22450& 0.43893& 0.27690\\
+ 0.00001& 0.00041& 0.00685& 0.05925& 0.27690& 0.65658
+\end{pmatrix}
+>0
+\]
+und dass daher für alle $n\ge 5$ die Matrix $A^n$ positiv ist.
+\end{beispiel}
+
+Die Eigenschaft der Matrix $A$ von
+\eqref{buch:wahrscheinlichkeit:eqn:diffusion}, dass $A^n>0$
+für genügend grosses $n$ ist bei Permutationsmatrizen nicht
+vorhanden.
+Die Zyklen-Zerlegung einer Permutationsmatrix zeigt, welche
+Unterräume von $\mathbb{R}^n$ die iterierten Bilder eines
+Standardbasisvektors aufspannen.
+Diese sind invariante Unterräume der Matrix.
+Das im Beispiel illustrierte Phänomen findet dann nur in invarianten
+Unterräumen statt.
+
+\begin{beispiel}
+Die Matrix
+\begin{equation}
+A=\begin{pmatrix}
+0.9&0.1& & & & \\
+0.1&0.8&0.1& & & \\
+ &0.1&0.9& & & \\
+ & & &0.9&0.1& \\
+ & & &0.1&0.8&0.1\\
+ & & & &0.1&0.9
+\end{pmatrix}
+\label{buch:wahrscheinlichkeit:eqn:diffusionbloecke}
+\end{equation}
+besteht aus zwei $3\times 3$-Blöcken.
+Die beiden Unterräume $V_1=\langle e_1,e_2,e_3\rangle$
+und $V_2=\langle e_4,e_5,e_6\rangle$ sind daher invariante
+Unterräume von $A$ und damit auch von $A^n$.
+Die Potenzen haben daher auch die gleich Blockstruktur.
+Insbesondere sind zwar die Blöcke von $A^n$ für $n>1$ positive
+Teilmatrizen, aber die Matrix $A^n$ ist für alle $n$ nicht positiv.
+\end{beispiel}
+
+\begin{definition}
+Eine nichtnegative Matrix mit der Eigenschaft, dass $A^n>0$ für
+ein genügend grosses $n$, heisst {\em primitiv}.
+\end{definition}
+
+Die Matrix $A$ von \eqref{buch:wahrscheinlichkeit:eqn:diffusion}
+ist also primitiv, Permutationsmatrizen sind niemals primitiv.
+Die Matrix $A$ von \eqref{buch:wahrscheinlichkeit:eqn:diffusionbloecke}
+ist nicht primitiv, aber die einzelnen Blöcke sind primitiv.
+Viele der Ausssagen über positive Matrizen lassen sich auf primitive
+nichtnegative Matrizen verallgemeinern.
+
+Das Beispiel zeigt auch, dass der Begriff der primitiven Matrix
+eng mit der Idee verknüpft ist, die Problemstellung in invariante
+Unterräume aufzuteilen, in denen eine primitive Matrix vorliegt.
+Primitive Matrizen werden damit zu naheliegenden Bausteinen für
+die Problemlösung für nicht primitive Matrizen.
+
+Eine interessante Eigenschaft positiver Vektoren oder Matrizen
+ist, dass die Positivität sich manchmal ``upgraden'' lässt,
+wie im folgenden Satz.
+Er zeigt, dass ein Vektor, der grösser ist als ein anderer, auch
+um einen definierten Faktor $>1$ grösser ist.
+Dies wird geometrisch in
+Abbildung~\ref{buch:wahrscheinlichkeit:figure:trenn} illustriert.
+
+\begin{figure}
+\centering
+\includegraphics{chapters/80-wahrscheinlichkeit/images/trenn.pdf}
+\caption{Die Vektoren $w\le u$ liegen im grauen Rechteck.
+Zwei nichtnegative Vektoren $u$ und $v$ mit $u>v$
+haben keine gleichen Komponenten.
+Daher kann man $v$ mit einer Zahl $\vartheta=1+\varepsilon > 1$
+strecken, so dass der gestreckte Vektor $(1+\varepsilon)v$ gerade noch
+im grauen Rechteck liegt: $u\ge (1+\varepsilon)v$.
+Streckung mit einem grösseren Faktor führt dagegen aus dem Rechteck
+hinaus.
+\label{buch:wahrscheinlichkeit:figure:trenn}}
+\end{figure}
+
+\begin{satz}[Trenntrick]
+\label{buch:wahrscheinlichkeit:satz:trenntrick}
+Sind $u$ und $v$ nichtnegative Vektoren und $u>v$, dann gibt es eine
+positive Zahl $\varepsilon>0$ derart, dass
+$u\ge (1+\varepsilon)v$.
+Ausserdem kann $\varepsilon$ so gewählt werden, dass $u\not\ge(1+\mu)v$
+für $\mu>\varepsilon$.
+\end{satz}
+
+\begin{proof}[Beweis]
+Wir betrachten die Zahl
+\[
+\vartheta
+=
+\max_{v_i\ne 0} \frac{u_i}{v_i}.
+\]
+Wegen $u>v$ sind die Quotienten auf der rechten Seite alle $>0$.
+Da nur endlich viele Quotienten miteinander verglichen werden, ist
+daher auch $\vartheta >1$.
+Es folgt $u\ge \vartheta v$.
+Wegen $\vartheta >1$ ist $\varepsilon = \vartheta -1 >0$ und
+$u\ge (1+\varepsilon)v$.
+\end{proof}
+
+Der Satz besagt also, dass es eine Komponente $v_i\ne 0$ gibt
+derart, dass $u_i = (1+\varepsilon)v_i$.
+Diese Komponenten limitiert also, wie stark man $v$ strecken kann,
+so dass er immer noch $\le u$ ist.
+Natürlich folgt aus den der Voraussetzung $u>v$ auch, dass $u$ ein
+positiver Vektor ist (Abbildung~\ref{buch:wahrscheinlichkeit:figure:trenn}).
+
+\begin{figure}
+\centering
+\includegraphics{chapters/80-wahrscheinlichkeit/images/vergleich.pdf}
+\caption{Eine positive Matrix $A$ bildet nichtnegative Vektoren in
+positive Vektoren ab
+(Korollar~\ref{buch:wahrscheinlichkeit:satz:Au>0korollar}).
+Zwei verschiedene Vektoren auf einer Seitenfläche erfüllen $u\ge v$,
+aber nicht $u>v$, da sie sich in der Koordinaten $x_2$ nicht unterscheiden.
+Die Bilder unter $A$ unterscheiden sich dann auch in $x_2$, es gilt
+$Au>Av$ (siehe auch Satz~\ref{buch:wahrscheinlichkeit:satz:vergleichstrick})
+\label{buch:wahrscheinlichkeit:fig:vergleich}}
+\end{figure}
+
+\begin{satz}[Vergleichstrick]
+\label{buch:wahrscheinlichkeit:satz:vergleichstrick}
+Sei $A$ eine positive Matrix und seinen $u$ und $v$ Vektoren
+mit $u\ge v$ und $u\ne v$, dann ist $Au > Av$
+(siehe auch Abbildung~\ref{buch:wahrscheinlichkeit:fig:vergleich}).
+\end{satz}
+
+\begin{proof}[Beweis]
+Wir schreiben $d=u-v$, nach Voraussetzung ist $d\ne 0$.
+Der Satz besagt dann, dass aus $d\ge 0$ folgt, dass $Ad>0$, dies
+müssen wir beweisen.
+
+Die Ungleichung $Ad>0$ besagt, dass alle Komponenten von $Ad$
+positiv sind.
+Um dies nachzuweisen, berechnen wir
+\begin{equation}
+(Ad)_i
+=
+\sum_{j=1}^n
+a_{ij}
+d_j.
+\label{buch:wahrscheinlichkeit:eqn:Adpositiv}
+\end{equation}
+Alle Terme $a_{ij}>0$, weil $A$ positiv ist, und mindestens eine
+der Komponenten $d_j>0$, weil $d\ne 0$.
+Insbesondere sind alle Terme der Summe $\ge 0$, woraus wir
+bereits schliessen können, dass $(Ad)_i\ge 0$ sein muss.
+Die Komponente $d_j>0$ liefert einen positiven Beitrag
+$a_{ij}d_j>0$
+zur Summe~\eqref{buch:wahrscheinlichkeit:eqn:Adpositiv},
+also ist $(Ad)_i>0$.
+\end{proof}
+
+Der folgende Spezialfall folgt unmittelbar aus dem
+Satz~\ref{buch:wahrscheinlichkeit:satz:vergleichstrick}.
+
+\begin{korollar}
+\label{buch:wahrscheinlichkeit:satz:Au>0korollar}
+Ist $A$ eine positive Matrix und $u\ge 0$ mit $u\ne 0$, dann
+ist $Au>0$.
+\end{korollar}
+
+Eine positive Matrix macht also aus nicht verschwindenden
+und nicht negativen Vektoren positive Vektoren.
+
+%
+% Die verallgemeinerte Dreiecksungleichung
+%
+\subsection{Die verallgemeinerte Dreiecksungleichung
+\label{buch:subsection:verallgemeinerte-dreiecksungleichung}}
+Die Dreiecksungleichung besagt, dass für beliebige Vektoren
+$u,v\in\mathbb{R}^n$ gilt
+\[
+|u+v|\le |u|+|v|
+\]
+mit Gleichheit genau dann, wenn $u$ und $v$ linear abhängig sind.
+Wenn beide von $0$ verschieden sind, dann gibt es eine positive Zahl
+$t$ mit $u=tv$.
+Wir brauchen eine Verallgemeinerung für eine grössere Zahl von
+Summanden.
+
+\begin{figure}
+\centering
+\includegraphics{chapters/80-wahrscheinlichkeit/images/dreieck.pdf}
+\caption{Die verallgemeinerte Dreiecksungleichung von
+Satz~\ref{buch:wahrscheinlichkeit:satz:verallgemeinerte-dreiecksungleichung}
+besagt, dass
+die Länge einer Summe von Vektoren (blau) höchstens so gross ist wie die
+Summe der Längen, mit Gleichheit genau dann, wenn alle Vektoren die
+gleiche Richtung haben (rot).
+Hier dargestellt am Beispiel von Zahlen in der komplexen Zahlenebene.
+In dieser Form wird die verallgemeinerte Dreiecksungleichung in
+Satz~\ref{buch:wahrscheinlichkeit:satz:verallgdreieckC}
+\label{buch:wahrscheinlichkeit:fig:dreieck}}
+\end{figure}
+
+\begin{satz}[Verallgemeinerte Dreiecksungleichung]
+\label{buch:wahrscheinlichkeit:satz:verallgemeinerte-dreiecksungleichung}
+Für $n$ Vektoren $v_i\ne 0$ gilt
+\[
+|u_1+\dots+u_n| \le |u_1|+\dots+|u_n|
+\]
+mit Gleichheit genau dann, wenn alle Vektoren nichtnegative Vielfache
+eines gemeinsamen Einheitsvektors $c$ sind: $u_i=|u_i|c$
+(siehe auch Abbildung~\ref{buch:wahrscheinlichkeit:fig:dreieck}).
+\end{satz}
+
+\begin{proof}[Beweis]
+Die Aussage kann mit vollständiger Induktion bewiesen werden.
+Die Induktionsverankerung ist der Fall $n=2$ gegeben durch die
+gewöhnliche Dreiecksungleichung.
+
+Wir nehmen daher jetzt an, die Aussage sei für $n$ bereits bewiesen,
+wir müssen sie dann für $n+1$ beweisen.
+Die Summe von $n+1$ Vektoren kann man $u=u_1+\dots+u_n$ und $v=u_{n+1}$
+aufteilen.
+Es gilt dann
+\[
+|u+v|
+=
+|u_1+\dots+u_n+u_{n+1}|
+\]
+und
+\[
+|u_1+\dots+u_n| = |u_1|+\dots+|u_n|.
+\]
+Aus der Induktionsannahme folgt dann, dass die Vektoren $u_1,\dots,u_n$
+positive Vielfache eines Einheitsvektors $u$ sind, $u_i=|u_i|c$.
+Es ist dann
+\[
+u=u_1+\dots+u_n = \biggl(\sum_{i=1}^n |u_i|\biggr).
+\]
+Aus der gewöhnlichen Dreiecksungleichung, angewendet auf $u$ und $v$
+folgt jetzt, dass $v$ ebenfalls ein nichtnegatives Vielfaches von $c$ ist.
+Damit ist der Induktionsschritt vollzogen.
+\end{proof}
+
+\begin{satz}
+\label{buch:wahrscheinlichkeit:satz:verallgdreieckC}
+Seien $a_1,\dots,a_n$ positive Zahlen und $u_i\in\mathbb C$ derart,
+dass
+\[
+\biggl|
+\sum_{i=1}^n a_i u_i
+\biggr|
+=
+\sum_{i=1}^n a_i |u_i|,
+\]
+dann gibt es eine komplexe Zahl $c$ und einen nichtnegativen Vektor $v$
+derart, dass $u=cv$.
+\end{satz}
+
+Der Satz besagt, dass die komplexen Komponenten $u_i$ alle das gleiche
+Argument haben.
+Die motiviert den nachstehenden geometrischen Beweis des Satzes.
+
+\begin{proof}[Beweis]
+Wer stellen uns die komplexen Zahlen $u_i$ als Vektoren in der
+zweidimensionalen Gaussschen Ebene vor.
+Dann ist die Aussage nichts anderes als ein Spezialfall von
+Satz~\ref{buch:wahrscheinlichkeit:satz:verallgemeinerte-dreiecksungleichung}
+für den zweidimensionalen reellen Vektorraum $\mathbb{C}$.
+\end{proof}
+
+
+%
+% Der Satz von Perron-Frobenius
+%
+\subsection{Der Satz von Perron-Frobenius
+\label{buch:subsection:der-satz-von-perron-frobenius}}
+Wir sind an den Eigenwerten und Eigenvektoren einer positiven
+oder primitiven Matrix interessiert.
+Nach Definition des Spektralradius $\varrho(A)$ muss es einen Eigenvektor
+zu einem Eigenwert $\lambda$ mit Betrag $|\lambda|=\varrho(A)$ geben,
+aber a priori wissen wir nicht, ob es einen reellen Eigenwert vom
+Betrag $\varrho(A)$ gibt, und ob der Eigenvektor dazu reell ist.
+
+\begin{figure}
+\centering
+\includegraphics{chapters/80-wahrscheinlichkeit/images/positiv.pdf}
+\caption{Die Iteration einer positiven Matrix bildet den positiven Oktanten
+in immer enger werdende Kegel ab, die die Richtung des gesuchten Eigenvektors
+gemeinsam haben.
+\label{buch:wahrscheinlichkeit:figure:positiv}}
+\end{figure}
+
+In Abbildung~\ref{buch:wahrscheinlichkeit:fig:vergleich} kann man sehen,
+dass eine positive Abbildung den positiven Oktanten in einen etwas engeren
+Kegel hinein abbildet.
+Iteriert man dies (Abbildung~\ref{buch:wahrscheinlichkeit:figure:positiv}),
+wird die Bildmenge immer enger, bis sie nur ein
+sehr enger Kegel um die Richtung des Eigenvektors ist.
+Tatsächlich kann man aus dieser Idee auch einen topologischen
+Beweis des untenstehenden Satzes von Perron-Frobenius konstruieren.
+Er beruht darauf, dass eine Abbildung, die Distanzen verkleinert,
+einen Fixpunkt hat.
+Die Konstruktion einer geeigneten Metrik ist allerdings eher
+kompliziert, weshalb wir im Beweise der nachstehenden Aussagen
+den konventionellen Weg wählen.
+
+Wir beginnen damit zu zeigen, dass für positive Matrizen $A$,
+nichtnegative Eigenvektoren zu Eigenwerten $\lambda\ne 0$
+automatisch positiv sind.
+Ausserdem müssen die zugehörigen Eigenwerte sogar positiv sein.
+
+\begin{satz}
+Sei $A$ eine positive Matrix und $u$ ein nichtnegativer Eigenvektor zum
+Eigenwert $\lambda\ne 0$.
+Dann ist $u$ ein positiver Vektor und $\lambda > 0$.
+\end{satz}
+
+\begin{proof}[Beweis]
+Nach dem Korollar~\ref{buch:wahrscheinlichkeit:satz:Au>0korollar}
+folgt, dass $Au>0$ ein positiver Vektor ist, es sind
+also alle Komponenten positiv.
+Der Vektor $u$ ist aber auch ein Eigenvektor, es gilt also
+$\lambda u = Au$.
+Da alle Komponenten von $Au$ positiv sind, müssen auch
+alle Komponenten von $\lambda u$ positiv sein.
+Das ist nur möglich, wenn $\lambda > 0$.
+\end{proof}
+
+\begin{satz}
+\label{buch:wahrscheinlichkeit:satz:positivereigenvektor}
+Sei $A$ eine positive Matrix und $v$ ein Eigenvektor von $A$ zu einem
+Eigenwert $\lambda$ mit Betrag $|\lambda|=\varrho(A)$,
+dann ist der Vektor $u$ mit den Komponenten $u_i=|v_i|$ ein
+positiver Eigenvektor zu Eigenwert $\varrho(A)$.
+\end{satz}
+
+\begin{proof}[Beweis]
+Es gilt natürlich auch, dass
+\[
+(Au)_i
+=
+\sum_{j=1}^n a_{ij}u_j
+=
+\sum_{j=1}^n |a_{ij}v_j|
+\ge
+\biggl|
+\sum_{j=1}^n a_{ij}v_j
+\biggr|
+=
+|(Av)_i|
+=
+|\lambda v_i|
+=
+\varrho(A) |v_i|
+=
+\varrho(A) u_i,
+\]
+oder $Au \ge \varrho(A)u$.
+Wir müssen zeigen, dass sogar $Au=\varrho(A)u$ gilt.
+Wir nehmen daher an, dass $Au\ne \varrho(A)u$ ist, und führen dies zu
+einem Widerspruch.
+
+Da $\varrho(A)u$ ein nichtnegativer Vektor ist, können wir den Vergleichstrick
+Satz~\ref{buch:wahrscheinlichkeit:satz:vergleichstrick}, auf die beiden
+Vektoren $Au$ und $\varrho(A)u$ anwenden.
+Wir schliessen $A^2u > \varrho(A)Au$.
+
+Mit dem Trenntrick
+Satz~\ref{buch:wahrscheinlichkeit:satz:trenntrick}
+können wir jetzt eine Zahl $\vartheta>1$ finden derart, dass
+\[
+A^2 u \ge \vartheta \varrho(A) Au
+\]
+ist.
+Durch weitere Anwendung von $A$ findet man
+\begin{align*}
+A^3 u & \ge (\vartheta \varrho(A))^2 Au
+\\
+&\phantom{0}\vdots
+\\
+A^{k+1} u & \ge (\vartheta \varrho(A))^{k} Au
+\end{align*}
+Daraus kann man jetzt die Norm abschätzen:
+\[
+\begin{aligned}
+\| A^{k}\|\, |Au|
+&\ge
+\| A^{k+1}u\|
+\ge
+(\vartheta\varrho(A))^{k} |Au|
+&&
+\Rightarrow
+&
+\|A^k\| &\ge (\vartheta\varrho(A))^k
+\\
+&&&\Rightarrow&
+\|A^k\|^{\frac{1}{k}} &\ge \vartheta\varrho(A)
+\\
+&&&\Rightarrow&
+\lim_{k\to\infty}
+\|A^k\|^{\frac{1}{k}} &\ge \vartheta\varrho(A)
+\\
+&&&\Rightarrow&
+\varrho(A)&\ge \vartheta\varrho(A)
+\end{aligned}
+\]
+Wegen $\vartheta>1$ ist dies aber gar nicht möglich.
+Dieser Widerspruch zeigt, dass $u=v$ sein muss, insbesondere ist
+$v$ ein nichtnegativer Eigenvektor.
+\end{proof}
+
+\begin{satz}
+Sei $A$ eine positive Matrix und $v$ ein Eigenvektor zu einem
+Eigenwert $\lambda$ mit Betrag $|\lambda|=\varrho(A)$.
+Dann ist $\lambda=\varrho(A)$.
+\end{satz}
+
+\begin{proof}[Beweis]
+Nach Satz~\ref{buch:wahrscheinlichkeit:satz:positivereigenvektor}
+ist der Vektor $u$ mit den Komponenten $u_i=|v_i|$ ein positiver
+Eigenvektor zum Eigenwert $\varrho(A)$.
+Aus der Eigenvektorgleichung für $u$ folgt
+\begin{equation}
+Au = \varrho(A) u
+\quad\Rightarrow\quad
+\sum_{j=1}^n a_{ij}|v_j| = \varrho(A) |v_i|.
+\label{buch:wahrscheinlichkeit:eqn:pev1}
+\end{equation}
+Anderseits ist $v$ ein Eigenvektor zum Eigenwert $\lambda$, also gilt
+\[
+\sum_{j=1}^n a_{ij}v_j = \lambda v_i.
+\]
+Der Betrag davon ist
+\begin{equation}
+\biggl|
+\sum_{j=1}^n a_{ij}v_j
+\biggr|
+=
+|\lambda v_i|
+=
+\varrho(A) |v_i|
+=
+\varrho |v_i|.
+\label{buch:wahrscheinlichkeit:eqn:pev2}
+\end{equation}
+Die beiden Gleichungen
+\eqref{buch:wahrscheinlichkeit:eqn:pev1}
+und
+\eqref{buch:wahrscheinlichkeit:eqn:pev2}
+zusammen ergeben die Gleichung
+\[
+\biggl|
+\sum_{j=1}^n a_{ij}v_j
+\biggr|
+=
+\sum_{j=1}^n a_{ij}|v_j|.
+\]
+Nach der verallgemeinerten Dreiecksungleichung
+Satz~\ref{buch:subsection:verallgemeinerte-dreiecksungleichung}
+folgt jetzt, dass es eine komplexe Zahl $c$ vom Betrag $1$ gibt derart,
+dass $v_j = |v_j|c=u_jc$.
+Insbesondere ist $v=cu$ und damit ist
+\[
+\lambda v = Av = Acu = c Au = c\varrho(A) u = \varrho(A) v,
+\]
+woraus $\lambda=\varrho(A)$ folgt.
+\end{proof}
+
+\begin{satz}
+\label{buch:wahrscheinlichkeit:satz:geometrischeinfach}
+Der Eigenraum einer positiven Matrix $A$ zum Eigenwert $\varrho(A)$ ist
+eindimensional.
+\end{satz}
+
+\begin{proof}[Beweis]
+Sei $u$ der bereits gefundene Eigenvektor von $A$ zum Eigenwert $\varrho(A)$
+und sei $v$ ein weiterer, linear unabhängiger Eigenvektor zum
+gleichen Eigenwert.
+Da $A$ und $\varrho(A)$ reell sind, sind auch die Vektoren $\Re v$ und $\Im v$
+aus den Realteilen $\Re v_i$ oder den Imaginärteilen $\Im v_i$ Eigenvektoren.
+Beide Vektoren sind reelle Vektoren und mindestens einer davon ist mit
+$u$ linear unabhängig.
+Wir dürfen daher annehmen, dass $v$ ein linear unabhängiger Eigenvektor
+zum Eigenwert $\varrho(A)$ ist.
+
+Weil wir wissen, dass $u$ ein positiver Vektor ist, gibt es einen
+grösstmöglichen Faktor $c>0$ derart, dass $u\ge cv$ oder $u\ge cv$.
+Insbesondere verschwindet mindestens eine Komponente von $u-cv$.
+Da $u$ und $v$ Eigenvektoren zum Eigenwert $\varrho(A)$ sind,
+ist
+\[
+A(u-cv)
+=
+\varrho(A)(u-cv).
+\]
+Der Vektor auf der rechten Seite hat mindestens eine verschwindende
+Komponente.
+Der Vektor auf der linken Seite ist nach Vergleichstrick
+Satz~\ref{buch:wahrscheinlichkeit:satz:vergleichstrick}
+\[
+A(u-cv) > 0,
+\]
+alle seine Komponenten sind $>0$.
+Dieser Widerspruch zeigt, dass die Annahme, es gäbe einen von $u$ linear
+unabhängigen Eigenvektor zum Eigenwert $\varrho(A)$ nicht haltbar ist.
+\end{proof}
+
+\begin{satz}
+\label{buch:wahrscheinlichkeit:satz:algebraischeinfach}
+Der verallgemeinerte Eigenraum zum Eigenwert $\varrho(A)$ einer
+positiven Matrix $A$ ist eindimensional.
+Ist $u$ der Eigenvektor von $A$ zum Eigenwert $\varrho(A)$ nach
+Satz~\ref{buch:wahrscheinlichkeit:satz:geometrischeinfach}
+und $p^t$ der entsprechende Eigenvektor $A^t$, dann
+ist
+\[
+\mathbb{R}^n
+=
+\langle u\rangle
+\oplus
+\{ x\in\mathbb{R}^n\;|\; px=0\}
+=
+\langle u\rangle
+\oplus
+\ker p
+\]
+eine Zerlegung in invariante Unterräume von $A$.
+\end{satz}
+
+\begin{proof}[Beweis]
+Die beiden Vektoren $x$ und $p$ sind beide positiv, daher ist das
+Produkt $pu\ne 0$.
+Insbesondere ist $u\not\in\ker p$
+
+Es ist klar, dass $A\langle u\rangle = \langle Au\rangle = \langle u\rangle$
+ein invarianter Unterraum ist.
+Für einen Vektor $x\in\mathbb{R}^n$ mit $px=0$ erfüllt das Bild $Ax$
+\[
+p(Ax)=(pA)x=(A^tp^t)^tx=
+\varrho(A)(p^t)^tx
+=
+\varrho(A)px = 0,
+\]
+somit ist $A\ker p \subset \ker p$.
+Beide Räume sind also invariante Unteräume.
+
+$\ker p$ ist $(n-1)$-dimensional, $\langle u\rangle$ ist eindimensional
+und $u$ ist nicht in $\ker p$ enthalten.
+Folglich spannen $\langle u\rangle$ und $\ker p$ den ganzen Raum auf.
+
+Gäbe es einen weitern linear unabhängigen Vektor im verallgemeinerten
+Eigenraum von $\mathcal{E}_{\varrho(A)}$, dann müsste es auch einen
+solchen Vektor in $\ker p$ geben.
+Da $\ker p$ invariant ist, müsste es also auch einen weiteren Eigenvektor
+$u_2$ zum Eigenwert $\varrho(A)$ in $\ker p$ geben.
+Die beiden Vektoren $u$ und $u_1$ sind dann beide Eigenvektoren, was
+nach Satz~\ref{buch:wahrscheinlichkeit:satz:geometrischeinfach}
+nicht möglich ist.
+\end{proof}
+
+Die in den Sätzen
+\ref{buch:wahrscheinlichkeit:satz:positivereigenvektor}
+bis
+\ref{buch:wahrscheinlichkeit:satz:algebraischeinfach}
+gefundenen Resultate können wir folgt zusammengefasst werden:
+
+\begin{satz}[Perron-Frobenius]
+\label{buch:wahrscheinlichkeit:satz:perron-frobenius}
+Sei $A$ eine positive Matrix mit Spektralradius $\varrho(A)$.
+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.
+
+\begin{satz}
+\label{buch:wahrscheinlichkeit:satz:perron-frobenius2}
+Sei $A$ ein primitive, nichtnegative Matrix.
+Dann ist $\varrho(A)$ der einzige Eigenwert vom Betrag $\varrho(A)$
+und er hat geometrische und algebraische Vielfachheit $1$.
+\end{satz}
+
+\begin{proof}[Beweis]
+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}
diff --git a/buch/chapters/80-wahrscheinlichkeit/rechnungen/btilde.maxima b/buch/chapters/80-wahrscheinlichkeit/rechnungen/btilde.maxima
new file mode 100644
index 0000000..6ba2ee6
--- /dev/null
+++ b/buch/chapters/80-wahrscheinlichkeit/rechnungen/btilde.maxima
@@ -0,0 +1,103 @@
+B: matrix(
+ [ 0 , 1/4, 3/4 ],
+ [ 1/10, 0 , 1/4 ],
+ [ 9/10, 3/4, 0 ]
+);
+F: matrix(
+ [ 0, -1, 1 ],
+ [ 1, 0, -1 ],
+ [ -1, 1, 0 ]
+);
+G: matrix(
+ [ 0, -1, 1 ],
+ [ 1, 0, -1 ],
+ [ -1, 1, 0 ]
+);
+U: matrix([1], [1], [1]);
+p: (1/3) * U;
+
+ratsimp(expand((B * G) . p));
+ratsimp(expand(transpose(U) . (B * G) . p));
+
+/* find the eigenvector */
+/* find the eigenvector */
+B0: B - identfor(B);
+
+r: expand(B0[1] / B0[1,1]);
+B0[1]: r;
+B0[2]: B0[2] - B0[2,1] * r;
+B0[3]: B0[3] - B0[3,1] * r;
+
+B0: expand(B0);
+
+r: B0[2] / B0[2,2];
+B0[2]: r;
+B0[3]: B0[3] - B0[3,2] * r;
+
+B0: ratsimp(expand(B0));
+
+B0[1]: B0[1] - B0[1,2] * B0[2];
+
+B0: ratsimp(expand(B0));
+
+l: 78 + 12 * epsilon + 80 * epsilon^2;
+
+D: ratsimp(expand(l*B0));
+n: ratsimp(expand(l -D[1,3] -D[2,3]));
+
+p: (1/n) * matrix(
+[ -B0[1,3]*l ],
+[ -B0[2,3]*l ],
+[ l ]
+);
+p: ratsimp(expand(p));
+
+/* compute the expected gain */
+G*B;
+ratsimp(expand(transpose(U). (G*B) . p));
+
+/* modified game */
+Btilde: B - epsilon * F;
+ratsimp(expand((Btilde * G) . p));
+gain: ratsimp(expand(transpose(U) . (Btilde * G) . p));
+
+/* find the eigenvector */
+B0: Btilde - identfor(Btilde);
+
+r: expand(B0[1] / B0[1,1]);
+B0[1]: r;
+B0[2]: B0[2] - B0[2,1] * r;
+B0[3]: B0[3] - B0[3,1] * r;
+
+B0: expand(B0);
+
+r: B0[2] / B0[2,2];
+B0[2]: r;
+B0[3]: B0[3] - B0[3,2] * r;
+
+B0: ratsimp(expand(B0));
+
+B0[1]: B0[1] - B0[1,2] * B0[2];
+
+B0: ratsimp(expand(B0));
+
+l: 78 + 12 * epsilon + 80 * epsilon^2;
+
+D: ratsimp(expand(l*B0));
+n: ratsimp(expand(l -D[1,3] -D[2,3]));
+
+pepsilon: (1/n) * matrix(
+[ -B0[1,3]*l ],
+[ -B0[2,3]*l ],
+[ l ]
+);
+pepsilon: ratsimp(expand(pepsilon));
+
+/* taylor series expansion of the eigenvector */
+taylor(pepsilon, epsilon, 0, 3);
+
+/* expectation */
+
+G*Btilde;
+gainepsilon: ratsimp(expand(transpose(U). (G*Btilde) . pepsilon));
+taylor(gainepsilon, epsilon, 0, 5);