\documentclass[11pt, a4paper]{article}

\usepackage{ngerman}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage[latin1]{inputenc}
\usepackage[pdftex,             
            pdfpagelabels,
            colorlinks=true,           % Links nicht farbig umrahmen, sondern als farbigen Text
            urlcolor=colorBlue,        % Farbe für externe Verweise, \href{...}{...}
            filecolor=colorGreen,      % Farbe für lokale Verweise, \href{...}{...}
            linkcolor=colorRed,        % Farbe für interne Verweise, \ref{...} und \pageref{...}
            pdftitle={},
            pdfauthor={Jan Hendrik Dithmar},
            pdfsubject={},
            pdfkeywords={},
            pdfpagemode=None,          % Navigationsleiste beim Start ausblenden 
            % pdfpagemode=UseThumbs,     % Thumbnails beim Start anzeigen
            % pdfpagemode=UseOutlines,   % Lesezeichen beim Start anzeigen
            % pdfpagemode=FullScreen,    % im Vollbildmodus starten
            % pdfstartpage=2,            % spezielle Startseite festlegen
            bookmarks,
            % bookmarksopen,             % alle Lesezeichen aufklappen
            % bookmarksopenlevel=2,      % Tiefe, bis zu welcher die Lesezeichen aufgeklappt werden sollen
            bookmarksnumbered,         % Lesezeichen nummerieren
            pdfstartview=FitH,         % Seite auf voller Breite anzeigen
            pagebackref
           ]{hyperref}

\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{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}

\thispagestyle{empty}

\title{Programmierung II - Übungsblatt 8 \\
	Übungsgruppe Do 14-16 \\	
	Andreas Augustin}
\author{Jan Hendrik Dithmar (Matrikelnummer 2031259) \\
	Dirk Heine (Matrikelnummer 2030941) \\
	Andreas Glitsch (Matrikelnummer 2026130)}
\date{}

\maketitle

\newpage

\section*{Aufgabe 1}
Zu zeigen:
$$P(\bigcap_{i=1}^n A_i) = P(A_1) \cdot \prod_{i=2}^n P(A_i | \bigcap_{j=1}^{i-1} A_j)$$
Beweis durch vollständige Induktion über $n$:
\begin{itemize}
	\item Induktionsanfang: $n=2$
		\begin{eqnarray*}
			P(\bigcap_{i=1}^2 A_i) & = & P(A_2 \cap A_1) \\
			& = & P(A_1) \cdot \frac{P(A_2 \cap A_1)}{P(A_1)} \\
			& = & P(A_1) \cdot P(A_2|A_1) \\
			& = & P(A_1) \cdot \prod_{i=2}^2 P(A_i | \bigcap_{j=1}^{i-1}A_j)
		\end{eqnarray*}
	\item Induktionsbehauptung: Es gilt
		$$P(\bigcap_{i=1}^n A_i) = P(A_1) \cdot \prod_{i=2}^n P(A_i | \bigcap_{j=1}^{i-1} A_j)$$
	\item Induktionsschritt: $n \leadsto n+1$
	\item Induktionsbeweis:
		\begin{eqnarray*}
			P(\bigcap_{i=1}^{n+1} A_i) & = & P(A_{n+1} \cap \bigcap_{i=1}^n A_i) \\
			& = & P(\bigcap_{i=1}^n A_i) \cdot \frac{P(A_{n+1} \cap \bigcap_{i=1}^n A_i)}{P(\bigcap_{i=1}^n A_i)} \\
			& = & P(\bigcap_{i=1}^n A_i) \cdot P(A_{n+1} | \bigcap_{i=1}^n A_i) \\
			& \stackrel{IA}{=} & P(A_1) \cdot \prod_{i=2}^n P(A_i | \bigcap_{j=1}^{i-1} A_j) \cdot P(A_{n+1} | \bigcap_{j=1}^n A_j) \\
			& = & P(A_1) \cdot \prod_{i=2}^{n+1} P(A_i | \bigcap_{j=1}^{i-1} A_j)
		\end{eqnarray*}
