From 474af74b757abcc54670c8de170c7458543a801a Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Andreas=20M=C3=BCller?= <andreas.mueller@ost.ch>
Date: Fri, 29 Jan 2021 20:59:05 +0100
Subject: new stuff about parrondo

---
 buch/chapters/80-wahrscheinlichkeit/parrondo.tex | 725 +++++++++++++++++++++++
 1 file changed, 725 insertions(+)

(limited to 'buch/chapters/80-wahrscheinlichkeit/parrondo.tex')

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}}
+
+
+
+
-- 
cgit v1.2.1


From e66709beeb36ee6f0967a0e309e41f52af29935f Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Andreas=20M=C3=BCller?= <andreas.mueller@ost.ch>
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 +++++++++++++++++++----
 1 file changed, 187 insertions(+), 32 deletions(-)

(limited to 'buch/chapters/80-wahrscheinlichkeit/parrondo.tex')

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.
 
 
 
-- 
cgit v1.2.1


From ada53a9c225b896c8d7608300427aac475bb7045 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Andreas=20M=C3=BCller?= <andreas.mueller@ost.ch>
Date: Tue, 9 Feb 2021 21:52:16 +0100
Subject: move all iamges to separate files

---
 buch/chapters/80-wahrscheinlichkeit/parrondo.tex | 88 +-----------------------
 1 file changed, 3 insertions(+), 85 deletions(-)

(limited to 'buch/chapters/80-wahrscheinlichkeit/parrondo.tex')

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

