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

\newcommand{\ZETTELNUMMER}{14}
\newcommand{\ABGABEDATUM}{bis zum 6. Februar 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

\noindent
Dies ist das letzte Aufgabenblatt.
\vskip 0.5cm
\noindent


\begin{description}

\AUFGABE{$st$-Pfad in ungerichteten Graphen}{10 Punkte}

Beweisen Sie detailliert, dass sich das $st$-Pfad-Problem 
in ungerichteten Graphen mit einem Monte-Carlo
Algorithmus l\"osen l\"asst, der logarithmischen
Platzbedarf und polynomielle  Laufzeit ben\"otigt.

\AUFGABE{Random Walks in allgemeinen Graphen}{20 Punkte}

Sei $G = (V, E)$ ein einfacher, zusammenh\"angender ungerichteter
Graph mit $n$ Knoten. Sei $V = \{1, \dots, n\}$, und f\"ur
$i \in V$, sei  $d_i$ der Grad des Knoten $i$.

Sei $A$ die 
Adjazenzmatrix von $G$, d.h., $A_{ij} = 1$, falls 
$\{i,j\} \in E$ ist, und $A_{ij} = 0$, sonst.
Sei weiterhin $D$ die Diagonalmatrix 
mit $D_{ii} = 1/d_i$, f\"ur $i = 1, \dots, n$ und
$D_{ij} = 0$, f\"ur $i \neq j$. F\"ur $\alpha \in \R$,
sei $D^\alpha$ die Diagonalmatrix mit den Eintr\"agen
$(D^\alpha)_{ij} = (D_{ij})^\alpha$, f\"ur 
$i, j = 1, \dots, n$.
\begin{enumerate}
\item  
Die Matrix $M = DA$ hei\ss{}t \emph{Random-Walk-Matrix}
von $G$.
Fixieren Sie $i, j \in V$ und $t \in \N$.
Betrachten Sie das folgende Zufallsexperiment: Wir beginnen
in Knoten $i$. In jedem Schritt w\"ahlen wir 
zuf\"allig gleichverteilt eine inzidente Kante des aktuellen
Knoten. Wir folgen dieser Kante zum benachbarten Knoten. Dies wiederholen
wir $t$ mal. Sei $p_{ij}^t$ die Wahrscheinlichkeit, dass
wir im Knoten $j$ aufh\"oren.

Zeigen Sie: Es ist $p_{ij}^t = (M^t)_{ij}$.

\item
Sei $N = D^{1/2}AD^{1/2}$. Zeigen Sie: Die Matrix $N$ verf\"ugt \"uber
eine Orthonormalbasis $v_1, \dots, v_n$ von Eigenvektoren. 
Au\ss{}erdem ist
der Vektor $v_1$ mit $v_{1i} = \sqrt{d_i/2|E|}$, f\"ur $i = 1, \dots, n$, 
Eigenvektor zum Eigenwert $1$.

Aus dem Satz von Perron-Frobenius folgt dann: der
Eigenwert $1$ ist einfach und alle Eigenwerte haben
Betrag h\"ochstens $1$. Au\ss{}erdem ist $-1$ genau dann Eigenwert, wenn
$G$ bipartit ist.

\item Zeigen Sie: $M$ ist diagonalisierbar
und l\"asst sich schreiben als
\[
M = \sum_{k = 1}^{n} \lambda_k D^{1/2}v_k v_k^TD^{-1/2},
\]
wobei $\lambda_1, \dots, \lambda_n$ und $v_1, \dots, v_n$ die
Eigenwerte und Eigenvektoren von $N$ sind. Dabei sei die 
Nummerierung so gew\"ahlt, dass $\lambda_1 = 1$ und
$|\lambda_1| \geq |\lambda_2| \geq \dots \geq |\lambda_n|$ ist.

\emph{Hinweis}: F\"uhren Sie $M$ auf $N$ zur\"uck. Verwenden Sie
die Darstellung von $N$ als Diagonalmatrix.

\item Sei $p_{ij}^t$ wie in (a).
Zeigen Sie:
\[
p_{ij}^t = 
\frac{d_j}{2|E|} + \sqrt{\frac{d_j}{d_i}}\sum_{k = 2}^n 
v_{ki}v_{kj}\lambda_k^t 
\]
und
\[
\left|p_{ij}^t - \frac{d_j}{2|E|}\right|  \leq 
\sqrt{\frac{d_j}{d_i}}|\lambda_2|^t.
\]

\emph{Hinweis}:
Sie d\"urfen verwenden:
Es ist $\sum_{k=1}^n v_{ki} v_{kj} = 1$, falls $i = j$, und
$\sum_{k=1}^n v_{ki} v_{kj} = 0$, sonst.
Au\ss{}erdem gilt die Cauchy-Schwarz Ungleichung:
\[\sum_{i = 1}^{n}|a_ib_i| \leq 
\sqrt{\sum_{i = 1}^n a_i^2 \sum_{i=1}^n b_i^2}.\]

\item Was k\"onnen Sie \"uber die Konvergenz von Random Walks
auf $G$ sagen?
\end{enumerate}

\end{description}
\end{document}
