diff options
Diffstat (limited to '')
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 Binary files differnew file mode 100644 index 0000000..b79b07b --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.jpg 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 Binary files differnew file mode 100644 index 0000000..ac4c0ff --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.pdf diff --git a/buch/chapters/80-wahrscheinlichkeit/images/diffusion.png b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.png Binary files differnew file mode 100644 index 0000000..f4c6294 --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.png 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 Binary files differnew file mode 100644 index 0000000..0cca2e1 --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/dreieck.pdf 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 Binary files differnew file mode 100644 index 0000000..12eaf1e --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/internet.pdf 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 Binary files differnew file mode 100644 index 0000000..f77cc62 --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/konvex.pdf diff --git a/buch/chapters/80-wahrscheinlichkeit/images/konvex.tex b/buch/chapters/80-wahrscheinlichkeit/images/konvex.tex new file mode 100644 index 0000000..05bbc60 --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/konvex.tex @@ -0,0 +1,75 @@ +% +% konvex.tex -- template for standalon tikz images +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usetikzlibrary{arrows,intersections,math,calc,hobby} +\begin{document} +\def\skala{1} +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\def\punkt#1{ + \fill[color=white] #1 circle[radius=0.05]; + \draw #1 circle[radius=0.05]; +} + +\begin{scope}[xshift=-3cm] +\coordinate (O) at (0,0); +\coordinate (A) at (-1,5); +\coordinate (B) at (3,2); +\draw[->] (O) -- (A); +\draw[->] (O) -- (B); +\begin{scope} +\clip (-2,0) rectangle (4,6); +\draw[color=red!40,line width=0.4pt] ($2*(B)-(A)$) -- ($2*(A)-(B)$); +\end{scope} +\draw[color=red,line width=1.5pt] (A) -- (B); +\punkt{(O)} +\punkt{(A)} +\punkt{(B)} +\node at (O) [below left] {$O$}; +\node at (A) [above right] {$A$}; +\node at (B) [above right] {$B$}; +\node at ($0.5*(A)$) [left] {$\vec{a}$}; +\node at ($0.5*(B)$) [below right] {$\vec{b}$}; +\fill[color=white] ($0.6*(A)+0.4*(B)$) circle[radius=0.05]; +\draw[color=red] ($0.6*(A)+0.4*(B)$) circle[radius=0.05]; +\node[color=red] at ($0.6*(A)+0.4*(B)$) [above right] {$t\vec{a}+(1-t)\vec{b}$}; +\end{scope} + +\begin{scope}[xshift=4cm] +\coordinate (O) at (0,0); +\coordinate (A) at (-1,3); +\coordinate (B) at (2,5); +\coordinate (C) at (4,1); +\draw[->] (O) -- (A); +\draw[->] (O) -- (B); +\draw[->] (O) -- (C); +\fill[color=red!50,opacity=0.5] (A) -- (B) -- (C) -- cycle; +\draw[color=red,line width=1.5pt,opacity=0.7] (A) -- (B) -- (C) -- cycle; +\punkt{(O)} +\punkt{(A)} +\punkt{(B)} +\punkt{(C)} +\node at (O) [below left] {$O$}; +\node at (A) [left] {$P_1$}; +\node at (B) [above] {$P_2$}; +\node at (C) [right] {$P_3$}; +\node at ($0.5*(A)$) [left] {$\vec{p}_1$}; +\node at ($0.3*(B)$) [right] {$\vec{p}_2$}; +\node at ($0.5*(C)$) [below] {$\vec{p}_3$}; +\fill[color=white] ($0.5*(C)+0.3*(A)+0.2*(B)$) circle[radius=0.05]; +\draw[color=red] ($0.5*(C)+0.3*(A)+0.2*(B)$) circle[radius=0.05]; +\node[color=red] at ($0.5*(C)+0.3*(A)+0.2*(B)$) [above] {$\displaystyle\sum_{t=1}^3 t_i\vec{p}_i$}; +\end{scope} + + +\end{tikzpicture} +\end{document} + diff --git a/buch/chapters/80-wahrscheinlichkeit/images/markov.pdf b/buch/chapters/80-wahrscheinlichkeit/images/markov.pdf Binary files differnew file mode 100644 index 0000000..fba9489 --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/markov.pdf 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 Binary files differnew file mode 100644 index 0000000..d534c8f --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/markov2.pdf 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 Binary files differnew file mode 100644 index 0000000..61f4fe7 --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/markov3.pdf 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 Binary files differnew file mode 100644 index 0000000..53544cb --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/positiv.jpg 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 Binary files differnew file mode 100644 index 0000000..39aa3cd --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/positiv.pdf diff --git a/buch/chapters/80-wahrscheinlichkeit/images/positiv.png b/buch/chapters/80-wahrscheinlichkeit/images/positiv.png Binary files differnew file mode 100644 index 0000000..a2bd9bf --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/positiv.png 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 Binary files differnew file mode 100644 index 0000000..466974d --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/spielB.pdf 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 Binary files differnew file mode 100644 index 0000000..7812c9c --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/spielBtilde.pdf 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 Binary files differnew file mode 100644 index 0000000..f4fa58f --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/trenn.pdf 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 Binary files differnew file mode 100644 index 0000000..3274f42 --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.jpg diff --git a/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf Binary files differnew file mode 100644 index 0000000..b7215b4 --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf diff --git a/buch/chapters/80-wahrscheinlichkeit/images/vergleich.png b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.png Binary files differnew file mode 100644 index 0000000..f20bd48 --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.png 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); |
