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

\newcommand{\ZETTELNUMMER}{5}
\newcommand{\ABGABEDATUM}{bis zum 21. November 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{Kullback-Leibler Divergenz} {10 Punkte}

\begin{enumerate}
\item Eine Funktion $f: \R \rightarrow \R$
  hei\ss{}t \emph{konvex}, falls f\"ur alle
  $x, y \in \R$ und $\lambda \in [0,1]$ gilt:
  \[
    f\big(\lambda x +(1-\lambda) y\big) \leq 
    \lambda f(x) + (1-\lambda) f(y).
  \]
  
  Beweisen Sie die \emph{Jensensche Ungleichung}. Ist $f: \R \rightarrow
  \R$ konvex, so gilt f\"ur alle $n \in \N$ und f\"ur alle 
  $x_1, \dots, x_n \in \R$ und $\lambda_1, \dots, \lambda_n \in [0,1]$
  mit $\sum_{i = 1}^n \lambda_i = 1$:
  \[
  f\left(\sum_{i=1}^{n} \lambda_i x_i\right) 
     \leq \sum_{i=1}^{n} \lambda_i f(x_i).
  \]
\item 
  Seien $a_1, \dots, a_n, b_1, \dots, b_n \in \R$ mit
  $a_i, b_i \geq 0$, f\"ur $i = 1, \dots, n$.
  Sei $a = \sum_{i = 1}^n a_i$ und $b = \sum_{i = 1}^n b_i$
  Beweisen Sie die \emph{Log-Summen-Ungleichung:}
  \[
    \sum_{i = 1}^n a_i \log \frac{a_i}{b_i} \geq a \log \frac{a}{b}.
  \]

  \emph{Hinweis:} Benutzen Sie die Jensensche Ungleichung f\"ur 
    $f(x) = x \log x$.

\item Zeigen Sie: F\"ur alle Wahrscheinlichkeitsverteilungen 
$P$ und $Q$ auf $n$
  Elementen gilt $D_\text{KL}(P \parallel Q) \geq 0$.
\end{enumerate}

\AUFGABE{Alternativer Beweis der Chernoff-Schranke} {10 Punkte}

In dieser Aufgabe betrachten wir Chv{\'a}tals Beweis f\"ur 
eine Variante der Chernoff Schranke. Sei $B(n,p)$ die 
Zufallsvariable, welche die Erfolge in einer Folge von 
$n$ unanbh\"angigen Bernoulli Versuchen mit 
Erfolgswahrscheinlichkeit $p$ z\"ahlt.

\begin{enumerate}
\item Zeigen Sie: f\"ur alle $x \geq 1$ ist
\[
\Pr[B(n,p) \geq k] \leq \sum_{i = 0}^{n} 
\binom{n}{i} p^i (1-p)^{n-i} x^{i-k}.
\]
\item Benutzen Sie den Binomialsatz, um eine 
geschlossene obere Schranke f\"ur
 die Wahrscheinlichkeit $\Pr[B(n,k) \geq k]$ zu erhalten.
\item Finden Sie den eine bestm\"ogliche Wahl f\"ur $x$.
\item Folgern Sie: f\"ur $t \geq 0$ gilt
\[
\Pr[B(n,p) \geq (p+t)n] \leq \left( \left(\frac{p}{p+t}\right)^{p+t}
\left(\frac{1-p}{1-p-t}\right)^{1-p-t}\right)^n.
\]
  Interpretieren Sie Ihr Ergebnis.
\end{enumerate}

\AUFGABE{Laufzeit eines FPRAS}{10 Punkte}

Nehmen Sie an, wir \"andern die Definition von FPRAS leicht ab und fordern
anstatt einer Laufzeit, die polynomiell in $1/\varepsilon$ ist, eine Laufzeit,
die polynomiell in $\log(1/\varepsilon)$ sein muss. 
\begin{enumerate}
\item Zeigen Sie, dass aus der Existenz eines solchen FPRAS f\"ur ein \#P 
vollst\"andiges Problem folgt, dass wir jedes Problem in \#P in Polynomialzeit
l\"osen k\"onnen.

\item Was w\"urde das f\"ur die Klassen P und NP bedeuten?
\end{enumerate}


\end{description}

\end{document}