\documentclass[11pt]{article}
\input{/Users/nicolascurien/Dropbox/Macros-bibli/macros-english2}
\newcommand{\pp}{\ensuremath{\sqsubset}}
\newcommand{\ppld}{\ensuremath{\sqsubset_{LD}}}
\newcommand{\rev}{\ensuremath{\textrm{\textup{rev}}}}
\newtheorem{exo}{Exercise}[section]
\newtheorem{theorem}{Theorem}[section]
\newtheorem{prperty}[theorem]{Property}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{exe}[theorem]{Example}
\newtheorem{open}{Open Question}
\newcommand{\rf}{\ensuremath{\mathfrak{R}}}
\newcommand{\m}{\mathcal{M}}
\newcommand{\T}{\mathcal{T}}
\renewcommand{\P}[1]{\mathbb{P}\left[#1\right]}
\newtheorem{rek}[theorem]{Remark}
\renewcommand{\sh}{\ensuremath{\textrm{\textup{sh}}}}
\renewcommand{\rg}{\ensuremath{\cyclearrowright}}
\usepackage{enumerate}
\def\llbracket{[\hspace{-.10em} [ }
\newcommand{\e}{\mbox{e}\hspace{-.34em}\mbox{\i}}
\renewcommand{\e}{\mathfrak{e}}
\def\rrbracket{ ] \hspace{-.10em}]}
\usepackage{amsmath}
%\usepackage{palatino}
\title{Metric Geometry}
\date{}
\author{}
\begin{document}
%\maketitle
\setcounter{section}{2}
\section{Stick-Breaking Construction of the CRT}
\begin{exo}[Aldous-Broder Algorithm and stick breaking construction of the CRT.] Given a finite  connected graph $G=(V,E)$, how can we sample a uniform spanning tree of $G$ ? In general it is hard to list all the spanning trees of a given graph. However, there exist stochastic algorithms that sample from this set without knowing it. The algorithm we describe here is due to Aldous \& Broder.\\
\textit{Recipe:} Let $G=(V,E)$ be a connected graph and $v_{0}\in V$ a vertex. We perform a simple random walk on $G$ starting from $v_{0}$. For any $v \in G$, we denote by $T_{v}$ the hitting time of $v$ by the walk and by $E_{T_{v}}$ the edge traversed by the walk just before it hits $v$. 
\begin{enumerate}
\setcounter{enumi}{0}
\item Show that the set of edges $\big \{ E_{T_{v}}, v \in V \backslash \{v_{0}\}\big\},$ defines a spanning tree of $G$.
\end{enumerate}
\begin{theorem} This (unrooted) spanning tree is uniform over the set of all spanning trees of $G$.
\end{theorem}
Now, we will focus on the case of $G= \mathbb{K}_{n}$ the complete graph over $n$ vertices \footnote{We have seen (tutorial 1) that the number of spanning trees of $\mathbb{K}_{n}$ is $n^{n-2}$}. Denote by $(X_{k})_{k\geq 0}$ the simple random walk on $\mathbb{K}_{n}$ (the dependence in $n$ is implicit). That is $(X_{k})_{k\geq 0}$ is a sequence of independent variables uniformly distributed over the vertices of $\mathbb{K}_{n}$. We introduce the first time the walk hits its past and the corresponding vertex $$T_{1}^{(n)}= \inf\big\{ k \geq 1 : X_{k} \in \{ X_{0}, ... , X_{k-1}\}\big\} \mbox{ and } P_{1}^{(n)}= X_{T_{1}^{(n)}}.$$ We define $T_{2}^{(n)} = \inf\{ k > T_{1}^{(n)}: X_{k} \in \{ X_{0}, ... , X_{k-1}\}\}$, $P_{2}^{(n)}= X_{T_{2}^{(n)}}$ ... by induction. \\We also recall ``the birthday paradox'': Assume that a year has $n$ days and that people are born equally likely each day of the year. Then among $\sqrt{n}$ people chosen at random two of them are born the same day with a big probability.
\begin{enumerate}
\setcounter{enumi}{1}
\item What is the rough order of $T_{1}^{(n)}$ as $n \to \infty$ (don't look below !).
\item Show that $n^{-1/2}T_{1}^{(n)}$ converges in distribution as $n \to \infty$ and identify the limit law.
\item More generally, show that for any $k \in \mathbb{Z}_{+}$, $$n^{-1}\left( \frac{(T_{1}^{(n)})^2}{2}, \frac{(T_{2}^{(n)})^2}{2}, ... ,\frac{(T_{k}^{(n)})^2}{2}\right),$$ converges in distribution towards the first $k$ points of a standard Poisson point process  on $\mathbb{R}_{+}$ with intensity $1$.
\item Show that for any $k\in \mathbb{Z}_{+}$, conditionally on $(T_{1}^{(n)}, ... ,T_{k}^{(n)}, X_{0},X_{1}, ... , X_{T_{k}-1})$ the point $P_{k}^{(n)}$ is uniformly distributed over $\{ X_{0}, ... , X_{T_{k}^{(n)}-1}\}$.
\item Describe the continuous limit of the construction of the spanning tree over $\mathbb{K}_{n}$.

\end{enumerate}
\end{exo}

\begin{exo} * Prove Theorem 3.1.\,in the case of the complete graph.
\end{exo}

\clearpage

\begin{exo} Who are these charming gentlemen ?
\begin{figure}[h]
\begin{center}
\includegraphics[height=5.5cm]{aldous}
\includegraphics[height=5.5cm]{broder}
\end{center}
\end{figure}
\end{exo}


\nocite{Ald90}
\nocite{Ald91a}
\nocite{Ald91}
\nocite{Ald93}

\bibliographystyle{alpha}
\bibliography{/Users/nicolascurien/Dropbox/Macros-Bibli/bibli}

\end{document}