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

\newcommand{\ZETTELNUMMER}{4}
\newcommand{\ABGABEDATUM}{am 16. November 2016 im Tutorium}

\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{Der Lolli-Graph}{10 Punkte}

   Der \emph{Lolli-Graph} besteht aus $2n-1$ Knoten
    $\{1, \dots, 2n-1\}$. Die Knoten $\{1, \dots, n\}$ bilden
    einen vollst\"andigen Graphen mit $n$ Knoten. 
    Die Knoten $\{1, n+1, \dots, 2n-1\}$ bilden
    einen Pfad der L\"ange $n$, in dieser Reihenfolge. 
    Es gibt keine weiteren Kanten
    zwischen Knoten in $\{2, \dots, n\}$ und Knoten in 
    $\{n+1, \dots, 2n-1\}$. 

    Betrachten Sie den Random Walk auf dem Lolli-Graphen,
    der bei $1$ beginnt und in jedem Schritt zu einem zuf\"allig 
    gleichverteilten Nachbarn des aktuellen Knoten geht.
    Geben Sie eine m\"oglichst gute Sch\"atzung f\"ur die erwartete 
    Anzahl an Schritten an, bis der Random Walk den Knoten $2n-1$ erreicht.

\AUFGABE{Kuppeln}{20 Punkte}

In der Vorlesung haben Sie die Methode des Kuppelns (Couplings)
von Zufallsvariablen kennen gelernt. Wir betrachten ein 
weiteres Beispiel. 

Sei $n \in \N$. Wir haben
ein Kartenspiel mit $n$ paarweise verschiedenen Karten. 
Wir f\"uhren den folgenden Schritt aus: 
W\"ahle eine zuf\"allige Karte und bringe sie nach ganz oben. 
Wie oft m\"ussen wir dies wiederholen, bis das
Kartenspiel zuf\"allig gemischt ist?

Wir definieren dazu zwei Folgen $X_1, X_2, \dots$ und
$Y_1, Y_2, \dots$ von Zufallsvariablen. Die Werte
der Zufallsvariablen sind Permutationen der Menge $\{1, \dots, n\}$.
Die Zufallsvariablen sind auf einem gemeinsamen Wahrscheinlichkeitsraum
$\Omega$ definiert. Ein Elementarereignis $\omega \in \Omega$ besteht
aus einer zuf\"allig gleichverteilten Permutation $\sigma$ und
einer Folge $Z_1, Z_2, \dots$ von unabh\"angigen  gleichverteilten
Elementen aus $\{1, \dots, n\}$.

Wir setzen $X_1(\omega)$ auf die Ausgangspermutation des Kartenspiels,
und $Y_1(\omega)$ auf die zuf\"allige Permutation $\sigma$.
Sei $i \geq 1$, und sei $k$ das $Z_i$-te Element in
$X_i(\omega)$. Man erh\"alt $X_{i+1}(\omega)$, indem man in 
$X_i(\omega)$ das Element 
$k$ an die erste Stelle bringt.
Man erh\"alt  $Y_{i+1}(\omega)$, indem man in $Y_i(\omega)$ das 
Element $k$ an die erste Stelle bringen.
Achtung: Wir benutzen beide male das gleiche Element.

\begin{enumerate}
  \item Zeigen Sie: F\"ur jede feste Permutation $\tau$ und f\"ur
    jedes $i \geq 1$ gilt: $\Pr[Y_i = \tau] = 1/n!$.
  \item Zeigen Sie: Die Verteilung der $X_i$ entspricht der
     Verteilung, die unser Algorithmus zum Kartenmischen erzeugt.
  \item Begr\"unden Sie: Wenn $X_i = Y_i$ ist, dann ist
    das Kartenspiel gemischt.
  \item Zeigen Sie: Die L\"ange des l\"angsten gemeinsamen Pr\"afix 
     von $X_i$ und $Y_i$ ist monoton wachsend mit $i$.
  \item  Zeigen Sie: Wenn die L\"ange des l\"angsten gemeinsamen Pr\"afix 
    von 
    $X_i$ und $Y_i$ genau $k$ ist, so ist die Wahrscheinlichkeit,
    dass sie sich in einem Schritt erh\"oht, genau $(n-k)/n$.
    Folgern Sie: Die erwartete Anzahl an Schritten, bis sich
    das Pr\"afix verl\"angert, ist $n/(n-k)$.
  \item Wie viele Schritte ben\"otigt man im Erwartungswert,
    bis das Kartenspiel gemischt ist?
\end{enumerate}
\end{description}

\end{document}
