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

\newcommand{\ZETTELNUMMER}{12}
\newcommand{\ABGABEDATUM}{bis zum 23. Januar 2017, 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}}
\DeclareMathOperator{\NN}{NN}
\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator{\VD}{VD}
\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
\noindent


\begin{description}
\AUFGABE{Bedingte Erwartungswerte und Martingale}{10 Punkte}

Zeigen Sie:
\begin{enumerate}
  \item Seien $X, Y$ Zufallsvariablen.
      Dann gilt $\E[X \cdot Y] = \E[X \cdot \E[Y \mid X]]$.
  \item  Sei $X_1, X_2, \dots$ ein Martingal.
    Dann gilt $\E[X_i] = \E[X_1]$ f\"ur alle $i \geq 0$.
  \item Sei $X_1, X_2, \dots$ ein Martingal
    bez\"uglich $Y_1, Y_2, \dots$. Dann ist
    $X_1, X_2, \dots$ ein Martingal.
\end{enumerate}

\AUFGABE{Lipschitz-Funktionen und Bedingte Erwartungswerte}{10 Punkte}

In der Vorlesung haben wir folgendes bewiesen:
Sei $f: \R^n \rightarrow R$ eine $c$-Lipschitz-Funktion 
und seien $X_1, \dots, X_n$ unabh\"angige Zufallsvariablen.
Setze \[ Z_0 = \E[f(X_1, \dots, X_n)] \] und
\[ Z_i = \E[f(X_1, \dots, X_n) \mid X_1, \dots, X_i], \]
f\"ur
$i = 1, \dots, n$. Dann gilt $|Z_i - Z_{i-1}| \leq c$,
f\"ur $i = 1, \dots, n$.

Zeigen Sie, dass diese Aussage im Allgemeinen nicht gilt,
wenn die $X_i$ nicht unabh\"angig sind.

\AUFGABE{Azuma-Ungleichung}{10 Punkte}

Beweisen Sie mit dem Kantenenth\"ullungs-Martingal und
der Azuma-Ungleichung, dass die F\"arbungszahl des
Erd\H{o}s-Renyi-Graphen $G_{n,p}$ stark um ihren Erwartungswert
konzentriert ist.

Dabei ist die \emph{F\"arbungszahl} die minimale Anzahl von Farben,
mit der man die Knoten von $G_{n,p}$ f\"arben kann, so dass
bei keiner Kante die Endpunkte gleich gef\"arbt sind.
\end{description}
\end{document}
