\documentclass{article}
\usepackage{amsmath,amssymb}
\usepackage{xspace}
\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\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\vep{\varepsilon}
\def\erd{Erd\H{o}s}
\newcommand{\ka}{\ensuremath{\kappa}\xspace}
\newcommand{\vk}{\ensuremath{\varkappa}\xspace}
\newcommand{\sep}[1]{\textrm{sep}(#1)}

\renewcommand{\l}{\ensuremath{\ell}}

\begin{document}
\lecture{13}{10 October 2001}{Igor Pak}{Bo-Yin Yang}



\newcommand{\erdren}{Erd\H{o}s--R\'{e}nyi\xspace}
\section*{More on Strong Uniform Stopping Times}
\begin{theorem}
  We have a \emph{tight} bound on group random walks with a strong
  uniform stopping time:
  \begin{enumerate}
  \item For any strong uniform stopping time \vk, $\sep{t} \le
    \Pr(\vk > t), \forall t$;
  \item (For any given group random walk) There exists a strong
    uniform stopping time \vk, such that $\sep{t} = \Pr(\vk > t),
    \forall t$;
  \end{enumerate}
\end{theorem}

We first give an application of this theorem, let
$G=\Bbb{Z}_2^n$, define a \emph{lazy} random walk with
generating set
$$ S=\bigl\{(0,\ldots,\stackrel{i-th}{1},\ldots,0),i\in\{1..n\}\bigr\},$$
where the random walk rules are:
\begin{enumerate}
\item Pick $j$ uniformly randomly from $1\ldots n$.
\item Flip a coin.
\item If heads, then move in the direction; if tails nothing happens.
\item Repeat.
\end{enumerate}

A stopping time for this random walk is \vk: \textit{mark a coordinate
  $j$ when it is ``picked'' regardless of the coin toss.  Stop when
  all coordinate directions have been marked.}  It is trivial that
this \vk is strong uniform, hence the mixing time for this random
walk is $O(n\log n)$.

\begin{proof}
  If $ R^t_j(g) = \Pr(X_t=g | \vk=j),$ then $\forall t>j,\, R^t_j =
  R^j_j * Q^{t-j} = U$, since $R^j_j=U$ by definition.  So

  \begin{eqnarray*}
    \Pr(X_t=g) &=&
    \sum_{j=1}^t \overbrace{\Pr(X_t=g|\vk=j)}^{(= 1/|G|)}\; \Pr(\vk=j) +
    \Pr (X_t=g| \vk>t)\; \Pr(\vk >t) \\
    &\ge& \sum_{j=1}^t \Pr(\vk=j)\cdot \frac1{|G|}
    = \Pr(\vk \ge t)\cdot \frac{1}{|G|}. \\
  \end{eqnarray*}

  Hence $$\sep{t} = |G| \,\max_{g\in G} (\frac1{|G|}- \Pr(X_t=g)) >
  \Pr(\vk>t).$$

  This ends the first part of the proof.  To prove the second part we
  will construct explicitly a stopping time.

  Let $\displaystyle q_t\equiv \min_{g\in G}Q^t(g)$.  The stopping
  rule is: if $X_t=g$, we stop with probability $\displaystyle
  \frac{q_t - q_{t-1}}{Q^t(g)-q_{t-1}},$ else keep walking.  We want,
  and it is easy to verify by mathematical induction that
  $$\Pr(X_t=g | \vk\ge t) = Q^t(g) - q_{t-1},$$
  hence
  $$\Pr(\vk=t)=\sum_{g\in G} \Pr(X_t=g | \vk\ge t) \; \frac{q_t -
    q_{t-1}}{Q^t(g)-q_{t-1}} = |G| (q_t - q_{t-1}),$$

  and
  $$\Pr(\vk > t) = 1 - \sum_{j=1}^t \Pr(\vk = j) = 1- |G|\cdot q_t
  = |G| \; \min_{g\in G} \left( \frac1{|G|} - Q^t(g)\right) = \sep{t}.$$
\end{proof}

We will now give an example of a strong uniform stopping time in
$S_n$, with the generating set being the exchanges
$R=\{r_i=(1\;i) \, | \, i=1, \dots, n\}$ (so $r_1=id$).  The Stopping Rule
to define \vk is to think of the numbers as a deck of cards and:
\begin{enumerate}
\item First mark $n$.
\item When the number on the first card is an unmarked number, and
  $r_j$ (with $j$ is a marked index) appears or $r_1$ appears, is
  first, then mark the first card (number in first position).
\item Wait until all cards are marked, then stop.
\end{enumerate}


We wish to show that \vk is strong uniform.
\begin{claim}
  If $S$ are the set of marked numbers, and $I$ are the numbers
  appearing in the places whose locations correspond to the marked
  numbers in $S$, then at all times
  $$
  \Pr(\pi = \omega | |S| = |I|= k) = \frac1{k!}, \forall \omega:
  I\rightarrow S.$$
\end{claim}

\begin{proof}
  By mathematical induction.  It's clearly true at the beginning when
  $k=1$.  When $|S|$ and $|I|$ both increase by $1$ (we mark another
  card), this card has an equal chance of being exchanged with any of
  the cards in marked locations or not being exchanged at all.  So
  from the properties of $S_n$ we know that this is true.
\end{proof}

\begin{corollary}
  Mixing time for this random walk is $O(n\, \log n)$.
\end{corollary}
\begin{proof}
  We know from the preceeding claim that \vk as defined is strong
  uniform.  So we know that
  $$\tau_3 \le E(\vk) = \sum_{k=1}^{n-1} \frac{n}{k+1} +
  \sum_{k=2}^{n-1} \frac{n}{n-k} = 2n\, \log n + O(n).$$

  Why the sum?  Because it is now a double Coupon Collector's Problem,
  in that we have to wait until we get a marked number, then until we
  get an unmarked number, then until we get a marked number again ....
  until everything is marked.
\end{proof}

In our next lecture we will talk about Random Walks on other groups,
in particular nilpotent groups of a certain kind.

\end{document}