\end{itemize} \QED

\section*{Aufgabe 3}
Seien $A_1, A_2, A_3, A_4 \subset \Omega$ Ereignisse, zwischen denen folgende Beziehungen bestehen:
\begin{eqnarray}
	A_1 \cap A_4 = \emptyset & \AND & A_2 \cap A_4 = \emptyset \\
	A_3 & = & (A_1 \cap A_2) \cup A_4 \\
	P(A_1) = \frac{1}{4} \AND P(A_2) = \frac{1}{4} & \AND & P(A_1 \cap A_2) = \frac{1}{64} \AND P(A_4) = \frac{15}{64}
\end{eqnarray}
Dann gilt:
\begin{eqnarray*}
	\text{Aus } (2) \Rightarrow P(A_3) & = & P(A_1 \cap A_2) + P(A_4) - P((A_1 \cap A_2) \cap A_4) \\
	P(A_3) & = & P(A_1 \cap A_2) + P(A_4) - P(\underbrace{A_1 \cap (\underbrace{A_2 \cap A_4}_{= \emptyset})}_{= \emptyset}) \\
	P(A_3) & = & \frac{1}{64} + \frac{15}{64} - 0 = \frac{1}{4} \quad \quad \quad (I) \\[0.5cm]
	A_1 \cap A_3 & \stackrel{(2)}{=} & A_1 \cap ((A_1 \cap A_2) \cup A_4) \\
	& = & (A_1 \cap (A_1 \cap A_2)) \cup (\underbrace{A_1 \cap A_4}_{\stackrel{(1)}{=} \emptyset}) \\
	& = & A_1 \cap A_2 \\
	\Rightarrow P(A_1 \cap A_3) & = & P(A_1 \cap A_2) \stackrel{(3)}{=} \frac{1}{64} \quad \quad \quad (II) \\[0.5cm]
	A_2 \cap A_3 & \stackrel{(2)}{=} & A_2 \cap ((A_1 \cap A_2) \cup A_4) \\
	& = & (A_2 \cap (A_1 \cap A_2)) \cup (\underbrace{A_2 \cap A_4}_{\stackrel{(1)}{=} \emptyset}) \\
	& = & A_1 \cap A_2 \\
	\Rightarrow P(A_2 \cap A_3) & = & P(A_1 \cap A_2) \stackrel{(3)}{=} \frac{1}{64} \quad \quad \quad (III) \\[0.5cm]
	A_1 \cap A_2 \cap A_3 & \stackrel{(2)}{=} & (A_1 \cap A_2) \cap ((A_1 \cap A_2) \cup A_4) \\
	& = & A_1 \cap A_2, \quad \text{da } A_1 \cap A_2 \subset (A_1 \cap A_2) \cup A_4 \text{ ist} \\
	\Rightarrow P(A_1 \cap A_2 \cap A_3) & = & P(A_1 \cap A_2) = \frac{1}{64} \quad \quad \quad (IV)
