\documentclass[a4paper,twoside,12pt]{article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts,amstext}
\usepackage{amsmath}
\usepackage{german}
\usepackage{fullpage}

\newcommand{\ZETTELNUMMER}{8}
\newcommand{\ABGABEDATUM}{bis zum 12. Dezember 2016, 12 Uhr, in den
Briefkasten neben Raum 111}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Aufgabe~\arabic{AUFGNR}]\stepcounter{AUFGNR} #1\hfill\emph{#2}}


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\eps}{\varepsilon}
\newcommand{\E}{\mathbf{E}}
\renewcommand{\Pr}{\mathbf{Pr}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\half}[1]{\frac{#1}{2}}



\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{(\roman{enumii})}


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Aufgabenblatt zur Vorlesung

\smallskip
\noindent
\large
\textbf{Randomisierte Algorithmen}\hfill WiSe 2016/17 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Paul Seiferth, Max Willert

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm

\begin{description}
\AUFGABE{Unabh\"angigkeit}{10 Punkte}

Seien $E_1, \dots, E_n, F$ Ereignisse.
Zeigen Sie: Ist $F$ von $E_1, \dots, E_n$
unabh\"angig, so gilt auch f\"ur jede Teilmenge 
$\mathcal{E} \subseteq \{ E_1, \dots, E_n, \overline{E_1}, \dots, \overline{E}_n\}$
mit $\Pr\left[\bigcap_{E \in \mathcal{E}} E \right] > 0$, dass
\[
\Pr[F] = \Pr\left[F \left\vert \bigcap_{E \in \mathcal{E} }E\right.\right]
\]
ist.

\AUFGABE{Das uniforme Kodierungslemma}{10 Punkte}

Sei $S$ eine endliche Menge. Ein \emph{pr\"afixfreier
Code} f\"ur $S$ ist eine Funktion 
$C: S \rightarrow \{0,1\}^*$, so dass f\"ur alle
$s, t \in S$ gilt: $C(s)$ ist kein Pr\"afix von $C(t)$ und
$C(t)$ ist kein Pr\"afix von $C(s)$.

\begin{enumerate}
  \item  Sei $C: S \rightarrow \{0,1\}^*$ und
    $\ell \in \N$. Zeigen Sie: 
    \[
      \left| \{ s \in S \mid |C(s)| \leq \ell\}\right| \leq 2^\ell.
    \]
  \item Sei $C : S \rightarrow \{0,1\}^*$ ein pr\"afixfreier Code,
    und sei $k \in \N$. Setze 
    \[
      B = \{ s \in S \mid |C(s)| \leq \log |S| - k\}.
    \]
    Beweisen Sie das \emph{uniforme Kodierungslemma}:
    Sei $s \in S$ zuf\"allig gleichverteilt. Dann gilt
    \[
      \Pr[s \in B] \leq 2^{-k}.
    \]
\end{enumerate}

\AUFGABE{L\"aufe in bin\"aren Zeichenfolgen}{10 Punkte}

Sei $n \in \N$ und sei $x \in \{0, 1\}^n$ ein 
bin\"ares Wort der L\"ange $n$. Ein \emph{Lauf
der L\"ange} $k$ in $x$ ist eine zusammenh\"ange
Teilfolge von $k$ Einsen in $x$, f\"ur $k \in \N$.

Benutzen Sie das uniforme Kodierungslemma, um eine
m\"oglichst gute obere Schranke f\"ur das Ereignis
zu erhalten, dass ein zuf\"allig gleichverteiltes 
bin\"ares Wort der L\"ange $n$ einen Lauf der
L\"ange $\lceil \log n \rceil + s + 1$ enth\"alt,
f\"ur $s \in \N$.
\end{description}

\end{document}
