\documentclass{article}
\usepackage{amsmath,amssymb}
\setlength{\oddsidemargin}{0.25 in}
\setlength{\evensidemargin}{-0.25 in}
\setlength{\topmargin}{-0.6 in}
\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\headsep}{0.75 in}
\setlength{\parindent}{0 in}
\setlength{\parskip}{0.1 in}
\newcounter{lecnum}
%
% The following macro is used to generate the header.
%
\newcommand{\lecture}[4]{
  \pagestyle{myheadings}
  \thispagestyle{plain}
  \newpage
  \setcounter{lecnum}{#1}
  \setcounter{page}{1}
  \noindent
  \begin{center}
    \framebox{
      \vbox{\vspace{2mm}
        \hbox to 6.28in { {{\bf 18.317~Combinatorics, Probability, and
  Computations on Groups} \hfill #2} }
        \vspace{4mm}
        \hbox to 6.28in { {\Large \hfill Lecture #1  \hfill} }
        \vspace{2mm}
        \hbox to 6.28in { {\it Lecturer: #3 \hfill Scribe: #4} }
        \vspace{2mm}}}
  \end{center}
  \markboth{Lecture #1: #2}{Lecture #1: #2}
  \vspace*{4mm}
}

\input{epsf}
%usage: \fig{LABEL}{FIGURE-HEIGHT}{CAPTION}{FILENAME}
\newcommand{\fig}[4]{
        \begin{figure}
        \setlength{\epsfysize}{#2}
        \centerline{\epsfbox{#4}}
        \caption{#3} \label{#1}
        \end{figure}
        }

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newenvironment{proof}{{\bf Proof:}}{\hfill\rule{2mm}{2mm}}
\newenvironment{mproof}[1]{{\bf #1}}{\hfill\rule{2mm}{2mm}}

\def\E#1{{\rm E}[#1]}
\def\Pr#1{{\rm Pr}[#1]}
\def\i{\hspace*{5mm}}
\newcounter{lineno}
\setcounter{lineno}{0}
\def\n{\addtocounter{lineno}{1} \hbox to 7mm{\hfill \arabic{lineno}:}\hspace{2mm}}
\def\resetn{\setcounter{lineno}{0}}
\def\tqbfk{\tqbf_k^\exists}
\def\ep{\epsilon}
\def\erd{Erd\H{o}s}

\begin{document}
\lecture{26}{16 November 2001}{Igor Pak}{Igor Pavlovsky}

\section*{Babai's Algorithm continued: escape time}
Last time, we proved
\begin{theorem}{}
Let $C$ be a subset of the group $G$, $S=S^{-1}$ a symmetric generating set, $\pi=U(S)$ the uniform distribution on $S$, and $p_\pi$ the ``one-step evolution'' of the random walk (i.e. $p_\pi\varphi = U(S)\star\varphi$). Then for any probability distribution $\varphi$,
$$\|p_\pi\varphi\| ^2  \leq   \left(1-\frac{|G\backslash C|}{2\cdot A\cdot|G|}\right) \cdot \|\varphi\|^2$$
where $A=d \cdot |S| \cdot \max_{s\in S}\max_{g\in \bar{C}} \mu_s(g)$, $d=\mbox{diam}(\bar{C},G)$.
\hfill\rule{2mm}{2mm}
\end{theorem}

We will use this theorem to bound the escape time of a random walk $X_t$ generated by $S$. For a subset $C$ of $G$, set
$$\varphi_t(g)=\Pr{\mbox{$X_t=g$ and $X_i\in C$ $\forall i=1\dots t$}}$$
Obviously, $\mbox{supp}~\varphi_t\subset C$, $\|\varphi_0\|\leq1$ ($1$ if $C$ contains $1_G$, $0$ otherwise) and
$$\varphi_{t+1}(g) =\left\{
\begin{array}{cl}
(p_\pi\varphi_t)(g) &\mbox{if } g\in C\\
0 &\mbox{otherwise}
\end{array}
\right.$$

Inductively applying the above theorem, conclude
\begin{corollary}
$\|\varphi_t\|^2 \leq \left(1-\frac{|G\backslash C|}{2\cdot A\cdot|G|}\right) ^t$
\hfill\rule{2mm}{2mm}
\end{corollary}

Given a bound $\|\varphi_t\|^2\leq\ep$, we'd like to bound the ``non-escape'' probability $p=\sum_{g\in C}\varphi_t(g)$. It is clear that the worst situation is when $\varphi_t(g)=\frac{p}{|C|}$ is uniform on $C$. In that case, $\|\varphi_t\|^2=\sum_{g\in C}\left(\varphi_t(g)\right)^2=|C|\frac{p^2}{|C|^2}=\frac{p^2}{|C|}$. Hence, $p^2\leq|C|\ep$. In other words:
\begin{lemma}
If $\|\varphi_t\|^2 \leq \frac{\alpha^2}{|C|}$, then $\Pr{X_1,\dots,X_t\in C} \leq\alpha$.
\hfill\rule{2mm}{2mm}
\end{lemma}

Combining the last two results, obtain
\begin{corollary}
Suppose $|C|\leq|G|/2$. Then $\Pr{X_1,\dots,X_t\in C} \leq \left(1-\frac{1}{4A}\right)^{t/2} \sqrt{|C|}$.
\hfill\rule{2mm}{2mm}
\end{corollary}

The first tool for our main escape-time theorem is now ready:

\begin{proposition}
Let $C$ be a subset of a finite group $G$, let $\{X_t\}_t$ be a random walk on $G$ w.r.t. some symmetric generating set. Suppose $|C|\leq|G|/2$. Then $\Pr{X_1,\dots,X_t\in C} \leq \frac{1}{e}$ for $t \geq 4A(\log|C|+2)$.
\hfill\rule{2mm}{2mm}
\end{proposition}

The following result will provide the remaining tool.

\begin{proposition}
Let $C=C^{-1}$ be a symmetric subset of a finite group $G$, let $\{X_t\}_t$ be a random walk on $G$ w.r.t. some (arbitrary) generating set, and suppose $\Pr{\mbox{$X_t \in C^2$ for all $1\leq t \leq T$}} \leq 1-p$. Then for $m\geq 2T$,
$$\frac{1}{m} \sum_{t=1}^m \Pr{X_t \notin C} \geq \frac{p}{p+1}\cdot\frac{T}{m}$$
\end{proposition}
\begin{proof}
Set $\tau$ to be the hitting time of $G\backslash C^2$, i.e. the first $t$ with $X_t \notin C^2$; then $\Pr{\tau \leq T} \geq p$. Note that if $\tau\leq T$, then $\{\tau,\tau+1,\dots,\tau+T-1\}\subset\{1,\dots,m\}$. Set $z=X_\tau$ and observe $(z \cdot C) \cap C=\emptyset$. The idea is that once the random walk wanders outside of $C$ and in fact to a point $z$ outside of the much bigger $C^2$, it is likely to stay in a $C$-neighborhood of $z$ (which is outside of $C$!) for some time. Compute:

\begin{center}
$
\begin{array}{rclcl}
\parbox{1.1in} {$$\frac{1}{m} \sum_{t=1}^m \Pr{X_t \notin C}$$}
& \geq & \lefteqn{ \frac{1}{m} \Pr{\tau \leq T} \cdot \sum_{t=\tau}^{\tau+T-1} \Pr{zX_t \in zC} } & & \\
& \geq & \parbox{1.3in} {$$\frac{p}{m}\sum_{t=\tau}^{\tau+T-1} \Pr{X_t \in C}$$}
& \geq & \parbox{2.2in} {$$\frac{p}{m}\left( \sum_{t=1}^{m} \Pr{X_t \in C} - (m-T) \cdot 1 \right)$$} \\
& &
& \geq &\parbox{1.6in} {$$\frac{p}{m}\left( T - \sum_{t=1}^{m} \Pr{X_t \notin C} \right)$$}
\end{array}
$
\end{center}

Here in the first line we used that $X_{\tau+t}$ has the distribution of $z\cdot X_t$, and in the second line that the $m-T$ extra terms $\Pr{X_t \in C}$ on the right all are $\mbox{}\leq1$.
Now denote by $q$ the expectation in question: $q=\frac{1}{m} \sum_{t=1}^m \Pr{X_t \notin C}$. The above inequality translates into $q \geq p\left(\frac{T}{m}-q\right)$. Solve for $q$.
\end{proof}


When $m=2T$ and $p=1-\frac{1}{e}$, the proposition gives $q\geq\frac{e-1}{2e-1}\cdot\frac{1}{2}>\frac{1.5}{5}\cdot\frac{1}{2}>\frac{1}{8}$. Hence, at last,

\begin{theorem}
Let $C=C^{-1}$ be a symmetric subset of a finite group $G$, with $|C^2| \leq |G|/2$. Let $\{X_t\}_t$ be a random walk on $G$ w.r.t. some symmetric generating set. Then for $2\cdot T\geq 2\cdot4A(\log|C|^2+2)=O(16\log|C|)$, the escape-expectation is ``large'':
$$\frac{1}{2T} \sum_{t=1}^{2T} \Pr{X_t \notin C} > \frac{1}{8}$$
\hfill\rule{2mm}{2mm}
\end{theorem}

Therefore, in Babai's Algorithm, run the random walk on $G$ for a {\it random} $\alpha\in[1\dots L]$ steps ($L=O(\log^3|G|)$ as before, $\mbox{}>O(\log|G|)$). At the end of many -- 1/8th -- of $l=O(16\log|G|)$ such runs, we expect to wonder away from any ``small'' subset. Done!


\end{document}