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

\newcommand{\ZETTELNUMMER}{7}
\newcommand{\ABGABEDATUM}{bis zum 5. 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{Alternative Definition eines FPAUS}{10 Punkte}

Eine allgemeine Definition von FPAUS ist folgenderma\ss{}en.
Gegeben  eine Familie von endlichen Wahrscheinlichkeitsr\"aumen
$(\Omega_x)_{x \in \{0,1\}^*}$ und eine Konstante $c > 0$,
so dass f\"ur alle $x \in \{0,1\}^*$ und f\"ur alle
$\omega \in \Omega_x$ gilt, dass wir $\omega$ eindeutig mit
$|x|^c$ Bits darstellen k\"onnen.

Ein FPAUS f\"ur $(\Omega_x)_{x \in \{0,1\}^*}$ ist ein randomisierter Algorithmus,
der bei Eingabe $x \in \{0, 1\}^*$ und $\eps > 0$ f\"ur
$\text{poly}(|x|, \log(1/\eps))$ Schritte l\"auft,
und dann ein zuf\"alliges $\omega \in \Omega_x$ liefert,
so dass f\"ur alle $S \subseteq \Omega_x$ gilt:
\[
  \left|\Pr[\omega \in S] - \frac{|S|}{|\Omega_x|}\right| \leq \eps.
\]

Eine alternative Definition geht so:
Ein FPAUS' f\"ur $(\Omega_x)_{x \in \{0,1\}^*}$ ist ein randomisierter Algorithmus,
der bei Eingabe $x \in \{0, 1\}^*$ und $\eps > 0$ f\"ur
$\text{poly}(|x|, \log(1/\eps))$ Schritte l\"auft,
und dann ein zuf\"alliges $\omega \in \Omega_x$ liefert,
so dass f\"ur alle $\sigma \in \Omega_x$ gilt:
\[
  \frac{\left|\Pr[\omega = \sigma] - 1/|\Omega_x|\right|}{1/|\Omega_x|} \leq \eps.
\]

Zeigen Sie, dass jedes FPAUS' auch ein FPAUS ist. Was k\"onnen
Sie \"uber die andere Richtung sagen?

\emph{Hinweis}: Zeigen Sie zun\"achst, dass
\[
\max_{S \subseteq \Omega_x} \left|\Pr[ \omega \in S] - \frac{|S|}{|\Omega_x|}\right| =
  \frac{1}{2} \sum_{\sigma \in \Omega_x} \left|\Pr[ \omega = \sigma] - \frac{1}{|\Omega_x|}\right|
\]
ist.
\AUFGABE{Lov\'asz Local Lemma}{10 Punkte}

\begin{enumerate}
\item
Beweisen Sie die allgemeine Form des Lov\'asz Local Lemmas:
Gegeben $n$ Ereignisse $E_1, \dots, E_n$ und ein
Abh\"angigkeitsgraph $G = (\{1, \dots, n\}, E)$ f\"ur diese Ereignisse.
Angenommen, es gibt Zahlen $x_1, \dots, x_n \in [0,1)$, so 
das f\"ur $i = 1, \dots, n$ gilt:
\[
\Pr[E_i] \leq x_i  \prod_{j : \{i,j\} \in E} (1-x_j).
\]
Dann ist
\[
\Pr\left[\bigcap_{i = 1}^n \overline{E_i}\right] 
\geq \prod_{i = 1}^{n} (1-x_i).
\]

\emph{Hinweis}:
  Zeigen Sie durch Induktion: F\"ur $i = 1, \dots, n$ und f\"ur alle
  $S \subseteq \{1, \dots, n\} \setminus \{i\}$ gilt:

\[
  \Pr\left[E_i \mid \bigcap_{j \in S} \overline{E_j}\right] \leq x_i.
\]
\item
Folgern Sie aus (a) die symmetrische Version des Local Lemmas aus 
der Vorlesung.
\end{enumerate}

\AUFGABE{Anwendung des Lov\'asz Local Lemmas}{10 Punkte}

Sei $V$ eine endliche Menge und $E \subseteq 2^V$ eine 
Teilmenge der Potenzmenge von $V$. Wir nennen $H = (V, E)$
einen \emph{Hypergraph}. Der Hypergraph $G$ hei\ss{}t genau dann \emph{zweif\"arbbar},
eine Funktion $\chi: V \rightarrow \{0, 1\}$ existiert,
so dass f\"ur alle Hyperkanten $e \in E$ gilt:
$\chi(e) = \{0, 1\}$.

Nehmen Sie an, dass jede Kante von $H$ mindestens $k$ Elemente besitzt und
dass jede Kante einen nichtleeren Schnitt mit h\"ochstens 
$d$ anderen Kanten hat. Finden sie eine m\"oglichst gute Beziehung zwischen
$k$ und $d$, die garantiert, dass $H$ zweif\"arbbar ist.
\end{description}

\end{document}