\end{eqnarray*}
Es gilt:
\begin{enumerate}[(a)]
	\item
		\begin{eqnarray*}
			P(A_1) \cdot P(A_2) \cdot P(A_3) & \stackrel{(3), (I)}{=} \frac{1}{4} \cdot \frac{1}{4} \cdot \frac{1}{4} = \frac{1}{64} \\
			& \stackrel{(IV)}{=} P(A_1 \cap A_2 \cap A_3)
		\end{eqnarray*}
		Also:
		$$P(\bigcap_{i=1}^3 A_i) = \prod_{i=1}^3 P(A_i)$$
	\item
		\begin{eqnarray*}
			P(A_1) \cdot P(A_2) & \stackrel{(3)}{=} & \frac{1}{4} \cdot \frac{1}{4} = \frac{1}{16} \ne \frac{1}{64} \stackrel{(3)}{=} P(A_1 \cap A_2)
		\end{eqnarray*}
		Also:
		$$P(A_1 \cap A_2) \ne P(A_1) \cdot P(A_2) \text{, d.h. } A_1 \text{ und } A_2 \text{ sind abhängig}$$
	\item
		\begin{eqnarray*}
			P(A_1) \cdot P(A_3) & \stackrel{(3), (I)}{=} \frac{1}{4} \cdot \frac{1}{4} = \frac{1}{16} \ne \frac{1}{64} \stackrel{(II)}{=} P(A_1 \cap A_3)
		\end{eqnarray*}
		Also:
		$$P(A_1 \cap A_3) \ne P(A_1) \cdot P(A_3) \text{, d.h. } A_1 \text{ und } A_3 \text{ sind abängig}$$
	\item
		\begin{eqnarray*}
			P(A_2) \cdot P(A_3) & \stackrel{(3), (I)}{=} \frac{1}{4} \cdot \frac{1}{4} = \frac{1}{16} \ne \frac{1}{64} \stackrel{(III)}{=} P(A_2 \cap A_3)
		\end{eqnarray*}
		Also:
		$$P(A_2 \cap A_3) \ne P(A_2) \cdot P(A_3) \text{, d.h. } A_2 \text{ und } A_3 \text{ sind abhängig}$$
\end{enumerate}
Insgesamt: \\
Die Regel (a)
$$P(\bigcap_{i=1}^3 A_i) = \prod_{i=1}^3 P(A_i)$$
bietet also keine Gewähr dafür, dass die Ereignisse $A_1,A_2,A_3$ auch paarweise unabhängig sind (wegen (b), (c) und (d)). \QED

\section*{Aufgabe 4}

$S$ ist die Anzahl aller möglichen Elementarereignisse. \\
$A$ ist die Wahrscheinlichkeit, dass das Los mit der Nummer 1111111 gezogen wird. \\
$B$ ist die Wahrscheinlichkeit, dass das Los mit der Nummer 1234567 gezogen wird. \\
\begin{eqnarray*}
	|S| & = & 70 \cdot 69 \cdot 68 \cdot 67 \cdot 66 \cdot 65 \cdot 64 = 6041824588800 \\
	|A| & = & 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 7! = 5040 \\
	|B| & = & 7 \cdot 7 \cdot 7 \cdot 7 \cdot 7 \cdot 7 \cdot 7 = 7^7 = 823543 \\
	P(A) & = & \frac{5040}{6041824588800} = 8,34185 \cdot 10^{-10} \\
	P(B) & = & \frac{823543}{6041824588800} = 1,36307 \cdot 10^{-7}
\end{eqnarray*}
Quotient: $$\frac{P(A)}{P(B)} = 0,0061198990216661425086486072979796 \approx 6,119899 \cdot 10^{-3}$$
Interpretation: Die Lotterie ist unfair, da die Wahrscheinlichkeiten der Elementarereignisse nicht gleich sind.

\section*{Aufgabe 5}
\subsection*{Chaining}

\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
\hline
 & $\downarrow$ & $\downarrow$ & $\downarrow$ & & & & $\downarrow$ \\
\hline
 & 337 & 442 & 523 & & & & 423 \\
\hline
 & $\downarrow$ & $\downarrow$ & & & & & \\
\hline
 & 353 & 394 & & & & & \\
\hline
 & $\downarrow$ & & & & & & \\
\hline
 & 561 & & & & & & \\
\hline
\end{tabular}
\\

\subsection*{Linear probing}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
\hline
 & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ \\
\hline
 & 561 & 353 & 523 & 394 & 442 & 337 & 423 \\
\hline
\end{tabular}
\\

\subsection*{quadratic probing}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
\hline
 & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ \\
\hline
 & 561 & 353 & 523 & 442 & 337 & 394 & 423 \\
\hline
\end{tabular}

\subsection*{Double hashing mit $h_2(x) = x \mod 5$}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
\hline
 & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ \\
\hline
 & 561 & 337 & 523 & 353 & 442 & 394 & 423 \\
\hline
\end{tabular}

\end{document}
