\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\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{9}{28 September 2001}{Igor Pak}{Christopher Malon}



\newcommand{\erdren}{Erd\H{o}s--R\'{e}nyi }

\section*{Generalized Random Subproducts}

Today, we start to upgrade the \erdren machine
to show that ``most'' generating
sets of size $O(\log \vert G \vert)$ have a mixing time
of $O(\log \vert G \vert)$.  We'll be more precise about this
in due course.

First, we want to show that \erdren is robust when we
insert junk in the middle of our strings.
Fix $\overline{g} = (g_1, g_2, \ldots, g_k) \in G^k$.
On Monday, we defined a probability distribution over $G$
$$Q_{\overline{g}} (h) = {\mathrm Pr}_{\overline{\epsilon}} \left[
g_1^{{\epsilon}_1} \cdots g_k^{{\epsilon}_k} = h \right]$$
where $\overline{\epsilon} = ({\epsilon}_1, \ldots, {\epsilon}_k)$
is picked randomly, uniformly from ${\{0, 1\}}^k$.
Now fix group elements $x_1, \ldots, x_l$ and
integers ${\gamma}_1, \ldots, {\gamma}_l$.
We insert the $x_i$ at intervals ${\gamma}_i$:
Let $$R_{\overline{g}} (h) = {\mathrm Pr}_{\overline{\epsilon}} \left[
g_1^{\epsilon_1} \cdots g_{{\gamma}_1}^{\epsilon_{{\gamma}_1}} x_1
g_{{\gamma}_1 + 1}^{\epsilon_{{\gamma}_1 + 1}} \cdots
g_{{\gamma}_1 + {\gamma}_2}^{\epsilon_{{\gamma_1 + \gamma_2}}} x_2
\cdots x_l \cdots g_k^{\epsilon_k} = h \right]$$

Let's look at this in the case where $l = 1$.
In this case, we are considering products of the form
$$g_1^{\epsilon_1} \cdots g_i^{\epsilon_i} x g_{i+1}^{\epsilon_{i+1}}
\cdots g_k^{\epsilon_k}
= g_1^{\epsilon_1} \cdots g_i^{\epsilon_i}
{\left( g_{i+1}^x \right)}^{\epsilon_{i+1}} \cdots
{\left( g_k^x \right)}^{\epsilon_k} x$$
where $i = \gamma_1$, $x = x_1$, and $g^x$ denotes $x g x^{-1}$.
Declare $\overline{z} (x, \gamma) = (1, \ldots, 1, x, \ldots, x)$,
where 1's appear in the first $i$ positions, and write
$$(g_1, \ldots, g_k)^{(z_1, \ldots, z_k)} = (g_1^{z_1}, \ldots, g_k^{z_k})$$
Evidently,
$$R_{\overline{g}} (h) = Q_{\overline{g}^{\overline{z}(x, \gamma)}}
(h x^{-1})$$

If $l > 1$, we just have to repeat these maneuvers
to define a string $\overline{z} (\overline{x}, \overline{\gamma})$
and a function $f(\overline{x})$ so that
$$g_1^{\epsilon_1} \cdots g_{{\gamma}_1}^{\epsilon_{{\gamma}_1}} x_1
g_{{\gamma}_1 + 1}^{\epsilon_{{\gamma}_1 + 1}} \cdots
g_{{\gamma}_1 + {\gamma}_2}^{\epsilon_{{\gamma_1 + \gamma_2}}} x_2
\cdots x_l \cdots g_k^{\epsilon_k}
= {(\overline{g}^{\overline{z}
(\overline{x}, \overline{\gamma})})}^{\overline{\epsilon}}
\cdot {(f(\overline{x}))}^{-1}$$
Then we have
\begin{equation}
R_{\overline{g}} (h) = Q_{\overline{g}^{\overline{z}(\overline{x},
\overline{\gamma})}}
(h \cdot f(\overline{x}))
\label{eq:shift}
\end{equation}

We want to show $R_{\overline{g}}$ is usually close to uniform.
\begin{definition}
A probability distribution $Q$ on a finite group $G$ is
$\epsilon$--{\em uniform} if $$Q(h) > \frac{1 - \epsilon}{\vert G \vert}$$
for all $h \in G$.
\end{definition}

Two lectures ago, we proved:
\begin{theorem} (\erdren)
For all $\epsilon, \delta > 0$, $Q_{\overline{g}}$ is $\epsilon$--uniform
for more than $1 - \delta$ proportion of $\overline{g} \in G^k$, given
$k > 2 \log_2 \vert G \vert + 2 \log_2 \frac{1}{\epsilon} + \log_2
\frac{1}{\delta}$.
\end{theorem}

Multiplication by $f(\overline{x})$ is a bijection on the elements of $G$,
so $\epsilon$--uniformity of $Q_{\overline{g}} (h)$ over $h$ implies
$\epsilon$--uniformity of $Q_{\overline{g}} (h \cdot f(\overline{x}))$
over $h$.  Because conjugation by $\overline{z} (\overline{x},
\overline{\gamma})$ is a bijection on $G^k$, the $R_{\overline{g}}$
will be $\epsilon$--uniform for the same proportion of
$\overline{g}$ as $Q_{\overline{g}}$, applying equation (\ref{eq:shift}).
Thus, we have \erdren for $R_{\overline{g}}$:
\begin{theorem}
For all $\epsilon, \delta > 0$, $R_{\overline{g}}$ is $\epsilon$--uniform
for more than $1 - \delta$ proportion of $\overline{g} \in G^k$, given
$k > 2 \log_2 \vert G \vert + 2 \log_2 \frac{1}{\epsilon} + \log_2
\frac{1}{\delta}$.
\label{thm:newer}
\end{theorem}


Now, we look at a probability distribution of group elements
over a larger sample space, describing what happens when the
$x_i$ may or may not be inserted.
Define
$$Q_{\overline{g}, \overline{x}} (h) = \mathrm{Pr}_{\overline{\epsilon},
\overline{\alpha}} \left[
g_1^{\epsilon_1} \cdots g_{{\gamma}_1}^{\epsilon_{{\gamma}_1}}
x_1^{\alpha_1}
g_{{\gamma}_1 + 1}^{\epsilon_{{\gamma}_1 + 1}} \cdots
g_{{\gamma}_1 + {\gamma}_2}^{\epsilon_{{\gamma_1 + \gamma_2}}} x_2^{\alpha_2}
\cdots x_l^{\alpha_l} \cdots g_k^{\epsilon_k} = h \right]$$
where $\overline{\alpha}$ is picked uniformly from ${\{0, 1\}}^l$.
For fixed $\overline{\alpha}$, let
$$R_{\overline{g}, \overline{x}, \overline{\alpha}} (h)
= \mathrm{Pr}_{\overline{\epsilon}} \left[
g_1^{\epsilon_1} \cdots g_{{\gamma}_1}^{\epsilon_{{\gamma}_1}}
x_1^{\alpha_1}
g_{{\gamma}_1 + 1}^{\epsilon_{{\gamma}_1 + 1}} \cdots
g_{{\gamma}_1 + {\gamma}_2}^{\epsilon_{{\gamma_1 + \gamma_2}}} x_2^{\alpha_2}
\cdots x_l^{\alpha_l} \cdots g_k^{\epsilon_k} = h \right]$$
Then we have
\begin{equation}
Q_{\overline{g}, \overline{x}} = \frac{1}{2^l}
\sum_{\overline{\alpha}} R_{\overline{g}, \overline{x}, \overline{\alpha}}
\label{eq:sumit}
\end{equation}

Suppose $k > 2 \log_2 \vert G \vert + 2 \log_2 \frac{1}{\epsilon}
+ \log_2 \frac{1}{\delta}$ is fixed.
Draw a grid whose rows represent the choices of
$\overline{g}$ from $G^k$, and whose columns represent the choices
of $\overline{\alpha}$.  Keep $l$, $\overline{\gamma}$, and $\overline{x}$
fixed.  Mark the $(\overline{g}, \overline{\alpha})$ position in this
grid if $R_{\overline{g}, \overline{x}, \overline{\alpha}}$ is
$\epsilon$--uniform.  Theorem \ref{thm:newer} applies to
$R_{\overline{g}, \overline{x}, \overline{\alpha}}$, saying that
in every column ({\em i.e.} for any fixed $\overline{\alpha}$), 
the proportion of unmarked squares is less than $\delta$.
Consequently, less than $\sqrt{\delta}$ of the rows have more than
$\sqrt{\delta}$ of their positions unmarked.  By equation (\ref{eq:sumit}),
for more than $1 - \sqrt{\delta}$ of the $\overline{g}$,
$$Q_{\overline{g}, \overline{x}} (h) > \frac{1 - \sqrt{\delta}}{\vert G \vert}
(1 - \epsilon)$$
This proves:
\begin{theorem}
For every $\epsilon, \delta > 0$, $Q_{\overline{g}, \overline{x}}$ is
$(\epsilon + \delta)$--uniform for more than $1 - \sqrt{\delta}$
proportion of $\overline{g}$, given
$k > 2 \log_2 \vert G \vert + 2 \log_2 \frac{1}{\epsilon}
+ \log_2 \frac{1}{\delta}$.
\label{thm:laster}
\end{theorem}

\section*{Lazy Random Walks}

Now we return to our question about mixing time.  

\begin{definition}
Fix $\overline{g} = (g_1, \ldots, g_k)$, not necessarily generating $G$.
A {\em lazy random walk} through $\overline{g}$ is a sequence of group
elements $X_t$ such that $X_0 = 1$ and
$X_{t+1} = X_t \cdot g_{i_{t+1}}^{\epsilon_{t+1}}$, where each
$i_{t+1}$ is picked randomly, uniformly from $\{1, \ldots, k\}$, and
$\epsilon_{t+1}$ is picked randomly, uniformly from $\{0, 1\}$.
Thus
$$X_t = g_{i_1}^{\epsilon_1} \cdots g_{i_t}^{\epsilon_t}$$
\end{definition}

Let $P_{\overline{g}}^t$ be the probability distribution of the
lazy random walk through $\overline{g}$ after $t$ steps.
Today's work has shown us: If, after $t$ steps, we have selected
$k^{\prime}$ distinct $i$'s (where $k^{\prime}$ is
at least as big as in theorem
\ref{thm:laster}), then $P_{\overline{g}}^t$ will be close to
uniform for most $\overline{g}$; the redundant generators chosen
in the lazy random walk will take the place of $\overline{x}$.

From the Coupon Collector's Problem, we can compute
how big $t$ must be in order to provide enough generators.
If we need to collect all the $g_i$ and $\overline{g} = (g_1, \ldots, g_k)$,
the expected waiting time is
$$1 + \frac{k}{k-1} + \frac{k}{k-2} + \ldots + k = k \log k + O(k)$$
We'll fill in more details in the next lecture.

\end{document}