From f88b8071a623096f9004007ced8ec97195aaa218 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Sat, 25 Sep 2021 16:43:39 +0200 Subject: zweite Lesung --- buch/chapters/80-wahrscheinlichkeit/google.tex | 25 ++++---- .../80-wahrscheinlichkeit/images/diffusion.jpg | Bin 203856 -> 203825 bytes .../80-wahrscheinlichkeit/images/diffusion.pdf | Bin 220008 -> 219976 bytes .../80-wahrscheinlichkeit/images/diffusion.png | Bin 265323 -> 265254 bytes .../80-wahrscheinlichkeit/images/dreieck.pdf | Bin 23945 -> 23945 bytes .../80-wahrscheinlichkeit/images/markov2.pdf | Bin 31027 -> 31110 bytes .../80-wahrscheinlichkeit/images/markov2.tex | 7 +++ .../80-wahrscheinlichkeit/images/positiv.jpg | Bin 111361 -> 111354 bytes .../80-wahrscheinlichkeit/images/positiv.pdf | Bin 124093 -> 124086 bytes .../80-wahrscheinlichkeit/images/positiv.png | Bin 191808 -> 191730 bytes buch/chapters/80-wahrscheinlichkeit/markov.tex | 65 ++++++++++++--------- buch/chapters/80-wahrscheinlichkeit/parrondo.tex | 12 ++-- buch/chapters/80-wahrscheinlichkeit/positiv.tex | 26 +++++---- 13 files changed, 80 insertions(+), 55 deletions(-) (limited to 'buch/chapters/80-wahrscheinlichkeit') diff --git a/buch/chapters/80-wahrscheinlichkeit/google.tex b/buch/chapters/80-wahrscheinlichkeit/google.tex index c9d0d8c..c8d6379 100644 --- a/buch/chapters/80-wahrscheinlichkeit/google.tex +++ b/buch/chapters/80-wahrscheinlichkeit/google.tex @@ -71,7 +71,7 @@ mehr Gewicht als eine Seite mit vielen Links, unter denen der Link auf die Seite $j$ einer von Vielen ist. Im Beispiel-Internet der Abbildung~\ref{buch:figure:modellinternet} signalisiert die Seite $6$ mit nur einem Link auf die Seite $8$ -viel deutlicher, dass $8$ eine wichtige Seite ist, also die die +viel deutlicher, dass $8$ eine wichtige Seite ist, also dies die Seite $5$ tut, die auch noch zwei andere Links enthält. Wir können diesen Unterschied berücksichtigen, indem wir zu einem Wahrscheinlichkeitsmodell übergehen, was wir im folgenden Abschnitt @@ -91,7 +91,7 @@ einer bestimmten Seite landet. Wir bezeichnen mit $S_i$ das Ereignis, dass sich der Besucher auf der Seite mit der Nummer $i$ befindet, wobei $i=1,\dots,N$. Gesucht ist die Wahrscheinlichkeit $P(S_i)$. -Ohne weitere Information müssten wir davon ausgehen, dass jede Seite +Ohne weitere Information müssen wir davon ausgehen, dass jede Seite etwa gleich wahrscheinlich ist, dass also $P(S_i) = 1/N$. Wir wissen jedoch mehr. @@ -128,6 +128,7 @@ Falls es einen Link gibt, ist $P(S'_j\mid S_i)\ge 0$. A priori wissen wir nicht, wie wahrscheinlich es ist, dass der Besucher dem Link auf die Seite $j$ folgt, normalerweise werden nicht alle Links mit gleicher Wahrscheinlichkeit verwendet. +Darüber hben wir aber keine Detailinformation. Wir nehmen daher vereinfachend an, dass alle Links gleich wahrscheinlich sind. Enthält die Seite $i$ genau $n_i$ Links, dann ist die Wahrscheinlichkeit, @@ -142,13 +143,13 @@ Es gilt \begin{equation} P(S'_j) = -P(S'j\mid S_1) P(S_1) +P(S'_j\mid S_1) P(S_1) + -P(S'j\mid S_2) P(S_2) +P(S'_j\mid S_2) P(S_2) + \dots + -P(S'j\mid S_N) P(S_N) +P(S'_j\mid S_N) P(S_N) = \sum_{i=1}^N P(S_j'\mid S_i)P(S_i) . @@ -212,7 +213,7 @@ entlang eines Links. \begin{beispiel} Für das Beispiel-Internet von Abbildung~\ref{buch:figure:modellinternet} -ist die zugehörige Matrix +ist die zugehörige Link-Matrix \begin{equation} H = \begin{pmatrix} @@ -423,7 +424,7 @@ diskutiert wird. Natürlich ist die heutzutage verwendete Matrix mit Sicherheit komplizierter. In der vorgestellten Form unterstützt sie zum Beispiel auch das folgende -Geschäftsmodell, welches in der Anfangszeit von Google eine Zeitlang +Geschäftsmodell, welches in der Anfangszeit von Google eine Zeit lang erfolgreich war. Ein Anbieter betreibt zu diesem Zweck eine grosse Zahl von Websites, deren Seiten im Wesentlichen aus Suchbegriffen und Links untereinander @@ -457,7 +458,7 @@ Relevanz einer Seite. Wir nehmen an, dass sich diese Wahscheinlichkeit nur langsam ändert. Diese Annahme trifft nicht zu für neue Nachrichten, die durchaus eine -hohe Relevanz haben, für es aber noch nicht viele Links geben kann, +hohe Relevanz haben, für die es aber noch nicht viele Links geben kann, die die Relevanz in der Google-Matrix erkennbar machen. Die Annahme bedeutet, dass sich die Verteilung $p$ sehr viel langsamer ändert als der Navigationsprozess entlang der Links erfolgt. @@ -516,7 +517,7 @@ p Der Vektor $p_0$ ist ein Einheitsvektor in der euklidischen Norm. Er kann daher nicht eine Wahrscheinlichkeitsverteilung sein, da sich die Elemente nicht zu $1$ summieren. -Die $L^1$-Norm $\|\;\cdot\;\|_1$ eines Vektors ist die Summe der Beträge aller +Die $l^1$-Norm $\|\;\cdot\;\|_1$ eines Vektors ist die Summe der Beträge aller Elemente eines Vektors. Indem man $p_0$ durch die Summe aller Einträge von $p_0$ teilt, erhält man die Wahrscheinlichkeitsverteilung $p$. @@ -580,9 +581,9 @@ Numerische Ungenauigkeiten können bewirken, dass die Iteration mit der Matrix $A/\lambda_1$ trotzdem nicht konvergiert. Man kann dies komponsieren, indem man nach jeder Iteration normiert. Da der gesuchte Eigenvektor eine Wahrscheinlichkeitsverteilung sein muss, -muss die $L^1$-Norm $1$ sein. -Statt mit der euklidischen $L^2$-Norm zu normieren, normiert man daher -besser mit der $L^1$-Norm. +muss die $l^1$-Norm $1$ sein. +Statt mit der euklidischen $l^2$-Norm zu normieren, normiert man daher +besser mit der $l^1$-Norm. Damit ergibt sich das folgende Verfahren zur Bestimmung der Pagerank-Verteilung $p$ für die Google-Matrix. diff --git a/buch/chapters/80-wahrscheinlichkeit/images/diffusion.jpg b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.jpg index b79b07b..565ae99 100644 Binary files a/buch/chapters/80-wahrscheinlichkeit/images/diffusion.jpg and b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.jpg differ diff --git a/buch/chapters/80-wahrscheinlichkeit/images/diffusion.pdf b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.pdf index ac4c0ff..46207a5 100644 Binary files a/buch/chapters/80-wahrscheinlichkeit/images/diffusion.pdf and b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.pdf differ diff --git a/buch/chapters/80-wahrscheinlichkeit/images/diffusion.png b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.png index f4c6294..46e6895 100644 Binary files a/buch/chapters/80-wahrscheinlichkeit/images/diffusion.png and b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.png differ diff --git a/buch/chapters/80-wahrscheinlichkeit/images/dreieck.pdf b/buch/chapters/80-wahrscheinlichkeit/images/dreieck.pdf index 0cca2e1..fb8a6bc 100644 Binary files a/buch/chapters/80-wahrscheinlichkeit/images/dreieck.pdf and b/buch/chapters/80-wahrscheinlichkeit/images/dreieck.pdf differ diff --git a/buch/chapters/80-wahrscheinlichkeit/images/markov2.pdf b/buch/chapters/80-wahrscheinlichkeit/images/markov2.pdf index d534c8f..457a650 100644 Binary files a/buch/chapters/80-wahrscheinlichkeit/images/markov2.pdf 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 index c2fab2e..3cf2f2f 100644 --- a/buch/chapters/80-wahrscheinlichkeit/images/markov2.tex +++ b/buch/chapters/80-wahrscheinlichkeit/images/markov2.tex @@ -14,6 +14,8 @@ \def\skala{1} \begin{tikzpicture}[>=latex,thick,scale=\skala] +\definecolor{darkgreen}{rgb}{0,0.6,0} + \def\punkt#1#2#3{ \fill[color=white] #1 circle[radius=0.10]; \fill[color=#2] #1 circle[radius=0.13]; @@ -68,6 +70,11 @@ } } +\fill[color=darkgreen!20] + (-0.5,{-4.2*\ys}) rectangle ({5*\xs+0.5},{-0.8*\ys}); +\fill[color=blue!20] + (-0.5,{-8.2*\ys}) rectangle ({5*\xs+0.5},{-4.8*\ys}); + \begin{scope} \clip (-0.5,{-8.5*\ys}) rectangle ({5*\xs+0.5},-0.5); \fan{-1}{gray} diff --git a/buch/chapters/80-wahrscheinlichkeit/images/positiv.jpg b/buch/chapters/80-wahrscheinlichkeit/images/positiv.jpg index 53544cb..aaa5f80 100644 Binary files a/buch/chapters/80-wahrscheinlichkeit/images/positiv.jpg and b/buch/chapters/80-wahrscheinlichkeit/images/positiv.jpg differ diff --git a/buch/chapters/80-wahrscheinlichkeit/images/positiv.pdf b/buch/chapters/80-wahrscheinlichkeit/images/positiv.pdf index 39aa3cd..7a17ed1 100644 Binary files a/buch/chapters/80-wahrscheinlichkeit/images/positiv.pdf and b/buch/chapters/80-wahrscheinlichkeit/images/positiv.pdf differ diff --git a/buch/chapters/80-wahrscheinlichkeit/images/positiv.png b/buch/chapters/80-wahrscheinlichkeit/images/positiv.png index a2bd9bf..2ea451d 100644 Binary files a/buch/chapters/80-wahrscheinlichkeit/images/positiv.png and b/buch/chapters/80-wahrscheinlichkeit/images/positiv.png differ diff --git a/buch/chapters/80-wahrscheinlichkeit/markov.tex b/buch/chapters/80-wahrscheinlichkeit/markov.tex index 6dad883..226c3d3 100644 --- a/buch/chapters/80-wahrscheinlichkeit/markov.tex +++ b/buch/chapters/80-wahrscheinlichkeit/markov.tex @@ -23,17 +23,17 @@ Ein stochastischer Prozess ist eine Familie von Zufallsvariablen \index{Zufallsvariable}% $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 +er kann beliebige reelle oder diskrete Werte annehmen, 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 +Die Funktion $t\mapsto X_t$ beschreibt 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 +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 @@ -41,17 +41,17 @@ vorstellen. \index{Vorgeschichte}% Die Vorgeschichte besteht dabei aus dem Eintreten gewisser Ereignisse \[ -\{X_0=x_0\}, -\{X_1=x_1\}, -\{X_2=x_2\}, -\dots, +\{X_0=x_0\},\; +\{X_1=x_1\},\; +\{X_2=x_2\},\; +\dots,\; \{X_n=x_n\} \] zu früheren Zeiten $t_00$, wenn alle seine Komponenten positiv sind: $v_i>0\forall i$. +$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$. +seine Komponenten nicht negativ sind: $v_i\ge 0\,\forall i$. \index{positiver Vektor}% \index{nichtnegativer Vektor}% \end{definition} @@ -67,9 +67,9 @@ 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_{i\!j}$ positiv sind: $a_{i\!j}>0\forall i,j$. +wenn alle ihre Einträge $a_{i\!j}$ positiv sind: $a_{i\!j}>0\,\forall i,j$. Eine Matrix $A\in M_{m\times n}(\mathbb{R})$ heisst {\em nichtnegativ}, -wenn alle ihre Einträge $a_{i\!j}$ nichtnegativ sind: $a_{i\!j}\ge 0\forall i,j$. +wenn alle ihre Einträge $a_{i\!j}$ nichtnegativ sind: $a_{i\!j}\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$. @@ -132,7 +132,7 @@ und dass daher für alle $n\ge 5$ die Matrix $A^n$ positiv ist. 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 +für genügend grosses $n$ ist, ist bei Permutationsmatrizen nicht vorhanden. Die Zyklen-Zerlegung einer Permutationsmatrix zeigt, welche Unterräume von $\mathbb{R}^n$ die iterierten Bilder eines @@ -144,14 +144,16 @@ Unterräumen statt. \begin{beispiel} Die Matrix \begin{equation} -A=\begin{pmatrix} +A=\left(\begin{array}{ccc|ccc} 0.9&0.1& & & & \\ 0.1&0.8&0.1& & & \\ &0.1&0.9& & & \\ +\hline & & &0.9&0.1& \\ & & &0.1&0.8&0.1\\ & & & &0.1&0.9 -\end{pmatrix} +\end{array} +\right) \label{buch:wahrscheinlichkeit:eqn:diffusionbloecke} \end{equation} besteht aus zwei $3\times 3$-Blöcken. @@ -164,6 +166,7 @@ Teilmatrizen, aber die Matrix $A^n$ ist für alle $n$ nicht positiv. \end{beispiel} \begin{definition} +\label{buch:positiv:def:primitiv} Eine nichtnegative Matrix mit der Eigenschaft, dass $A^n>0$ für ein genügend grosses $n$, heisst {\em primitiv}. \index{primitive Matrix}% @@ -323,6 +326,7 @@ 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} +angewendet. \label{buch:wahrscheinlichkeit:fig:dreieck}} \end{figure} @@ -344,7 +348,7 @@ gewöhnliche Dreiecksungleichung. Wir nehmen daher jetzt an, die Aussage sei für $n$ bereits bewiesen, wir müssen sie für $n+1$ beweisen. -Die Summe von $n+1$ Vektoren kann man $u=u_1+\dots+u_n$ und $v=u_{n+1}$ +Die Summe von $n+1$ Vektoren kann man in $u=u_1+\dots+u_n$ und $v=u_{n+1}$ aufteilen. Es gilt nach der gewöhnlichen Dreiecksungleichung, dass \[ @@ -465,8 +469,8 @@ Das ist nur möglich, wenn $\lambda > 0$. Wenn $v$ ein Eigenvektor von $A$ ist, dann ist auch jedes Vielfache davon ein Eigenvektor, insbesondere können einzelne Komponenten des Vektors $v$ auch negativ sein. -Der folgende Satz zeigt aber, dass man der Vektor aus den Beträgen -von der Komponenten von $v$ ebenfalls ein Eigenvektor zum +Der folgende Satz zeigt aber, dass der Vektor aus den Beträgen +der Komponenten von $v$ ebenfalls ein Eigenvektor zum gleichen Eigenwert ist. Insbesondere gibt es immer einen nichtnegativen Eigenvektor. -- cgit v1.2.1