\documentclass[10pt]{article}

\usepackage{ngerman,a4,amssymb,amsmath}
\usepackage[latin1]{inputenc}
\usepackage{listings}
\usepackage{enumerate}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\Inv}[1]{\ensuremath{\frac{1}{#1}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}

\thispagestyle{empty}

\begin{center}
  {\Large Übungsblatt 6} \\
  Jan Hendrik Dithmar (Matrikelnummer 2031259) \\
  Andreas Steinel (Matrikelnummer 2029984) \\
  Manuel Gorius (Matrikelnummer 2030845) \\
  Robert Vollmann (Matrikelnummer 2030097) \\
  Übungsgruppe Di, 9-11 Uhr \\
  Andreas Augustin \\
\end{center}

\newpage
\section*{Aufgabe 1}
\paragraph{Vorbetrachtung:} Betrachte zwei aufeinander folgende Münzwürfe. Die Wahrscheinlichkeit, dass Zahl geworfen wird unter der
Bedingung, dass zuvor Kopf geworfen wurde, ist $p(Z) \cdot p(K)$. Die Wahrscheinlichkeit, dass Kopf geworfen wird unter der
Bedingung, dass zuvor Zahl geworfen wurde, ist $p(K) \cdot p(Z)$. Die Wahrscheinlichkeiten dieser Fälle ist also gleich.
\paragraph{fairer Wurf mit unfairer Münze:} Es werden immer zwei Würfe mit der potentiell unfairen Münze auf einmal durchgeführt.
Erhält man als Resultat zweimal Kopf oder zweimal Zahl, so wird das Ergebnis verworfen und von vorne begonnen. Erhält man
jedoch als Resultat entweder
\begin{enumerate}[(1)]
  \item zuerst Zahl, dann Kopf oder
  \item zuerst Kopf, dann Zahl
\end{enumerate}
hat man ein faires Ergebnis, da beide Fälle nach Vorbetrachtung gleich wahrscheinlich sind. Die Würfe vor diesem Ergebnis
sowie deren Anzahl werden dabei nicht berücksichtigt. Die Ergebnisse ,,Kopf`` und ,,Zahl`` des \emph{simulierten} fairen
Wurfes kann man beliebig den Fällen zuordnen, es bietet sich die Zuweisung
\begin{enumerate}[(1)]
  \item =: Zahl
  \item =: Kopf
\end{enumerate}
an.
\paragraph{Erwartungswert:} Da wir nur die Fälle betrachten, in denen die zwei jeweils zusammengehörenden potentiell unfairen
Münzwürfe verschiedene Resultate haben, können vor Erreichen dieses Ereignisses einige Wurf-Paare mit zweimal Zahl oder zweimal
Kopf auftreten, bis eine Entscheidung getroffen werden kann. Seien folgende Ereignisse definiert
\begin{itemize}
  \item $Z   = $ es wird einmal Zahl geworfen
  \item $K   = $ es wird einmal Kopf geworfen
  \item $Z^2 = $ ein Wurf-Paar ergibt das Ergebnis Zahl \& Zahl
  \item $K^2 = $ ein Wurf-Paar ergibt das Ergebnis Kopf \& Kopf
  \item $D   = $ ein Wurf-Paar ergibt einen Pasch
  \item $W_n = $ erst beim $n$-ten Wurf-Paar kann eine Entscheidung gefällt werden
\end{itemize}
Für die Wahrscheinlichkeiten der Ereignisse $Z^2$ und $K^2$ gilt trivialerweise
$$ p(Z^2) = p(Z|Z) = p(Z) \cdot p(Z) = p(Z)^2 $$
$$ p(K^2) = p(K|K) = p(K) \cdot p(K) = p(K)^2 $$
Daraus folgt für die Wahrscheinlichkeit von $D$ offensichtlich
$$ p(D) = p(Z^2) + p(K^2) = p(Z)^2 + p(K)^2 $$
Damit das Ereignis $W_n$ eintreten kann, muss vorher $(n-1)$ mal das Ereignis $D$ eintreten. Die Wahrscheinlichkeit, dass das
Ereignis $D$ genau $(n-1)$ mal in Folge auftritt ist $p(D)^{n-1}$. Somit ist
$$ p(W_n) = p(D)^{n-1} = \left( p(Z)^2 + p(K)^2 \right) ^{n-1} $$
Nun stellt sich die Frage wie hoch der Erwartungswert der Anzahl der Würfe, bis eine Entscheidung getroffen werden kann, ist.
Der Erwartungswert ist gleich der unendlichen Summe über das Produkt der Wahrscheinlichkeit, dass $i$ Wurf-Paare benötigt werden,
und der Anzahl der Würfe in diesem Fall, also $2i$, für alle $i$ von $1$ bis $\infty$.
$$ E = \sum_{i=1}^\infty 2i \cdot p(W_i) = \sum_{i=1}^\infty 2i \left( p(Z)^2 + p(K)^2 \right) ^{i-1} $$
Es ist klar, dass $p(Z) = 1 - p(K)$ gelten muss, da anderenfalls kein Wahrscheinlichkeitsraum vorliegt.
Obiger Term für den Erwartungswert $E$ kann somit in eine einfache geschlossene Form gebracht werden, die nur noch von $p(Z)$ abhängt:
$$ E = \Inv{2 \cdot p(Z)^2 ( p(Z)-1 )^2} $$

\section*{Aufgabe 2}
\subsection*{Zu zeigen:}
$$ (E[XY])^2 \le E[X^2] \cdot E[Y^2] $$
\subsubsection*{Beweis in mehreren Schritten:}
\begin{enumerate}[(1)]
  \item \textbf{Zu zeigen:} Für $P(\{Y=0\})=1$ gilt $$ (E[XY])^2 = E[X^2] \cdot E[Y^2] $$
        \textbf{Beweis:}
        \begin{eqnarray*}
          P(\{Y=0\})=1 & \Longrightarrow & p(e)=0 \quad\forall e \in S \text{ mit } Y(e) \neq 0 \\
          (E[XY])^2 & = & E[X^2] \cdot E[Y^2] \\
          \Longleftrightarrow \underbrace{ \left( \sum_{e \in S} \underbrace{p(e) \cdot X(e) \cdot Y(e)}_{=0 \quad (*)} \right)^2}_{=0} & = & \underbrace{\left( \sum_{e \in S} p(e) \cdot X(e)^2 \right) \cdot \underbrace{\left( \sum_{e \in S} \underbrace{p(e) \cdot Y(e)^2}_{=0 \quad (*)} \right)}_{=0}}_{=0} \\
          & & (*) \text{ weil } p(e)=0 \text{ wenn } Y(e) \neq 0 \\
        \end{eqnarray*}
        \QED
  \item Definiere für $P(\{Y=0\} \neq 1$ $$ h(a) = E[(X-aY)^2] $$
        \textbf{Zu zeigen:} $$ h(a) \ge 0 $$ $$ h(a) \text{ hat ein Minimum bei } a^* = \frac{E[XY]}{E[Y^2]} $$
        \textbf{Beweis 1:} $p(e)$ ist per Definition $\ge 0$.
        $$ E[(X-aY)^2] = \underbrace{\sum_{e \in S} \underbrace{p(e)}_{\ge 0} \cdot \underbrace{(X(e)-aY(e))^2}_{\ge 0}}_{\ge 0} $$
        \QED \\
        \textbf{Beweis 2:} Zunächst Berechnung der ersten beiden Ableitungen.
        \begin{eqnarray*}
          h'(a)  & = & \left( \sum_{e \in S} p(e) (X(e)-aY(e))^2 \right)' \\
                 & = & \sum_{e \in S} [ p(e) (X(e)-aY(e))^2 ]' \\
                 & = & \sum_{e \in S} \left[ 2 p(e) (X(e)-aY(e)) \cdot (-Y(e)) \right] \\
                 & = & \sum_{e \in S} 2a p(e) Y(e)^2 - 2 p(e) X(e) Y(e) \\
          h''(a) & = & \left( \sum_{e \in S} 2a p(e) Y(e)^2 - 2 p(e) X(e) Y(e) \right)' \\
                 & = & \sum_{e \in S} [ 2a p(e) Y(e)^2 - 2 p(e) X(e) Y(e) ]' \\
                 & = & \sum_{e \in S} 2 p(e) Y(e)^2
        \end{eqnarray*}
        Damit $h(a)$ an der Stelle $a^*$ ein Minimum hat, muss gelten
        $$ h'(a^*) = 0 \quad\wedge\quad h''(a^*)>0 $$
        Überprüfe die Korrektheit durch Einsetzen und Evaluieren
        \begin{eqnarray*}
          h'(a^*)  & = & \sum_{e \in S} 2a^* p(e) Y(e)^2 - 2 p(e) X(e) Y(e) \\
                   & = & \left( \sum_{e \in S} 2a^* p(e) Y(e)^2 \right) - \left( \sum_{e \in S} 2 p(e) X(e) Y(e) \right) \\
                   & = & 2 \cdot a^* \cdot \left( \sum_{e \in S} p(e) Y(e)^2 \right) - 2 \cdot \left( \sum_{e \in S} p(e) X(e) Y(e) \right) \\
                   & = & 2 \cdot \frac{ \displaystyle \sum_{e \in S} p(e) X(e) Y(e) }{ \displaystyle \sum_{e \in S} p(e) Y(e)^2 } \cdot \left( \sum_{e \in S} p(e) Y(e)^2 \right) - 2 \cdot \left( \sum_{e \in S} p(e) X(e) Y(e) \right) \\
                   & = & 2 \cdot \left( \sum_{e \in S} p(e) X(e) Y(e) \right) - 2 \cdot \left( \sum_{e \in S} p(e) X(e) Y(e) \right) \\
                   & = & 0 \\
          h''(a^*) & = & \sum_{e \in S} 2 \underbrace{p(e)}_{\ge 0} \underbrace{Y(e)^2}_{\ge 0} \\
                   &   & \quad\quad P(\{Y=0\}) \neq 1 \\
                   &   & \quad\quad\quad\quad \Longrightarrow P(\{Y \neq 0\})>0 \\
                   &   & \quad\quad\quad\quad \Longrightarrow \exists e \in S \text{ mit } Y(e) \neq 0 \wedge p(e) > 0 \\
                   &   & \quad\quad\quad\quad \Longrightarrow \text{mindestens ein Summand ist echt größer als $0$} \\
                   & > & 0
        \end{eqnarray*}
        \QED
  \item \textbf{Zu zeigen:} \\ Für $P(\{Y=0\}) \neq 1$ folgt aus $h(a^*) \ge 0$ die Cauchy-Schwarz-Ungleichung. \\
        \textbf{Beweis:}
        \begin{eqnarray*}
          h(a^*) & = & \sum_{e \in S} p(e) (X(e) - a^* Y(e))^2 \\
                 & = & \left( \sum_{e \in S} p(e) X(e)^2 \right) - 2a^* \cdot \left( \sum_{e \in S} p(e) X(e) Y(e) \right) + \left( a^* \right)^2 \left( \sum_{e \in S} p(e) Y(e)^2 \right) \\
                 & = & E[X^2] - 2a^* \cdot E[XY] + \left( a^* \right)^2 \cdot E[Y^2] \\
                 & = & E[X^2] - 2 \cdot \frac{E[XY]}{E[Y^2]} \cdot E[XY] + \left( \frac{E[XY]}{E[Y^2]} \right)^2 \cdot E[Y^2] \\
                 & = & E[X^2] - 2 \cdot \frac{(E[XY])^2}{E[Y^2]} + \frac{(E[XY])^2}{E[Y^2]} \\
                 & = & E[X^2] - \frac{(E[XY])^2}{E[Y^2]} \\
        \end{eqnarray*}
        es gilt
        \begin{itemize}
          \item $h(a^*) \ge 0$ nach Voraussetzung
          \item $h''(a) > 0 \quad\forall a$ nach (2)
          \item $E[Y^2]=\Inv{2} \cdot h''(0) > 0$
        \end{itemize}
        somit gilt
        \begin{eqnarray*}
          E[X^2] - \frac{(E[XY])^2}{E[Y^2]} & \ge & 0 \\
          \Longleftrightarrow\quad\quad E[X^2] & \ge & \frac{(E[XY])^2}{E[Y^2]} \\
          \Longleftrightarrow\quad\quad E[X^2] \cdot E[Y^2] & \ge & (E[XY])^2 \\
        \end{eqnarray*}
        \QED
\end{enumerate}

\section*{Aufgabe 3}
\begin{enumerate}[(a)]
  \item Zu bestimmen:
        $$ P(K^+|T^+) $$
        Der Satz von Bayes besagt
        $$ P(A|B) = \frac{P(A)}{P(A) \cdot P(B|A) + P(\overline{A}) \cdot P(B|\overline{A})} \cdot P(B|A) $$
        In unserem Fall erhalten wir
        \begin{eqnarray*}
          P(K^+|T^+) & = & \frac{P(K^+)}{P(K^+) \cdot P(T^+|K^+) + P(\overline{K^+}) \cdot P(T^+|\overline{K^+})} \cdot P(T^+|K^+) \\
                     & = & \frac{P(K^+)}{P(K^+) \cdot P(T^+|K^+) + P(K^-) \cdot P(T^+|K^-)} \cdot P(T^+|K^+) \\
        \end{eqnarray*}
        Alle benötigten Wahrscheinlichkeiten sind uns bekannt, bis auf $P(T^+|K^-)$.
        Aus der elementaren Mengenlehre folgt
        $$ (A \cap B) \cup (\overline{A} \cap B) = B $$
        $$ P(A \cap B) + P(\overline{A} \cap B) = P(B) $$
        Betrachte die Summe $P(T^+|K^-)+P(T^-|K^-)$. \\
        Es gilt nach der Definition der bedingten Wahrscheinlichkeit
        \begin{eqnarray*}
          P(T^+|K^-)+P(T^-|K^-) & = & \frac{P(T^+ \cap K^-)}{P(K^-)} + \frac{P(T^- \cap K^-)}{P(K^-)} \\
                                & = & \frac{P(T^+ \cap K^-) + P(T^- \cap K^-)}{P(K^-)} \\
                                & = & \frac{P(K^-)}{P(K^-)} \\
                                & = & 1 \\
          \Longrightarrow\quad P(T^+|K^-) & = & 1-P(T^-|K^-) \\
        \end{eqnarray*}
        Also gilt
        \begin{eqnarray*}
          P(K^+|T^+) & = & \frac{P(K^+)}{P(K^+) \cdot P(T^+|K^+) + P(K^-) \cdot P(T^+|K^-)} \cdot P(T^+|K^+) \\
                     & = & \frac{P(K^+)}{P(K^+) \cdot P(T^+|K^+) + (1-P(K^+)) \cdot (1-P(T^-|K^-))} \cdot P(T^+|K^+) \\
        \end{eqnarray*}
  \item Gegeben seien:
        \begin{itemize}
          \item Spezifizität $P(T^-|K^-)=0,97$
          \item Sensitivität $P(T^+|K^+)=0,997$
          \item Krankheitswahrscheinlichkeit $P(K^+)=0,0005$
        \end{itemize}
        Für die Wahrscheinlichkeit, mit der ein positiv diagnostizierter Patient tatsächlich mit HIV infiziert ist, ergibt sich
        \begin{eqnarray*}
          P(K^+|T^+) & = & \frac{P(K^+)}{P(K^+) \cdot P(T^+|K^+) + (1-P(K^+)) \cdot (1-P(T^-|K^-))} \cdot P(T^+|K^+) \\
                     & = & \frac{0,0005}{0,0005 \cdot 0,997 + (1-0,0005) \cdot (1-0,97)} \cdot 0,997 \\
                     & = & \frac{0,0005}{0,0005 \cdot 0,997 + 0,9995 \cdot 0,03} \cdot 0,997 \\
                     & \approx & 0,016353109059 = 1,6353109059 \% \\
        \end{eqnarray*}
\end{enumerate}

\section*{Aufgabe 4}
Es soll gelten
$$ P(\{X=k\}) := \binom{n}{k} \cdot p^k \cdot q^{n-k} $$
mit $q=1-p$ gilt
$$ P(\{X=k\}) := \binom{n}{k} \cdot p^k \cdot (1-p)^{n-k} $$
Nach Definition Erwartungswert gilt
$$ E(X) = \sum_{k \in X(S)} \binom{n}{k} \cdot p^k \cdot (1-p)^{n-k} \cdot k $$
Es muss gelten
$$ 0 \le k \le n $$
Als geschlossene Form ergibt sich
\begin{eqnarray*}
  E(X) & = & n \cdot p \cdot \frac{ (1-p)^n \cdot \left( 1+\frac{p}{1-p} \right)^n }{ (1-p) \cdot \left( 1+\frac{p}{1-p} \right) } \\
       & = & n \cdot p \cdot (1-p)^{n-1} \cdot \left( 1+\frac{p}{1-p} \right)^{n-1} \\
       & = & n \cdot p \cdot (1-p)^{n-1} \cdot \left( \frac{1}{1-p} \right)^{n-1} \\
       & = & n \cdot p \cdot \left( \frac{1-p}{1-p} \right)^{n-1} \\
       & = & n \cdot p \cdot 1^{n-1} \\
       & = & n \cdot p \\
\end{eqnarray*}

\section*{Aufgabe 5}
\lstset{language=C++,basicstyle=\small}
\lstinputlisting{b6_a5.cpp}

\end{document}