From 7c87c2a7f34086001e0274bf804ae47b220f832a Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Mon, 25 Jan 2021 21:28:42 +0100 Subject: Perron-Frobenius Theorie --- buch/chapters/80-wahrscheinlichkeit/Makefile.inc | 1 + buch/chapters/80-wahrscheinlichkeit/chapter.tex | 1 + .../chapters/80-wahrscheinlichkeit/images/Makefile | 19 + .../80-wahrscheinlichkeit/images/diffusion.jpg | Bin 0 -> 203856 bytes .../80-wahrscheinlichkeit/images/diffusion.m | 33 ++ .../80-wahrscheinlichkeit/images/diffusion.pdf | Bin 0 -> 220008 bytes .../80-wahrscheinlichkeit/images/diffusion.tex | 46 ++ buch/chapters/80-wahrscheinlichkeit/positiv.tex | 617 +++++++++++++++++++++ 8 files changed, 717 insertions(+) create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/Makefile create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/diffusion.jpg create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/diffusion.m create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/diffusion.pdf create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/diffusion.tex create mode 100644 buch/chapters/80-wahrscheinlichkeit/positiv.tex (limited to 'buch/chapters/80-wahrscheinlichkeit') 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/images/Makefile b/buch/chapters/80-wahrscheinlichkeit/images/Makefile new file mode 100644 index 0000000..3c6a7f9 --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/Makefile @@ -0,0 +1,19 @@ +# +# Makefile +# +# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschulen +# +all: diffusion.png diffusion.pdf + +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 + diff --git a/buch/chapters/80-wahrscheinlichkeit/images/diffusion.jpg b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.jpg new file mode 100644 index 0000000..b79b07b Binary files /dev/null and b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.jpg differ diff --git a/buch/chapters/80-wahrscheinlichkeit/images/diffusion.m b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.m new file mode 100644 index 0000000..ad56fe5 --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.m @@ -0,0 +1,33 @@ +# +# diffusion.m +# +# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +# +e1 = [ 1; 0; 0; 0; 0; 0 ]; +A = 0.8*eye(6) + 0.1*shift(eye(6),1) + 0.1*shift(eye(6),-1); +A(1,1) = 0.9; +A(6,6) = 0.9; +A(1,6) = 0; +A(6,1) = 0; + +N = 30; +b = zeros(6,N); +b(:,1) = e1; +for i = (2:N) + b(:,i) = A * b(:,i-1); +end +b + +f = fopen("vektoren.inc", "w"); +for i = (1:N) + fprintf(f, "vektor(%d,%.4f,%.4f,%.4f,%.4f,%.4f,%.4f)\n", i, + b(1,i), b(2,i), b(3,i), b(4,i), b(5,i), b(6,i)) +end +fclose(f); + +A1=A +A2=A*A +A3=A*A2 +A4=A*A3 +A5=A*A4 +A6=A*A5 diff --git a/buch/chapters/80-wahrscheinlichkeit/images/diffusion.pdf b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.pdf new file mode 100644 index 0000000..ac4c0ff Binary files /dev/null and b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.pdf differ 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/positiv.tex b/buch/chapters/80-wahrscheinlichkeit/positiv.tex new file mode 100644 index 0000000..f956374 --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/positiv.tex @@ -0,0 +1,617 @@ +% +% 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} + +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. + +\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. + +\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$. +\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{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$. +\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} +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. + +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$ ein 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] +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} + + -- cgit v1.2.1 From a503cc5c7fcbb125ec7c220845b9e760248db233 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Tue, 26 Jan 2021 13:11:37 +0100 Subject: =?UTF-8?q?Visualisierungen=20f=C3=BCr=20Perron-Frobenius-Theorie?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- .../chapters/80-wahrscheinlichkeit/images/Makefile | 35 +++- .../80-wahrscheinlichkeit/images/diffusion.png | Bin 0 -> 265323 bytes .../80-wahrscheinlichkeit/images/diffusion.pov | 87 +++++++++ .../80-wahrscheinlichkeit/images/dreieck.m | 41 +++++ .../80-wahrscheinlichkeit/images/dreieck.pdf | Bin 0 -> 23945 bytes .../80-wahrscheinlichkeit/images/dreieck.tex | 90 +++++++++ .../80-wahrscheinlichkeit/images/positiv.jpg | Bin 0 -> 111361 bytes .../80-wahrscheinlichkeit/images/positiv.m | 36 ++++ .../80-wahrscheinlichkeit/images/positiv.png | Bin 0 -> 191808 bytes .../80-wahrscheinlichkeit/images/positiv.pov | 137 ++++++++++++++ .../80-wahrscheinlichkeit/images/trenn.pdf | Bin 0 -> 13272 bytes .../80-wahrscheinlichkeit/images/trenn.tex | 44 +++++ .../80-wahrscheinlichkeit/images/vergleich.jpg | Bin 0 -> 105809 bytes .../80-wahrscheinlichkeit/images/vergleich.pdf | Bin 0 -> 120558 bytes .../80-wahrscheinlichkeit/images/vergleich.png | Bin 0 -> 223136 bytes .../80-wahrscheinlichkeit/images/vergleich.pov | 203 +++++++++++++++++++++ .../80-wahrscheinlichkeit/images/vergleich.tex | 46 +++++ buch/chapters/80-wahrscheinlichkeit/positiv.tex | 74 +++++++- 18 files changed, 788 insertions(+), 5 deletions(-) create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/diffusion.png create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/diffusion.pov create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/dreieck.m create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/dreieck.pdf create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/dreieck.tex create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/positiv.jpg create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/positiv.m create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/positiv.png create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/positiv.pov create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/trenn.pdf create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/trenn.tex create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/vergleich.jpg create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/vergleich.png create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/vergleich.pov create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/vergleich.tex (limited to 'buch/chapters/80-wahrscheinlichkeit') diff --git a/buch/chapters/80-wahrscheinlichkeit/images/Makefile b/buch/chapters/80-wahrscheinlichkeit/images/Makefile index 3c6a7f9..5511f14 100644 --- a/buch/chapters/80-wahrscheinlichkeit/images/Makefile +++ b/buch/chapters/80-wahrscheinlichkeit/images/Makefile @@ -3,8 +3,10 @@ # # (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschulen # -all: diffusion.png diffusion.pdf +all: dreieck.pdf trenn.pdf vergleich.pdf vergleich.jpg positiv.jpg \ + diffusion.png diffusion.pdf +# Visualisierung diffusion in einer primitiven Matrix diffusion.pdf: diffusion.tex diffusion.jpg pdflatex diffusion.tex @@ -17,3 +19,34 @@ diffusion.jpg: diffusion.png vektoren.inc: diffusion.m octave diffusion.m +# Visualizierung positive Matrix +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 diff --git a/buch/chapters/80-wahrscheinlichkeit/images/diffusion.png b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.png new file mode 100644 index 0000000..f4c6294 Binary files /dev/null and b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.png differ diff --git a/buch/chapters/80-wahrscheinlichkeit/images/diffusion.pov b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.pov new file mode 100644 index 0000000..9b385da --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.pov @@ -0,0 +1,87 @@ +// +// diffusion.pov +// +// (c) 2021 Prof Dr Andreas Müller, OST Ostscheizer Fachhochschule +// +#version 3.7; +#include "colors.inc" + +global_settings { + assumed_gamma 1 +} + +#declare imagescale = 0.270; +#declare N = 30; +#declare vscale = 10; +#declare r = 0.08; + +camera { + location <43, 20, -50> + look_at + 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 { , } +#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 { , , r } + #declare xx = xx + 1; +#end +#declare yy = 0; +#while (yy <= 6) + cylinder { <1, 0, yy>, , r } + #declare yy = yy + 1; +#end + sphere { <1,0,0>, r } + sphere { <1,0,6>, r } + sphere { , r } + sphere { , 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/dreieck.m b/buch/chapters/80-wahrscheinlichkeit/images/dreieck.m new file mode 100644 index 0000000..cc9661b --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/dreieck.m @@ -0,0 +1,41 @@ +# +# dreieck.m +# +# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +# +w = 12 +N = 10 + +rand("seed", 1); + +angles = 80 * rand(1,N) +radii = 2 * rand(1,N) + 0.4 +angle = 20 + +radii = radii * w / (cosd(angle) * sum(radii)) +radius = sum(radii) +radius * cosd(angle) + +points = zeros(2,N); +ray = zeros(2,N); + +p = [ 0; 0 ]; +for i = (1:N) + p = p + radii(1,i) * [ cosd(angles(1,i)); sind(angles(1,i)) ]; + points(:, i) = p; + ray(:, i) = sum(radii(1,1:i)) * [ cosd(angle); sind(angle) ]; +end + +points + +ray + +fn = fopen("drei.inc", "w"); +for i = (1:N) + fprintf(fn, "\\coordinate (A%d) at (%.4f,%.4f);\n", i, + points(1,i), points(2,i)); + fprintf(fn, "\\coordinate (B%d) at (%.4f,%.4f);\n", i, + ray(1,i), ray(2,i)); +end +fprintf(fn, "\\def\\r{%.4f}\n", radius); +fclose(fn); diff --git a/buch/chapters/80-wahrscheinlichkeit/images/dreieck.pdf b/buch/chapters/80-wahrscheinlichkeit/images/dreieck.pdf new file mode 100644 index 0000000..0cca2e1 Binary files /dev/null and b/buch/chapters/80-wahrscheinlichkeit/images/dreieck.pdf differ diff --git a/buch/chapters/80-wahrscheinlichkeit/images/dreieck.tex b/buch/chapters/80-wahrscheinlichkeit/images/dreieck.tex new file mode 100644 index 0000000..0935992 --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/dreieck.tex @@ -0,0 +1,90 @@ +% +% dreieck.tex -- verallgemeinerte Dreiecksungleichung +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usepackage{pgf} +\usetikzlibrary{arrows,intersections,math,calc,hobby} +\begin{document} +\def\skala{1} +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\coordinate (O) at (0,0); + +\input{drei.inc} + +\begin{scope} +\clip (O) rectangle (12.3,8); +\draw[color=red!40] (O) circle[radius=\r]; +\end{scope} + +\draw[->] (-0.1,0) -- (12.3,0) coordinate[label={$\Re z$}]; +\draw[->] (0,-0.1) -- (0,8.3) coordinate[label={right:$\Im z$}]; + +\fill[color=blue] (A1) circle[radius=0.05]; +\fill[color=blue] (A2) circle[radius=0.05]; +\fill[color=blue] (A3) circle[radius=0.05]; +\fill[color=blue] (A4) circle[radius=0.05]; +\fill[color=blue] (A5) circle[radius=0.05]; +\fill[color=blue] (A6) circle[radius=0.05]; +\fill[color=blue] (A7) circle[radius=0.05]; +\fill[color=blue] (A8) circle[radius=0.05]; +\fill[color=blue] (A9) circle[radius=0.05]; +\fill[color=blue] (A10) circle[radius=0.05]; +\draw[color=blue] (O) -- (A1); +\draw[color=blue] (A1) -- (A2); +\draw[color=blue] (A2) -- (A3); +\draw[color=blue] (A3) -- (A4); +\draw[color=blue] (A4) -- (A5); +\draw[color=blue] (A5) -- (A6); +\draw[color=blue] (A6) -- (A7); +\draw[color=blue] (A7) -- (A8); +\draw[color=blue] (A8) -- (A9); +\draw[color=blue] (A9) -- (A10); +\draw[->,color=blue!40] (O) -- (A10); +\node[color=blue] at ($0.5*(A1)$) [left] {$z_1$}; +\node[color=blue] at ($0.5*(A1)+0.5*(A2)$) [left] {$z_2$}; +\node[color=blue] at ($0.5*(A2)+0.5*(A3)$) [above] {$z_3$}; +\node[color=blue] at ($0.5*(A3)+0.5*(A4)$) [above] {$z_4$}; +\node[color=blue] at ($0.5*(A4)+0.5*(A5)$) [below right] {$z_5$}; +\node[color=blue] at ($0.5*(A5)+0.5*(A6)$) [left] {$z_6$}; +\node[color=blue] at ($0.5*(A6)+0.5*(A7)$) [left] {$z_7$}; +\node[color=blue] at ($0.5*(A7)+0.5*(A8)$) [above] {$z_8$}; +\node[color=blue] at ($0.5*(A8)+0.5*(A9)$) [left] {$z_9$}; +\node[color=blue] at ($0.5*(A9)+0.5*(A10)$) [above] {$z_{10}$}; +\node[color=blue] at ($0.8*(A10)$) [rotate=35,below] {$\displaystyle\sum_{i=1}^n z_i$}; + +\draw[->,color=red] (O) -- (B10); +\fill[color=red] (B1) circle[radius=0.05]; +\fill[color=red] (B2) circle[radius=0.05]; +\fill[color=red] (B3) circle[radius=0.05]; +\fill[color=red] (B4) circle[radius=0.05]; +\fill[color=red] (B5) circle[radius=0.05]; +\fill[color=red] (B6) circle[radius=0.05]; +\fill[color=red] (B7) circle[radius=0.05]; +\fill[color=red] (B8) circle[radius=0.05]; +\fill[color=red] (B9) circle[radius=0.05]; +\fill[color=red] (B10) circle[radius=0.05]; + +\node[color=red] at ($0.5*(B1)$) [above] {$|z_1|c$}; +\node[color=red] at ($0.5*(B1)+0.5*(B2)$) [above] {$|z_2|c$}; +\node[color=red] at ($0.5*(B2)+0.5*(B3)$) [above] {$|z_3|c$}; +\node[color=red] at ($0.5*(B3)+0.5*(B4)$) [above] {$|z_4|c$}; +\node[color=red] at ($0.5*(B4)+0.5*(B5)$) [above] {$|z_5|c$}; +\node[color=red] at ($0.5*(B5)+0.5*(B6)$) [above] {$|z_6|c$}; +\node[color=red] at ($0.5*(B6)+0.5*(B7)$) [above] {$|z_7|c$}; +\node[color=red] at ($0.5*(B7)+0.5*(B8)$) [above] {$|z_8|c$}; +\node[color=red] at ($0.5*(B8)+0.5*(B9)$) [above] {$|z_9|c$}; +\node[color=red] at ($0.5*(B9)+0.5*(B10)$) [above] {$|z_{10}|c$}; + +\node[color=red] at ($0.8*(B10)$) [rotate=20,below] {$\displaystyle c\sum_{i=1}^n |z_i|$}; + +\end{tikzpicture} +\end{document} + diff --git a/buch/chapters/80-wahrscheinlichkeit/images/positiv.jpg b/buch/chapters/80-wahrscheinlichkeit/images/positiv.jpg new file mode 100644 index 0000000..53544cb Binary files /dev/null and b/buch/chapters/80-wahrscheinlichkeit/images/positiv.jpg differ diff --git a/buch/chapters/80-wahrscheinlichkeit/images/positiv.m b/buch/chapters/80-wahrscheinlichkeit/images/positiv.m new file mode 100644 index 0000000..4dca950 --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/positiv.m @@ -0,0 +1,36 @@ +# +# positiv.m +# +# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +# +N = 10; +p = 0.2; + +A = eye(3) + p * rand(3,3); +A = [ + 1, 0.2, 0.2; + 0.1, 1, 0.1; + 0.05, 0.05, 1 +]; +B = eye(3); + +function retval = punkt(x) + retval = sprintf("<%.4f,%.4f,%.4f>", x(1), x(3), x(2)); +end + +fn = fopen("quadrant.inc", "w"); +for i = (1:N) + fprintf(fn, "quadrant(%s,%s,%s)\n", + punkt(B(:,1)), punkt(B(:,2)), punkt(B(:,3))) + B = B * A; +end + +x = [ 1; 1; 1 ]; +for i = (1:100) + x = A * x; + x = x / norm(x); +end +fprintf(fn, "eigenvektor(<%.4f, %.4f, %.4f>)\n", x(1), x(3), x(2)); + + +fclose(fn); diff --git a/buch/chapters/80-wahrscheinlichkeit/images/positiv.png b/buch/chapters/80-wahrscheinlichkeit/images/positiv.png new file mode 100644 index 0000000..a2bd9bf Binary files /dev/null and b/buch/chapters/80-wahrscheinlichkeit/images/positiv.png differ diff --git a/buch/chapters/80-wahrscheinlichkeit/images/positiv.pov b/buch/chapters/80-wahrscheinlichkeit/images/positiv.pov new file mode 100644 index 0000000..9197498 --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/positiv.pov @@ -0,0 +1,137 @@ +// +// diffusion.pov +// +// (c) 2021 Prof Dr Andreas Müller, OST Ostscheizer Fachhochschule +// +#version 3.7; +#include "colors.inc" + +global_settings { + assumed_gamma 1 +} + +#declare imagescale = 0.077; +#declare N = 30; +#declare vscale = 10; +#declare r = 0.04; + +camera { + location <43, 20, -20> + look_at <1, 0.83, 2.5> + right 16/9 * x * imagescale + up y * imagescale +} + +light_source { + <40, 20, -10> color White + area_light <1,0,0> <0,0,1>, 10, 10 + adaptive 1 + jitter +} + +sky_sphere { + pigment { + color rgb<1,1,1> + } +} + +// +// draw an arrow from to with thickness with +// color +// +#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 + } + 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/trenn.pdf b/buch/chapters/80-wahrscheinlichkeit/images/trenn.pdf new file mode 100644 index 0000000..f4fa58f Binary files /dev/null and b/buch/chapters/80-wahrscheinlichkeit/images/trenn.pdf differ diff --git a/buch/chapters/80-wahrscheinlichkeit/images/trenn.tex b/buch/chapters/80-wahrscheinlichkeit/images/trenn.tex new file mode 100644 index 0000000..f34879c --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/trenn.tex @@ -0,0 +1,44 @@ +% +% trenn.tex -- Trenntrick graphische Darstellung +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usetikzlibrary{arrows,intersections,math} +\begin{document} +\def\skala{1} +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\def\d{6} + +\coordinate (u) at (5,3); +\coordinate (v) at (3,1); +\coordinate (ve) at (5,1.666); + +\fill[color=gray!40] (0,0) rectangle (u); + +\begin{scope} +\clip (0,0) rectangle (6.1,4.1); +\draw[color=red] (0,0) -- (9,3); +\end{scope} + +\draw[->] (-0.1,0) -- (6.3,0) coordinate[label={$x_1$}]; +\draw[->] (0,-0.1) -- (0,4.3) coordinate[label={right:$x_2$}]; + +\fill (u) circle[radius=0.05]; +\node at (u) [above right] {$u$}; + +\fill (v) circle[radius=0.05]; +\node at (v) [above right] {$v$}; + +\fill[color=red] (ve) circle[radius=0.05]; +\node[color=red] at (ve) [above,rotate={atan(1/3)}] {$(1+\varepsilon)v$}; + +\end{tikzpicture} +\end{document} + diff --git a/buch/chapters/80-wahrscheinlichkeit/images/vergleich.jpg b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.jpg new file mode 100644 index 0000000..3274f42 Binary files /dev/null and b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.jpg differ diff --git a/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf new file mode 100644 index 0000000..feb19a2 Binary files /dev/null and b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf differ diff --git a/buch/chapters/80-wahrscheinlichkeit/images/vergleich.png b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.png new file mode 100644 index 0000000..f20bd48 Binary files /dev/null and b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.png differ diff --git a/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pov b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pov new file mode 100644 index 0000000..e696481 --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pov @@ -0,0 +1,203 @@ +// +// diffusion.pov +// +// (c) 2021 Prof Dr Andreas Müller, OST Ostscheizer Fachhochschule +// +#version 3.7; +#include "colors.inc" +#include "textures.inc" +#include "transforms.inc" + +global_settings { + assumed_gamma 1 +} + +#declare imagescale = 0.077; +#declare N = 30; +#declare vscale = 10; +#declare r = 0.04; + +camera { + location <43, 20, -20> + look_at <1, 0.83, 2.5> + right 16/9 * x * imagescale + up y * imagescale +} + +light_source { + <20, 60, -80> color White + area_light <1,0,0> <0,0,1>, 40, 40 + adaptive 1 + jitter +} + +sky_sphere { + pigment { + color rgb<1,1,1> + } +} + +// +// draw an arrow from to with thickness with +// color +// +#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 + } + 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(, A_transformation); +#declare Vy = vtransform(<0, V.y, 0>, A_transformation); +#declare UU = vtransform(U, A_transformation); +#declare Ux = vtransform(, 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/positiv.tex b/buch/chapters/80-wahrscheinlichkeit/positiv.tex index f956374..935aa2d 100644 --- a/buch/chapters/80-wahrscheinlichkeit/positiv.tex +++ b/buch/chapters/80-wahrscheinlichkeit/positiv.tex @@ -40,6 +40,10 @@ seine Komponenten nicht negativ sind: $v_i\ge 0\forall i$. \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 @@ -177,6 +181,22 @@ 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} @@ -207,12 +227,26 @@ 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. +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$. +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] @@ -269,6 +303,21 @@ $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 @@ -276,7 +325,8 @@ 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$. +eines gemeinsamen Einheitsvektors $c$ sind: $u_i=|u_i|c$ +(siehe auch Abbildung~\ref{buch:wahrscheinlichkeit:fig:dreieck}). \end{satz} \begin{proof}[Beweis] @@ -310,6 +360,7 @@ 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 \[ @@ -454,7 +505,7 @@ $v$ ein nichtnegativer Eigenvektor. \end{proof} \begin{satz} -Sei $A$ ein positive Matrix und $v$ ein Eigenvektor zu einem +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} @@ -609,9 +660,24 @@ bis 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} +Der Satz~\ref{buch:wahrscheinlichkeit:satz:perron-frobenius} +von Perron-Frobenius kann auf primitive Matrizen verallgemeinert +werden. +\begin{satz} +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}. +\end{proof} -- cgit v1.2.1 From 8e60e54d34a85a7458457ec7e7c2359204e9d55f Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Tue, 26 Jan 2021 18:43:06 +0100 Subject: =?UTF-8?q?Illustrationen=20zum=20Kapitel=20=C3=BCber=20positive?= =?UTF-8?q?=20Matrizen?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- .../chapters/80-wahrscheinlichkeit/images/Makefile | 7 ++- .../80-wahrscheinlichkeit/images/positiv.pdf | Bin 0 -> 124093 bytes .../80-wahrscheinlichkeit/images/positiv.tex | 51 +++++++++++++++++++++ .../80-wahrscheinlichkeit/images/vergleich.pdf | Bin 120558 -> 120558 bytes buch/chapters/80-wahrscheinlichkeit/positiv.tex | 23 ++++++++++ 5 files changed, 79 insertions(+), 2 deletions(-) create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/positiv.pdf create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/positiv.tex (limited to 'buch/chapters/80-wahrscheinlichkeit') diff --git a/buch/chapters/80-wahrscheinlichkeit/images/Makefile b/buch/chapters/80-wahrscheinlichkeit/images/Makefile index 5511f14..8042eb1 100644 --- a/buch/chapters/80-wahrscheinlichkeit/images/Makefile +++ b/buch/chapters/80-wahrscheinlichkeit/images/Makefile @@ -3,8 +3,8 @@ # # (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschulen # -all: dreieck.pdf trenn.pdf vergleich.pdf vergleich.jpg positiv.jpg \ - diffusion.png diffusion.pdf +all: dreieck.pdf trenn.pdf vergleich.pdf vergleich.jpg \ + positiv.pdf positiv.jpg diffusion.png diffusion.pdf # Visualisierung diffusion in einer primitiven Matrix diffusion.pdf: diffusion.tex diffusion.jpg @@ -20,6 +20,9 @@ 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 diff --git a/buch/chapters/80-wahrscheinlichkeit/images/positiv.pdf b/buch/chapters/80-wahrscheinlichkeit/images/positiv.pdf new file mode 100644 index 0000000..39aa3cd Binary files /dev/null and b/buch/chapters/80-wahrscheinlichkeit/images/positiv.pdf differ 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/vergleich.pdf b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf index feb19a2..bbcc95a 100644 Binary files a/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf and b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf differ diff --git a/buch/chapters/80-wahrscheinlichkeit/positiv.tex b/buch/chapters/80-wahrscheinlichkeit/positiv.tex index 935aa2d..4cdc533 100644 --- a/buch/chapters/80-wahrscheinlichkeit/positiv.tex +++ b/buch/chapters/80-wahrscheinlichkeit/positiv.tex @@ -399,6 +399,29 @@ 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. -- cgit v1.2.1 From 474af74b757abcc54670c8de170c7458543a801a Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Fri, 29 Jan 2021 20:59:05 +0100 Subject: new stuff about parrondo --- buch/chapters/80-wahrscheinlichkeit/parrondo.tex | 725 +++++++++++++++++++++ .../80-wahrscheinlichkeit/rechnungen/btilde.maxima | 46 ++ 2 files changed, 771 insertions(+) create mode 100644 buch/chapters/80-wahrscheinlichkeit/rechnungen/btilde.maxima (limited to 'buch/chapters/80-wahrscheinlichkeit') diff --git a/buch/chapters/80-wahrscheinlichkeit/parrondo.tex b/buch/chapters/80-wahrscheinlichkeit/parrondo.tex index ac4163e..d1a38ca 100644 --- a/buch/chapters/80-wahrscheinlichkeit/parrondo.tex +++ b/buch/chapters/80-wahrscheinlichkeit/parrondo.tex @@ -6,3 +6,728 @@ \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 +\begin{tikzpicture}[>=latex,thick] +\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} +\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 elementweisen 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 +$\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} += +\begin{pmatrix}1&1&1\end{pmatrix} +G\odot B. +\] +Die Gewinnerwartung ist dann das Produkt +\[ +E(Y) += +\sum_{i=0}^2 +E(Y|K\equiv i) p_i += +\begin{pmatrix}1&1&1\end{pmatrix} +(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 +\begin{pmatrix}1&1&1\end{pmatrix} 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} +\begin{pmatrix}\frac13&\frac13&\frac13\end{pmatrix} += +\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. + +\subsubsection{Das modifizierte Spiel $B$} +\begin{figure} +\centering +\begin{tikzpicture}[>=latex,thick] +\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} +\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} +&= +\begin{pmatrix}1&1&1\end{pmatrix} G\odot \tilde{B} +\\ +&= +\begin{pmatrix}1&1&1\end{pmatrix} G\odot B ++ +\varepsilon +\begin{pmatrix}1&1&1\end{pmatrix} G\odot F +\\ +&= +\begin{pmatrix} -\frac{8}{10}&\frac12&\frac12 \end{pmatrix} ++ +\varepsilon\begin{pmatrix}2&2&2\end{pmatrix} +\\ +&= +\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) +&= +\begin{pmatrix}1&1&1\end{pmatrix} G\odot \tilde{B} +\begin{pmatrix} +\frac13& +\frac13& +\frac13 +\end{pmatrix} +\\ +&= +\begin{pmatrix}1&1&1\end{pmatrix} G\odot B +\begin{pmatrix} \frac13& \frac13& \frac13 \end{pmatrix} ++ +\varepsilon +\begin{pmatrix}1&1&1\end{pmatrix} G\odot F +\begin{pmatrix} \frac13& \frac13& \frac13 \end{pmatrix} +\\ +&= +\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} += +\] +Wie früher ist +\begin{align*} +E(Y) +&= +e^t (G\odot \tilde{B}) p +\\ +&= +\begin{pmatrix} +\end{pmatrix} +p += +\end{align*} + +% +% Die Kombination +% +\subsection{Kombination der Spiele +\label{buch:subsection:kombination}} + +% +% Gewinn-Erwartung +% +\subsection{Gewinnerwartung +\label{buch:subsection:gewinnerwartung}} + +% +% Gleichgewichtszustand +% +\subsection{Gleichgewichtszustand +\label{buch:subsection:gleichgewichtszustand}} + + + + diff --git a/buch/chapters/80-wahrscheinlichkeit/rechnungen/btilde.maxima b/buch/chapters/80-wahrscheinlichkeit/rechnungen/btilde.maxima new file mode 100644 index 0000000..16be152 --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/rechnungen/btilde.maxima @@ -0,0 +1,46 @@ +Btilde: matrix( + [ -1 , 1/4 + epsilon, 3/4 - epsilon ], + [ 1/10 - epsilon, -1 , 1/4 + epsilon ], + [ 9/10 + epsilon, 3/4 - epsilon, -1 ] +); + +r: expand(Btilde[1] / Btilde[1,1]); +Btilde[1]: r; +Btilde[2]: Btilde[2] - Btilde[2,1] * r; +Btilde[3]: Btilde[3] - Btilde[3,1] * r; + +Btilde: expand(Btilde); + +r: Btilde[2] / Btilde[2,2]; +Btilde[2]: r; +Btilde[3]: Btilde[3] - Btilde[3,2] * r; + +Btilde: ratsimp(expand(Btilde)); + +Btilde[1]: Btilde[1] - Btilde[1,2] * Btilde[2]; + +Btilde: ratsimp(expand(Btilde)); + +l: 78 + 12 * epsilon + 80 * epsilon^2; + +D: ratsimp(expand(l*Btilde)); +n: ratsimp(expand(l -D[1,3] -D[2,3])); + +p: (1/n) * matrix( +[ -Btilde[1,3]*l ], +[ -Btilde[2,3]*l ], +[ l ] +); +p: ratsimp(expand(p)); + +taylor(p, epsilon, 0, 3); + +G: matrix( + [ 0, 1, -1 ], + [ -1, 0, 1 ], + [ 1, -1, 0 ] +); + +e: matrix([1,1,1]); + +ratsimp(expand(e. (G*Btilde) . p)); -- cgit v1.2.1 From e66709beeb36ee6f0967a0e309e41f52af29935f Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Sat, 30 Jan 2021 21:46:50 +0100 Subject: =?UTF-8?q?parrondo=20vollst=C3=A4ndig?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- buch/chapters/80-wahrscheinlichkeit/parrondo.tex | 219 ++++++++++++++++++--- .../80-wahrscheinlichkeit/rechnungen/btilde.maxima | 107 +++++++--- 2 files changed, 269 insertions(+), 57 deletions(-) (limited to 'buch/chapters/80-wahrscheinlichkeit') diff --git a/buch/chapters/80-wahrscheinlichkeit/parrondo.tex b/buch/chapters/80-wahrscheinlichkeit/parrondo.tex index d1a38ca..3bdba9a 100644 --- a/buch/chapters/80-wahrscheinlichkeit/parrondo.tex +++ b/buch/chapters/80-wahrscheinlichkeit/parrondo.tex @@ -205,7 +205,7 @@ G=\begin{pmatrix} \end{pmatrix} \] gibt die Gewinne an, die bei einem Übergang anfallen. -Die Matrixelemente $g_{ij}b_{ij}$ des elementweisen Produktes +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. @@ -218,7 +218,7 @@ E(Y|K\equiv j) 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 -$\begin{pmatrix}1&1&1\end{pmatrix}$ +$U^t=\begin{pmatrix}1&1&1\end{pmatrix}$ entsteht: \[ \begin{pmatrix} @@ -227,7 +227,7 @@ E(Y|K\equiv 1)& E(Y|K\equiv 2) \end{pmatrix} = -\begin{pmatrix}1&1&1\end{pmatrix} +U^t G\odot B. \] Die Gewinnerwartung ist dann das Produkt @@ -237,7 +237,7 @@ E(Y) \sum_{i=0}^2 E(Y|K\equiv i) p_i = -\begin{pmatrix}1&1&1\end{pmatrix} +U^t (G\odot B)p. \] Tatsächlich ist @@ -250,7 +250,7 @@ G\odot B -\frac9{10} & \frac34 & 0 \end{pmatrix} \quad\text{und}\quad -\begin{pmatrix}1&1&1\end{pmatrix} G\odot B +U^t G\odot B = \begin{pmatrix}-\frac{8}{10}&\frac12&\frac12\end{pmatrix}. \] @@ -260,10 +260,10 @@ Dies stimmt mit den Erwartungswerten in Die gesamte Geinnerwartung ist dann \begin{equation} (G\odot B) -\begin{pmatrix}\frac13&\frac13&\frac13\end{pmatrix} +\begin{pmatrix}\frac13\\\frac13\\\frac13\end{pmatrix} = \begin{pmatrix}-\frac{8}{10}&\frac12&\frac12\end{pmatrix} -\begin{pmatrix}\frac13&\frac13&\frac13\end{pmatrix} +\frac13U = \frac13\biggl(-\frac{8}{10}+\frac12+\frac12\biggr) = @@ -433,6 +433,27 @@ 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 $B$} \begin{figure} \centering @@ -545,18 +566,18 @@ E(Y|K\equiv 1)& E(Y|K\equiv 2) \end{pmatrix} &= -\begin{pmatrix}1&1&1\end{pmatrix} G\odot \tilde{B} +U^t (G\odot \tilde{B}) \\ &= -\begin{pmatrix}1&1&1\end{pmatrix} G\odot B +U^t (G\odot B) + \varepsilon -\begin{pmatrix}1&1&1\end{pmatrix} G\odot F +U^t (G\odot F) \\ &= \begin{pmatrix} -\frac{8}{10}&\frac12&\frac12 \end{pmatrix} + -\varepsilon\begin{pmatrix}2&2&2\end{pmatrix} +2\varepsilon U^t \\ &= \begin{pmatrix} -\frac{8}{10}+2\varepsilon&\frac12+2\varepsilon&\frac12+2\varepsilon \end{pmatrix}. @@ -566,20 +587,22 @@ erhält man die Gewinnerwartung \begin{align*} E(Y) &= -\begin{pmatrix}1&1&1\end{pmatrix} G\odot \tilde{B} +U^t(G\odot \tilde{B}) \begin{pmatrix} -\frac13& -\frac13& +\frac13\\ +\frac13\\ \frac13 \end{pmatrix} \\ &= -\begin{pmatrix}1&1&1\end{pmatrix} G\odot B -\begin{pmatrix} \frac13& \frac13& \frac13 \end{pmatrix} +U^t +(G\odot B) +\frac13 U + \varepsilon -\begin{pmatrix}1&1&1\end{pmatrix} G\odot F -\begin{pmatrix} \frac13& \frac13& \frac13 \end{pmatrix} +U^t +(G\odot F) +\frac13 U \\ &= \frac1{15} @@ -696,37 +719,169 @@ 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 +Wie früher ist der erwartete Gewinn \begin{align*} E(Y) &= -e^t (G\odot \tilde{B}) p +U^t (G\odot \tilde{B}) p_{\varepsilon} \\ &= \begin{pmatrix} +-\frac{3}{10}-2\varepsilon & \frac12-2\varepsilon & \frac12-2\varepsilon \end{pmatrix} -p -= +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}. +\] -% -% Gewinn-Erwartung -% -\subsection{Gewinnerwartung -\label{buch:subsection:gewinnerwartung}} +\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. -% -% Gleichgewichtszustand -% -\subsection{Gleichgewichtszustand -\label{buch:subsection:gleichgewichtszustand}} +\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/rechnungen/btilde.maxima b/buch/chapters/80-wahrscheinlichkeit/rechnungen/btilde.maxima index 16be152..6ba2ee6 100644 --- a/buch/chapters/80-wahrscheinlichkeit/rechnungen/btilde.maxima +++ b/buch/chapters/80-wahrscheinlichkeit/rechnungen/btilde.maxima @@ -1,46 +1,103 @@ -Btilde: matrix( - [ -1 , 1/4 + epsilon, 3/4 - epsilon ], - [ 1/10 - epsilon, -1 , 1/4 + epsilon ], - [ 9/10 + epsilon, 3/4 - epsilon, -1 ] +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(Btilde[1] / Btilde[1,1]); -Btilde[1]: r; -Btilde[2]: Btilde[2] - Btilde[2,1] * r; -Btilde[3]: Btilde[3] - Btilde[3,1] * r; +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; -Btilde: expand(Btilde); +B0: expand(B0); -r: Btilde[2] / Btilde[2,2]; -Btilde[2]: r; -Btilde[3]: Btilde[3] - Btilde[3,2] * r; +r: B0[2] / B0[2,2]; +B0[2]: r; +B0[3]: B0[3] - B0[3,2] * r; -Btilde: ratsimp(expand(Btilde)); +B0: ratsimp(expand(B0)); -Btilde[1]: Btilde[1] - Btilde[1,2] * Btilde[2]; +B0[1]: B0[1] - B0[1,2] * B0[2]; -Btilde: ratsimp(expand(Btilde)); +B0: ratsimp(expand(B0)); l: 78 + 12 * epsilon + 80 * epsilon^2; -D: ratsimp(expand(l*Btilde)); +D: ratsimp(expand(l*B0)); n: ratsimp(expand(l -D[1,3] -D[2,3])); p: (1/n) * matrix( -[ -Btilde[1,3]*l ], -[ -Btilde[2,3]*l ], +[ -B0[1,3]*l ], +[ -B0[2,3]*l ], [ l ] ); p: ratsimp(expand(p)); -taylor(p, epsilon, 0, 3); +/* compute the expected gain */ +G*B; +ratsimp(expand(transpose(U). (G*B) . p)); -G: matrix( - [ 0, 1, -1 ], - [ -1, 0, 1 ], - [ 1, -1, 0 ] +/* 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); -e: matrix([1,1,1]); +/* expectation */ -ratsimp(expand(e. (G*Btilde) . p)); +G*Btilde; +gainepsilon: ratsimp(expand(transpose(U). (G*Btilde) . pepsilon)); +taylor(gainepsilon, epsilon, 0, 5); -- cgit v1.2.1 From 063038e94ac789b3d7b7cf2884d8f3e948b0a926 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Sun, 31 Jan 2021 21:15:06 +0100 Subject: Markov-Ketten --- buch/chapters/80-wahrscheinlichkeit/google.tex | 16 +- buch/chapters/80-wahrscheinlichkeit/markov.tex | 783 ++++++++++++++++++++++++ buch/chapters/80-wahrscheinlichkeit/positiv.tex | 1 + 3 files changed, 792 insertions(+), 8 deletions(-) (limited to 'buch/chapters/80-wahrscheinlichkeit') diff --git a/buch/chapters/80-wahrscheinlichkeit/google.tex b/buch/chapters/80-wahrscheinlichkeit/google.tex index bb5597d..c1318fe 100644 --- a/buch/chapters/80-wahrscheinlichkeit/google.tex +++ b/buch/chapters/80-wahrscheinlichkeit/google.tex @@ -358,7 +358,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 +369,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 +385,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} @@ -409,13 +409,13 @@ 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 \] heisst die {\em Google-Matrix}. diff --git a/buch/chapters/80-wahrscheinlichkeit/markov.tex b/buch/chapters/80-wahrscheinlichkeit/markov.tex index 5fb156a..0d77926 100644 --- a/buch/chapters/80-wahrscheinlichkeit/markov.tex +++ b/buch/chapters/80-wahrscheinlichkeit/markov.tex @@ -6,5 +6,788 @@ \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_0s$ 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 Date: Mon, 1 Feb 2021 13:29:17 +0100 Subject: =?UTF-8?q?=C3=9Cbersicht=20algebraische=20Strukturen?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- buch/chapters/80-wahrscheinlichkeit/google.tex | 7 +- .../chapters/80-wahrscheinlichkeit/images/Makefile | 7 +- .../80-wahrscheinlichkeit/images/konvex.pdf | Bin 0 -> 24033 bytes .../80-wahrscheinlichkeit/images/konvex.tex | 75 +++++++++++++++ .../80-wahrscheinlichkeit/images/vergleich.pdf | Bin 120558 -> 120558 bytes buch/chapters/80-wahrscheinlichkeit/markov.tex | 101 ++++++++++++++++++++- buch/chapters/80-wahrscheinlichkeit/positiv.tex | 14 +++ 7 files changed, 196 insertions(+), 8 deletions(-) create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/konvex.pdf create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/konvex.tex (limited to 'buch/chapters/80-wahrscheinlichkeit') diff --git a/buch/chapters/80-wahrscheinlichkeit/google.tex b/buch/chapters/80-wahrscheinlichkeit/google.tex index c1318fe..42cd0a1 100644 --- a/buch/chapters/80-wahrscheinlichkeit/google.tex +++ b/buch/chapters/80-wahrscheinlichkeit/google.tex @@ -401,9 +401,9 @@ A \] vereinfacht werden. -\begin{definition} +\begin{definition}[Google-Matrix] Die Matrix -\[ +\begin{equation} G = \alpha H @@ -416,7 +416,8 @@ G \alpha H + (1-\alpha)qU^t -\] +\label{buch:wahrscheinlichkeit:eqn:google-matrix} +\end{equation} heisst die {\em Google-Matrix}. \index{Google-Matrix}% diff --git a/buch/chapters/80-wahrscheinlichkeit/images/Makefile b/buch/chapters/80-wahrscheinlichkeit/images/Makefile index 8042eb1..24c0631 100644 --- a/buch/chapters/80-wahrscheinlichkeit/images/Makefile +++ b/buch/chapters/80-wahrscheinlichkeit/images/Makefile @@ -4,7 +4,8 @@ # (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschulen # all: dreieck.pdf trenn.pdf vergleich.pdf vergleich.jpg \ - positiv.pdf positiv.jpg diffusion.png diffusion.pdf + positiv.pdf positiv.jpg diffusion.png diffusion.pdf \ + konvex.pdf # Visualisierung diffusion in einer primitiven Matrix diffusion.pdf: diffusion.tex diffusion.jpg @@ -53,3 +54,7 @@ dreieck.pdf: dreieck.tex drei.inc drei.inc: dreieck.m octave dreieck.m + +# Konvex +konvex.pdf: konvex.tex + pdflatex konvex.tex diff --git a/buch/chapters/80-wahrscheinlichkeit/images/konvex.pdf b/buch/chapters/80-wahrscheinlichkeit/images/konvex.pdf new file mode 100644 index 0000000..f77cc62 Binary files /dev/null and b/buch/chapters/80-wahrscheinlichkeit/images/konvex.pdf differ diff --git a/buch/chapters/80-wahrscheinlichkeit/images/konvex.tex b/buch/chapters/80-wahrscheinlichkeit/images/konvex.tex new file mode 100644 index 0000000..05bbc60 --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/konvex.tex @@ -0,0 +1,75 @@ +% +% konvex.tex -- template for standalon tikz images +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usetikzlibrary{arrows,intersections,math,calc,hobby} +\begin{document} +\def\skala{1} +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\def\punkt#1{ + \fill[color=white] #1 circle[radius=0.05]; + \draw #1 circle[radius=0.05]; +} + +\begin{scope}[xshift=-3cm] +\coordinate (O) at (0,0); +\coordinate (A) at (-1,5); +\coordinate (B) at (3,2); +\draw[->] (O) -- (A); +\draw[->] (O) -- (B); +\begin{scope} +\clip (-2,0) rectangle (4,6); +\draw[color=red!40,line width=0.4pt] ($2*(B)-(A)$) -- ($2*(A)-(B)$); +\end{scope} +\draw[color=red,line width=1.5pt] (A) -- (B); +\punkt{(O)} +\punkt{(A)} +\punkt{(B)} +\node at (O) [below left] {$O$}; +\node at (A) [above right] {$A$}; +\node at (B) [above right] {$B$}; +\node at ($0.5*(A)$) [left] {$\vec{a}$}; +\node at ($0.5*(B)$) [below right] {$\vec{b}$}; +\fill[color=white] ($0.6*(A)+0.4*(B)$) circle[radius=0.05]; +\draw[color=red] ($0.6*(A)+0.4*(B)$) circle[radius=0.05]; +\node[color=red] at ($0.6*(A)+0.4*(B)$) [above right] {$t\vec{a}+(1-t)\vec{b}$}; +\end{scope} + +\begin{scope}[xshift=4cm] +\coordinate (O) at (0,0); +\coordinate (A) at (-1,3); +\coordinate (B) at (2,5); +\coordinate (C) at (4,1); +\draw[->] (O) -- (A); +\draw[->] (O) -- (B); +\draw[->] (O) -- (C); +\fill[color=red!50,opacity=0.5] (A) -- (B) -- (C) -- cycle; +\draw[color=red,line width=1.5pt,opacity=0.7] (A) -- (B) -- (C) -- cycle; +\punkt{(O)} +\punkt{(A)} +\punkt{(B)} +\punkt{(C)} +\node at (O) [below left] {$O$}; +\node at (A) [left] {$P_1$}; +\node at (B) [above] {$P_2$}; +\node at (C) [right] {$P_3$}; +\node at ($0.5*(A)$) [left] {$\vec{p}_1$}; +\node at ($0.3*(B)$) [right] {$\vec{p}_2$}; +\node at ($0.5*(C)$) [below] {$\vec{p}_3$}; +\fill[color=white] ($0.5*(C)+0.3*(A)+0.2*(B)$) circle[radius=0.05]; +\draw[color=red] ($0.5*(C)+0.3*(A)+0.2*(B)$) circle[radius=0.05]; +\node[color=red] at ($0.5*(C)+0.3*(A)+0.2*(B)$) [above] {$\displaystyle\sum_{t=1}^3 t_i\vec{p}_i$}; +\end{scope} + + +\end{tikzpicture} +\end{document} + diff --git a/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf index bbcc95a..f065f76 100644 Binary files a/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf and b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf differ diff --git a/buch/chapters/80-wahrscheinlichkeit/markov.tex b/buch/chapters/80-wahrscheinlichkeit/markov.tex index 0d77926..9df7e89 100644 --- a/buch/chapters/80-wahrscheinlichkeit/markov.tex +++ b/buch/chapters/80-wahrscheinlichkeit/markov.tex @@ -439,6 +439,17 @@ Das Problem, die stationären Verteilungen von $T$ zu finden, ist auf die Untermatrizen $T_i$ reduziert worden. \subsubsection{Die konvexe Menge der stationären Verteilungen} +\begin{figure} +\centering +\includegraphics{chapters/80-wahrscheinlichkeit/images/konvex.pdf} +\caption{Die Konvexe Kombination von Vektoren $\vec{p}_1,\dots,\vec{p}_n$ ist +eine Summe der Form $\sum_{i=1}^n t_i\vec{p}_i$ wobei die $t_i\ge 0$ +sind mit $\sum_{i=1}^nt_i=1$. +Für zwei Punkte bilden die konvexen Kombinationen die Verbindungsstrecke +zwischen den Punkten, für drei Punkte in drei Dimensionen spannen die +konvexen Kombinationen ein Dreieck auf. +\label{buch:wahrscheinlichkeit:fig:konvex}} +\end{figure} Die stationären Verteilungen \[ \operatorname{Stat}(T) @@ -674,6 +685,7 @@ E&R\\ \right). \] Die Matrix $R$ beschreibt die Wahrscheinlichkeiten, mit denen man +ausgehend von einem transienten Zustand in einem bestimmten absorbierenden Zustand landet. Die Matrix $Q$ beschreibt die Übergänge, bevor dies passiert. Die Potenzen von $T$ sind @@ -698,7 +710,7 @@ E&R+RQ+RQ^2 \\ \end{array} \right), \; -\dots +\dots, \; T^k = @@ -740,9 +752,90 @@ Wenn der Prozess genau im Schritt $k$ zum ersten Mal Zustand $i$ ankommt, dann ist $E(k)$ die mittlere Wartezeit. Der Prozess verbringt also zunächst $k-1$ Schritte in transienten Zuständen, bevor er in einen absorbierenden Zustand wechselt. -Die Wahrscheinlichkeit ausgehend vom transjenten Zustand $j$ in -genau $k$ Schritten im absorbierenden Zustand zu landen ist -das Matrix-Element $(i,j)$ der Matrix $RQ^{k-1}$. + +Wir brauchen die Wahrscheinlichkeit für einen Entwicklung des Zustandes +ausgehend vom Zustand $j$, die nach $k-1$ Schritten im Zustand $l$ +landet, von wo er in den absorbierenden Zustand wechselt. +Diese Wahrscheinlichkeit ist +\[ +P(X_k = i\wedge X_{k-1} = l \wedge X_0=j) += +\sum_{i_1,\dots,i_{k-2}} +r_{il} q_{li_{k-2}} q_{i_{k-2}i_{k-3}}\dots q_{i_2i_1} q_{i_1j} +\] +Von den Pfaden, die zur Zeit $k-1$ im Zustand $l$ ankommen gibt es +aber auch einige, die nicht absorbiert werden. +Für die Berechnung der Wartezeit möchten wir nur die Wahrscheinlichkeit +innerhalb der Menge der Pfade, die auch tatsächlich absorbiert werden, +das ist die bedingte Wahrscheinlichkeit +\begin{equation} +\begin{aligned} +P(X_k = i\wedge X_{k-1} = l \wedge X_0=j|X_k=i) +&= +\frac{ +P(X_k = i\wedge X_{k-1} = l \wedge X_0=j) +}{ +P(X_k=i) +} +\\ +&= +\sum_{i_1,\dots,i_{k-2}} +q_{li_{k-2}} q_{i_{k-2}i_{k-3}}\dots q_{i_2i_1} q_{i_1j}. +\end{aligned} +\label{buch:wahrscheinlichkeit:eqn:ankunftswahrscheinlichkeit} +\end{equation} +Auf der rechten Seite steht das Matrixelement $(l,j)$ von $Q^{k-1}$. + +% XXX Differenz + +Für die Berechnung der erwarteten Zeit ist müssen wir die +Wahrscheinlichkeit mit $k$ multiplizieren und summieren: +\begin{align} +E(k) +&= +\sum_{k=0}^\infty +k( +q^{(k)}_{lj} +- +q^{(k-1)}_{lj} +) +\notag +\\ +&= +\dots ++ +(k+1)( +q^{(k)}_{lj} +- +q^{(k+1)}_{lj} +) ++ +k( +q^{(k-1)}_{lj} +- +q^{(k)}_{lj} +) ++ +\dots +\label{buch:wahrscheinlichkeit:eqn:telescope} +\\ +&= +\dots ++ +q^{(k-1)}_{lj} ++ +\dots += +\sum_{k} q^{(k)}_{lj}. +\notag +\end{align} +In zwei benachbarten Termen in +\eqref{buch:wahrscheinlichkeit:eqn:telescope} +heben sich die Summanden $kq^{(k)}_{lj}$ weg, man spricht von +einer teleskopischen Reihe. +Die verbleibenden Terme sind genau die Matrixelemente der Fundamentalmatrix $N$. +Die Fundamentalmatrix enthält also im Eintrag $(l,j)$ die Wartezeit +bis zur Absorption über den Zustand $l$. \subsubsection{Wartezeit} % XXX Mittlere Zeit bis zu einem bestimmten Zustand diff --git a/buch/chapters/80-wahrscheinlichkeit/positiv.tex b/buch/chapters/80-wahrscheinlichkeit/positiv.tex index c49ffd6..9f8f38f 100644 --- a/buch/chapters/80-wahrscheinlichkeit/positiv.tex +++ b/buch/chapters/80-wahrscheinlichkeit/positiv.tex @@ -689,6 +689,18 @@ Dann gibt es einen positiven Eigenvektor zum Eigenwert $\varrho(A)$, mit geometrischer und algebraischer Vielfachheit $1$. \end{satz} +\begin{beispiel} +In der Google-Matrix mit freiem Willen +nach +\eqref{buch:wahrscheinlichkeit:eqn:google-matrix} +enthält den Term $((1-\alpha)/N)UU^t$. +Die Matrix $UU^t$ ist eine Matrix aus lauter Einsen, der Term +ist also für $\alpha < 1$ eine positive Matrix. +Die Google-Matrix ist daher eine positive Matrix. +Nach dem Satz von Perron-Frobenius ist die Grenzverteilung +eindeutig bestimmt. +\end{beispiel} + Der Satz~\ref{buch:wahrscheinlichkeit:satz:perron-frobenius} von Perron-Frobenius kann auf primitive Matrizen verallgemeinert werden. @@ -704,4 +716,6 @@ und er hat geometrische und algebraische Vielfachheit $1$. Nach Voraussetzung gibt es ein $n$ derart, dass $A^n>0$. Für $A^n$ gelten die Resultate von Satz~\ref{buch:wahrscheinlichkeit:satz:perron-frobenius}. + +XXX TODO \end{proof} -- cgit v1.2.1 From 4c0bd6f788ee36619671c7301a1fa4520bffd438 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Tue, 9 Feb 2021 20:44:05 +0100 Subject: Illustrationen Markov-Ketten --- buch/chapters/80-wahrscheinlichkeit/google.tex | 105 +++++++++---------- .../chapters/80-wahrscheinlichkeit/images/Makefile | 15 ++- .../80-wahrscheinlichkeit/images/internet.pdf | Bin 0 -> 10681 bytes .../80-wahrscheinlichkeit/images/internet.tex | 58 +++++++++++ .../80-wahrscheinlichkeit/images/markov.pdf | Bin 0 -> 28921 bytes .../80-wahrscheinlichkeit/images/markov.tex | 99 ++++++++++++++++++ .../80-wahrscheinlichkeit/images/markov2.pdf | Bin 0 -> 31027 bytes .../80-wahrscheinlichkeit/images/markov2.tex | 113 +++++++++++++++++++++ .../80-wahrscheinlichkeit/images/markov3.pdf | Bin 0 -> 30437 bytes .../80-wahrscheinlichkeit/images/markov3.tex | 113 +++++++++++++++++++++ .../80-wahrscheinlichkeit/images/vergleich.pdf | Bin 120558 -> 120558 bytes buch/chapters/80-wahrscheinlichkeit/markov.tex | 42 +++++++- 12 files changed, 490 insertions(+), 55 deletions(-) create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/internet.pdf create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/internet.tex create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/markov.pdf create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/markov.tex create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/markov2.pdf create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/markov2.tex create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/markov3.pdf create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/markov3.tex (limited to 'buch/chapters/80-wahrscheinlichkeit') diff --git a/buch/chapters/80-wahrscheinlichkeit/google.tex b/buch/chapters/80-wahrscheinlichkeit/google.tex index 42cd0a1..3616760 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,58 @@ 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} +%\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 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. @@ -389,7 +390,7 @@ Im Fall $q=\frac1NU$ kann dies zu \[ A = -\frac1N uU^t +\frac1N UU^t = \frac1N \begin{pmatrix} diff --git a/buch/chapters/80-wahrscheinlichkeit/images/Makefile b/buch/chapters/80-wahrscheinlichkeit/images/Makefile index 24c0631..b04f6ff 100644 --- a/buch/chapters/80-wahrscheinlichkeit/images/Makefile +++ b/buch/chapters/80-wahrscheinlichkeit/images/Makefile @@ -5,7 +5,7 @@ # all: dreieck.pdf trenn.pdf vergleich.pdf vergleich.jpg \ positiv.pdf positiv.jpg diffusion.png diffusion.pdf \ - konvex.pdf + konvex.pdf internet.pdf markov.pdf markov2.pdf markov3.pdf # Visualisierung diffusion in einer primitiven Matrix diffusion.pdf: diffusion.tex diffusion.jpg @@ -58,3 +58,16 @@ drei.inc: 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 + diff --git a/buch/chapters/80-wahrscheinlichkeit/images/internet.pdf b/buch/chapters/80-wahrscheinlichkeit/images/internet.pdf new file mode 100644 index 0000000..12eaf1e Binary files /dev/null and b/buch/chapters/80-wahrscheinlichkeit/images/internet.pdf differ diff --git a/buch/chapters/80-wahrscheinlichkeit/images/internet.tex b/buch/chapters/80-wahrscheinlichkeit/images/internet.tex new file mode 100644 index 0000000..1b384ad --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/internet.tex @@ -0,0 +1,58 @@ +% +% internet.tex -- Modellinternet +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usetikzlibrary{arrows,intersections,math} +\begin{document} +\def\skala{1} +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\foreach \x in {0,3,6,9}{ + \foreach \y in {0,3}{ + \fill[color=white] ({\x},{\y}) circle[radius=0.3]; + \draw ({\x},{\y}) circle[radius=0.3]; + } +} +\node at (0,3) {$1$}; +\node at (0,0) {$2$}; +\node at (3,3) {$3$}; +\node at (3,0) {$4$}; +\node at (6,3) {$5$}; +\node at (6,0) {$6$}; +\node at (9,3) {$7$}; +\node at (9,0) {$8$}; +% 1 +\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (0,3) -- (3,3); +\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (0,3) -- (0,0); +% 2 +\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (0,0) to[out=-20,in=-160] (3,0); +% 3 +\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,3) -- (6,3); +\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,3) -- (0,0); +% 4 +\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,0) -- (6,3); +\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,0) -- (6,0); +\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,0) to[out=160,in=20] (0,0); +% 5 +\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (6,3) -- (9,3); +\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (6,3) -- (9,0); +\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (6,3) -- (6,0); +% 6 +\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (6,0) to[out=20,in=160] (9,0); +% 7 +\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (9,3) .. controls (7.5,4) .. (6,4) -- (3,4) .. controls (1.5,4) .. (0,3); +\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (9,3) to[out=-110,in=110] (9,0); +% 8 +\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (9,0) to[out=-160,in=-20] (6,0); +\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (9,0) to[out=70,in=-70] (9,3); + +\end{tikzpicture} +\end{document} + diff --git a/buch/chapters/80-wahrscheinlichkeit/images/markov.pdf b/buch/chapters/80-wahrscheinlichkeit/images/markov.pdf new file mode 100644 index 0000000..fba9489 Binary files /dev/null and b/buch/chapters/80-wahrscheinlichkeit/images/markov.pdf differ diff --git a/buch/chapters/80-wahrscheinlichkeit/images/markov.tex b/buch/chapters/80-wahrscheinlichkeit/images/markov.tex new file mode 100644 index 0000000..72f3b85 --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/markov.tex @@ -0,0 +1,99 @@ +% +% markov2.tex -- template for standalon tikz images +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usetikzlibrary{arrows,intersections,math} +\begin{document} +\def\skala{1} +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\def\punkt#1#2#3{ + \fill[color=white] #1 circle[radius=0.10]; + \fill[color=#2] #1 circle[radius=0.13]; + \node[color=white] at #1 {$\scriptstyle #3$}; +} + +\def\xs{2.5} +\def\ys{1} + +\foreach \x in {0,...,5}{ + \draw[color=red,line width=0.5pt] + ({\x*\xs},{-0.7*\ys}) -- ({\x*\xs},{-6.5*\ys}); +} + +\def\dotradius{0.04} + +\def\dotrow#1#2{ + \punkt{({#1*\xs},{-1*\ys})}{#2}{1} + \punkt{({#1*\xs},{-2*\ys})}{#2}{2} + \punkt{({#1*\xs},{-3*\ys})}{#2}{3} + \punkt{({#1*\xs},{-4*\ys})}{#2}{4} + \fill[color=#2] ({#1*\xs},{-5*\ys-0.3}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-5*\ys-0.15}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-5*\ys}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-5*\ys+0.15}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-5*\ys+0.3}) circle[radius=\dotradius]; + \punkt{({#1*\xs},{-6*\ys})}{#2}{s} +} + +\def\fan#1#2{ + \foreach \x in {1,2,3,4,6}{ + \foreach \y in {1,2,3,4,6}{ + \draw[->,shorten >= 2mm,shorten <= 2mm,color=#2] + ({#1*\xs},{-\x*\ys}) + -- + ({(#1+1)*\xs},{-\y*\ys}); + } + } +} + +\begin{scope} +\clip (-0.5,{-6.5*\ys}) rectangle ({5*\xs+0.5},-0.5); +\fan{-1}{gray} +\fan{0}{gray} +\fan{1}{gray} +\fan{2}{black} +\fan{3}{gray} +\fan{4}{gray} +\fan{5}{gray} +\end{scope} + +\dotrow{0}{gray} +\dotrow{1}{gray} +\dotrow{2}{black} +\dotrow{3}{black} +\dotrow{4}{gray} +\dotrow{5}{gray} + +\def\ty{-0.5} +\node[color=gray] at ({0.5*\xs},{\ty*\ys}) {$T(n-1,n-2)$}; +\node[color=gray] at ({1.5*\xs},{\ty*\ys}) {$T(n,n-1)$}; +\node[color=black] at ({2.5*\xs},{\ty*\ys}) {$T(n+1,n)$}; +\node[color=gray] at ({3.5*\xs},{\ty*\ys}) {$T(n+2,n+1)$}; +\node[color=gray] at ({4.5*\xs},{\ty*\ys}) {$T(n+3,n+2)$}; + +\draw[->,color=red] (-0.7,{-6.5*\ys}) -- ({5*\xs+0.7},{-6.5*\ys}) coordinate[label={$t$}]; + +\foreach \x in {0,...,5}{ + \draw[color=red] + ({\x*\xs},{-6.5*\ys-0.05}) + -- + ({\x*\xs},{-6.5*\ys+0.05}); +} +\node[color=red] at ({0*\xs},{-6.5*\ys}) [below] {$n-2\mathstrut$}; +\node[color=red] at ({1*\xs},{-6.5*\ys}) [below] {$n-1\mathstrut$}; +\node[color=red] at ({2*\xs},{-6.5*\ys}) [below] {$n\mathstrut$}; +\node[color=red] at ({3*\xs},{-6.5*\ys}) [below] {$n+1\mathstrut$}; +\node[color=red] at ({4*\xs},{-6.5*\ys}) [below] {$n+2\mathstrut$}; +\node[color=red] at ({5*\xs},{-6.5*\ys}) [below] {$n+3\mathstrut$}; + +\end{tikzpicture} +\end{document} + diff --git a/buch/chapters/80-wahrscheinlichkeit/images/markov2.pdf b/buch/chapters/80-wahrscheinlichkeit/images/markov2.pdf new file mode 100644 index 0000000..d534c8f Binary files /dev/null and b/buch/chapters/80-wahrscheinlichkeit/images/markov2.pdf differ diff --git a/buch/chapters/80-wahrscheinlichkeit/images/markov2.tex b/buch/chapters/80-wahrscheinlichkeit/images/markov2.tex new file mode 100644 index 0000000..c2fab2e --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/markov2.tex @@ -0,0 +1,113 @@ +% +% markov.tex -- Illustration markov-Kette +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usetikzlibrary{arrows,intersections,math} +\begin{document} +\def\skala{1} +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\def\punkt#1#2#3{ + \fill[color=white] #1 circle[radius=0.10]; + \fill[color=#2] #1 circle[radius=0.13]; + \node[color=white] at #1 {$\scriptstyle #3$}; +} + +\def\xs{2.5} +\def\ys{1} + +\foreach \x in {0,...,5}{ + \draw[color=red,line width=0.5pt] + ({\x*\xs},{-0.7*\ys}) -- ({\x*\xs},{-8.5*\ys}); +} + +\def\dotradius{0.04} + +\def\dotrow#1#2{ + \punkt{({#1*\xs},{-1*\ys})}{#2}{1} + \punkt{({#1*\xs},{-2*\ys})}{#2}{2} + \fill[color=#2] ({#1*\xs},{-3*\ys-0.3}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-3*\ys-0.15}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-3*\ys}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-3*\ys+0.15}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-3*\ys+0.3}) circle[radius=\dotradius]; + \punkt{({#1*\xs},{-4*\ys})}{#2}{7} + \punkt{({#1*\xs},{-5*\ys})}{#2}{8} + \punkt{({#1*\xs},{-6*\ys})}{#2}{9} + \fill[color=#2] ({#1*\xs},{-7*\ys-0.3}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-7*\ys-0.15}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-7*\ys}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-7*\ys+0.15}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-7*\ys+0.3}) circle[radius=\dotradius]; + \punkt{({#1*\xs},{-8*\ys})}{#2}{s} +} + +\def\fan#1#2{ + \foreach \x in {1,2,4}{ + \foreach \y in {1,2,4}{ + \draw[->,shorten >= 2mm,shorten <= 2mm,color=#2] + ({#1*\xs},{-\x*\ys}) + -- + ({(#1+1)*\xs},{-\y*\ys}); + } + } + \foreach \x in {5,6,8}{ + \foreach \y in {5,6,8}{ + \draw[->,shorten >= 2mm,shorten <= 2mm,color=#2] + ({#1*\xs},{-\x*\ys}) + -- + ({(#1+1)*\xs},{-\y*\ys}); + } + } +} + +\begin{scope} +\clip (-0.5,{-8.5*\ys}) rectangle ({5*\xs+0.5},-0.5); +\fan{-1}{gray} +\fan{0}{gray} +\fan{1}{gray} +\fan{2}{black} +\fan{3}{gray} +\fan{4}{gray} +\fan{5}{gray} +\end{scope} + +\dotrow{0}{gray} +\dotrow{1}{gray} +\dotrow{2}{black} +\dotrow{3}{black} +\dotrow{4}{gray} +\dotrow{5}{gray} + +\def\ty{-0.5} +\node[color=gray] at ({0.5*\xs},{\ty*\ys}) {$T(n-1,n-2)$}; +\node[color=gray] at ({1.5*\xs},{\ty*\ys}) {$T(n,n-1)$}; +\node[color=black] at ({2.5*\xs},{\ty*\ys}) {$T(n+1,n)$}; +\node[color=gray] at ({3.5*\xs},{\ty*\ys}) {$T(n+2,n+1)$}; +\node[color=gray] at ({4.5*\xs},{\ty*\ys}) {$T(n+3,n+2)$}; + +\draw[->,color=red] (-0.7,{-8.5*\ys}) -- ({5*\xs+0.7},{-8.5*\ys}) coordinate[label={$t$}]; + +\foreach \x in {0,...,5}{ + \draw[color=red] + ({\x*\xs},{-8.5*\ys-0.05}) + -- + ({\x*\xs},{-8.5*\ys+0.05}); +} +\node[color=red] at ({0*\xs},{-8.5*\ys}) [below] {$n-2\mathstrut$}; +\node[color=red] at ({1*\xs},{-8.5*\ys}) [below] {$n-1\mathstrut$}; +\node[color=red] at ({2*\xs},{-8.5*\ys}) [below] {$n\mathstrut$}; +\node[color=red] at ({3*\xs},{-8.5*\ys}) [below] {$n+1\mathstrut$}; +\node[color=red] at ({4*\xs},{-8.5*\ys}) [below] {$n+2\mathstrut$}; +\node[color=red] at ({5*\xs},{-8.5*\ys}) [below] {$n+3\mathstrut$}; + +\end{tikzpicture} +\end{document} + diff --git a/buch/chapters/80-wahrscheinlichkeit/images/markov3.pdf b/buch/chapters/80-wahrscheinlichkeit/images/markov3.pdf new file mode 100644 index 0000000..61f4fe7 Binary files /dev/null and b/buch/chapters/80-wahrscheinlichkeit/images/markov3.pdf differ diff --git a/buch/chapters/80-wahrscheinlichkeit/images/markov3.tex b/buch/chapters/80-wahrscheinlichkeit/images/markov3.tex new file mode 100644 index 0000000..0b99ef3 --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/markov3.tex @@ -0,0 +1,113 @@ +% +% markov2.tex -- template for standalon tikz images +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usetikzlibrary{arrows,intersections,math} +\begin{document} +\def\skala{1} +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\def\punkt#1#2#3{ + \fill[color=white] #1 circle[radius=0.10]; + \fill[color=#2] #1 circle[radius=0.13]; + \node[color=white] at #1 {$\scriptstyle #3$}; +} + +\def\xs{2.5} +\def\ys{1} + +\fill[color=blue!20] + (-0.5,{-3.3*\ys}) rectangle ({5*\xs+0.5},{-0.7*\ys}); + +\foreach \x in {0,...,5}{ + \draw[color=red,line width=0.5pt] + ({\x*\xs},{-0.7*\ys}) -- ({\x*\xs},{-7.5*\ys}); +} + +\def\dotradius{0.04} + +\def\dotrow#1#2{ + \punkt{({#1*\xs},{-1*\ys})}{#2}{1} + \fill[color=#2] ({#1*\xs},{-2*\ys-0.3}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-2*\ys-0.15}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-2*\ys}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-2*\ys+0.15}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-2*\ys+0.3}) circle[radius=\dotradius]; + \punkt{({#1*\xs},{-3*\ys})}{#2}{7} + \punkt{({#1*\xs},{-4*\ys})}{#2}{8} + \punkt{({#1*\xs},{-5*\ys})}{#2}{9} + \fill[color=#2] ({#1*\xs},{-6*\ys-0.3}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-6*\ys-0.15}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-6*\ys}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-6*\ys+0.15}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-6*\ys+0.3}) circle[radius=\dotradius]; + \punkt{({#1*\xs},{-7*\ys})}{#2}{s} +} + +\def\fan#1#2{ + \foreach \x in {1,3}{ + \draw[->,shorten >= 2mm,shorten <= 2mm,color=#2,line width=2pt] + ({#1*\xs},{-\x*\ys}) + -- + ({(#1+1)*\xs},{-\x*\ys}); + } + \foreach \x in {4,5,7}{ + \foreach \y in {1,3,4,5,7}{ + \draw[->,shorten >= 2mm,shorten <= 2mm,color=#2] + ({#1*\xs},{-\x*\ys}) + -- + ({(#1+1)*\xs},{-\y*\ys}); + } + } +} + +\begin{scope} +\clip (-0.5,{-7.5*\ys}) rectangle ({5*\xs+0.5},-0.5); +\fan{-1}{gray} +\fan{0}{gray} +\fan{1}{gray} +\fan{2}{black} +\fan{3}{gray} +\fan{4}{gray} +\fan{5}{gray} +\end{scope} + +\dotrow{0}{gray} +\dotrow{1}{gray} +\dotrow{2}{black} +\dotrow{3}{black} +\dotrow{4}{gray} +\dotrow{5}{gray} + +\def\ty{-0.5} +\node[color=gray] at ({0.5*\xs},{\ty*\ys}) {$T(n-1,n-2)$}; +\node[color=gray] at ({1.5*\xs},{\ty*\ys}) {$T(n,n-1)$}; +\node[color=black] at ({2.5*\xs},{\ty*\ys}) {$T(n+1,n)$}; +\node[color=gray] at ({3.5*\xs},{\ty*\ys}) {$T(n+2,n+1)$}; +\node[color=gray] at ({4.5*\xs},{\ty*\ys}) {$T(n+3,n+2)$}; + +\draw[->,color=red] (-0.7,{-7.5*\ys}) -- ({5*\xs+0.7},{-7.5*\ys}) coordinate[label={$t$}]; + +\foreach \x in {0,...,5}{ + \draw[color=red] + ({\x*\xs},{-7.5*\ys-0.05}) + -- + ({\x*\xs},{-7.5*\ys+0.05}); +} +\node[color=red] at ({0*\xs},{-7.5*\ys}) [below] {$n-2\mathstrut$}; +\node[color=red] at ({1*\xs},{-7.5*\ys}) [below] {$n-1\mathstrut$}; +\node[color=red] at ({2*\xs},{-7.5*\ys}) [below] {$n\mathstrut$}; +\node[color=red] at ({3*\xs},{-7.5*\ys}) [below] {$n+1\mathstrut$}; +\node[color=red] at ({4*\xs},{-7.5*\ys}) [below] {$n+2\mathstrut$}; +\node[color=red] at ({5*\xs},{-7.5*\ys}) [below] {$n+3\mathstrut$}; + +\end{tikzpicture} +\end{document} + diff --git a/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf index f065f76..c6173ce 100644 Binary files a/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf and b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf differ diff --git a/buch/chapters/80-wahrscheinlichkeit/markov.tex b/buch/chapters/80-wahrscheinlichkeit/markov.tex index 9df7e89..0485714 100644 --- a/buch/chapters/80-wahrscheinlichkeit/markov.tex +++ b/buch/chapters/80-wahrscheinlichkeit/markov.tex @@ -171,6 +171,9 @@ 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, @@ -195,9 +198,18 @@ 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. +zeitliche Entwicklung dar +(Abbildung~\ref{buch:wahrscheinlichkeit:fig:diskretemarkovkette}). Aus der Matrix \[ T(n+1,n) @@ -384,12 +396,28 @@ 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 @@ -671,7 +699,17 @@ Nicht absorbierende Zustände heissen {\em transient} \index{transienter Zustand}% \end{definition} -Eine Markov-Kette kann mehrere absorbierende Zustände haben. +\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 \[ -- cgit v1.2.1 From ada53a9c225b896c8d7608300427aac475bb7045 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Tue, 9 Feb 2021 21:52:16 +0100 Subject: move all iamges to separate files --- buch/chapters/80-wahrscheinlichkeit/google.tex | 40 ---------- .../chapters/80-wahrscheinlichkeit/images/Makefile | 8 +- .../80-wahrscheinlichkeit/images/spielB.pdf | Bin 0 -> 9917 bytes .../80-wahrscheinlichkeit/images/spielB.tex | 59 ++++++++++++++ .../80-wahrscheinlichkeit/images/spielBtilde.pdf | Bin 0 -> 14592 bytes .../80-wahrscheinlichkeit/images/spielBtilde.tex | 59 ++++++++++++++ .../80-wahrscheinlichkeit/images/vergleich.pdf | Bin 120558 -> 120558 bytes buch/chapters/80-wahrscheinlichkeit/parrondo.tex | 88 +-------------------- 8 files changed, 128 insertions(+), 126 deletions(-) create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/spielB.pdf create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/spielB.tex create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/spielBtilde.pdf create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/spielBtilde.tex (limited to 'buch/chapters/80-wahrscheinlichkeit') diff --git a/buch/chapters/80-wahrscheinlichkeit/google.tex b/buch/chapters/80-wahrscheinlichkeit/google.tex index 3616760..ca78b3d 100644 --- a/buch/chapters/80-wahrscheinlichkeit/google.tex +++ b/buch/chapters/80-wahrscheinlichkeit/google.tex @@ -41,46 +41,6 @@ zerstört. \begin{figure} \centering \includegraphics{chapters/80-wahrscheinlichkeit/images/internet.pdf} -%\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} diff --git a/buch/chapters/80-wahrscheinlichkeit/images/Makefile b/buch/chapters/80-wahrscheinlichkeit/images/Makefile index b04f6ff..8d34217 100644 --- a/buch/chapters/80-wahrscheinlichkeit/images/Makefile +++ b/buch/chapters/80-wahrscheinlichkeit/images/Makefile @@ -5,7 +5,8 @@ # 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 + 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 @@ -71,3 +72,8 @@ markov2.pdf: 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/spielB.pdf b/buch/chapters/80-wahrscheinlichkeit/images/spielB.pdf new file mode 100644 index 0000000..466974d Binary files /dev/null and b/buch/chapters/80-wahrscheinlichkeit/images/spielB.pdf differ diff --git a/buch/chapters/80-wahrscheinlichkeit/images/spielB.tex b/buch/chapters/80-wahrscheinlichkeit/images/spielB.tex new file mode 100644 index 0000000..92989ed --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/spielB.tex @@ -0,0 +1,59 @@ +% +% spielB.tex -- Zutandsdiagramm für Spiel B +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usetikzlibrary{arrows,intersections,math} +\begin{document} +\def\skala{1} +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\def\R{2} +\def\r{0.5} +\coordinate (A) at (0,\R); +\coordinate (B) at ({\R*sqrt(3)/2},{-0.5*\R}); +\coordinate (C) at ({-\R*sqrt(3)/2},{-0.5*\R}); + +\draw[->,shorten >= 0.5cm,shorten <= 0.5cm] (A) -- (B); +\draw[->,shorten >= 0.5cm,shorten <= 0.5cm] (A) -- (C); +\draw[->,shorten >= 0.5cm,shorten <= 0.5cm] (C) -- (B); + +\draw[->,shorten >= 0.5cm,shorten <= 0.5cm] (B) to[out=90,in=-30] (A); +\draw[->,shorten >= 0.5cm,shorten <= 0.5cm] (C) to[out=90,in=-150] (A); +\draw[->,shorten >= 0.5cm,shorten <= 0.5cm] (B) to[out=-150,in=-30] (C); + +\pgfmathparse{0.93*\R} +\xdef\Rgross{\pgfmathresult} + +\node at (30:\Rgross) {$\frac34$}; +\node at (150:\Rgross) {$\frac14$}; +\node at (-90:\Rgross) {$\frac14$}; + +\pgfmathparse{0.33*\R} +\xdef\Rklein{\pgfmathresult} + +\node at (-90:\Rklein) {$\frac34$}; +\node at (30:\Rklein) {$\frac9{10}$}; +\node at (150:\Rklein) {$\frac1{10}$}; + +\fill[color=white] (A) circle[radius=\r]; +\draw (A) circle[radius=\r]; +\node at (A) {$0$}; + +\fill[color=white] (B) circle[radius=\r]; +\draw (B) circle[radius=\r]; +\node at (B) {$2$}; + +\fill[color=white] (C) circle[radius=\r]; +\draw (C) circle[radius=\r]; +\node at (C) {$1$}; + +\end{tikzpicture} +\end{document} + diff --git a/buch/chapters/80-wahrscheinlichkeit/images/spielBtilde.pdf b/buch/chapters/80-wahrscheinlichkeit/images/spielBtilde.pdf new file mode 100644 index 0000000..7812c9c Binary files /dev/null and b/buch/chapters/80-wahrscheinlichkeit/images/spielBtilde.pdf differ diff --git a/buch/chapters/80-wahrscheinlichkeit/images/spielBtilde.tex b/buch/chapters/80-wahrscheinlichkeit/images/spielBtilde.tex new file mode 100644 index 0000000..b2d4b01 --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/spielBtilde.tex @@ -0,0 +1,59 @@ +% +% spielBtilde.tex -- Zustandsdiagramm des modifzierten Spiels +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usetikzlibrary{arrows,intersections,math} +\begin{document} +\def\skala{1} +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\def\R{2.5} +\def\r{0.5} +\coordinate (A) at (0,\R); +\coordinate (B) at ({\R*sqrt(3)/2},{-0.5*\R}); +\coordinate (C) at ({-\R*sqrt(3)/2},{-0.5*\R}); + +\draw[->,shorten >= 0.5cm,shorten <= 0.5cm] (A) -- (B); +\draw[->,shorten >= 0.5cm,shorten <= 0.5cm] (A) -- (C); +\draw[->,shorten >= 0.5cm,shorten <= 0.5cm] (C) -- (B); + +\draw[->,shorten >= 0.5cm,shorten <= 0.5cm] (B) to[out=90,in=-30] (A); +\draw[->,shorten >= 0.5cm,shorten <= 0.5cm] (C) to[out=90,in=-150] (A); +\draw[->,shorten >= 0.5cm,shorten <= 0.5cm] (B) to[out=-150,in=-30] (C); + +\pgfmathparse{0.93*\R} +\xdef\Rgross{\pgfmathresult} + +\node at (30:\Rgross) {$\frac34-\varepsilon$}; +\node at (150:\Rgross) {$\frac14+\varepsilon$}; +\node at (-90:\Rgross) {$\frac14+\varepsilon$}; + +\pgfmathparse{0.32*\R} +\xdef\Rklein{\pgfmathresult} + +\node at (-90:\Rklein) {$\frac34-\varepsilon$}; +\node at (30:\Rklein) {$\frac9{10}+\varepsilon$}; +\node at (150:\Rklein) {$\frac1{10}-\varepsilon$}; + +\fill[color=white] (A) circle[radius=\r]; +\draw (A) circle[radius=\r]; +\node at (A) {$0$}; + +\fill[color=white] (B) circle[radius=\r]; +\draw (B) circle[radius=\r]; +\node at (B) {$2$}; + +\fill[color=white] (C) circle[radius=\r]; +\draw (C) circle[radius=\r]; +\node at (C) {$1$}; + +\end{tikzpicture} +\end{document} + diff --git a/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf index c6173ce..b7215b4 100644 Binary files a/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf and b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf differ diff --git a/buch/chapters/80-wahrscheinlichkeit/parrondo.tex b/buch/chapters/80-wahrscheinlichkeit/parrondo.tex index 3bdba9a..a62d813 100644 --- a/buch/chapters/80-wahrscheinlichkeit/parrondo.tex +++ b/buch/chapters/80-wahrscheinlichkeit/parrondo.tex @@ -61,48 +61,7 @@ Fälle recht gross, in einem Fall aber sehr klein. \subsubsection{Übergangsmatrix im Spiel $B$} \begin{figure} \centering -\begin{tikzpicture}[>=latex,thick] -\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} +\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}} @@ -454,51 +413,10 @@ U^t (G\odot B) p \] wie erwartet. -\subsubsection{Das modifizierte Spiel $B$} +\subsubsection{Das modifizierte Spiel $\tilde{B}$} \begin{figure} \centering -\begin{tikzpicture}[>=latex,thick] -\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} +\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$ -- cgit v1.2.1