\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{10}{1 October 2001}{Igor Pak}{Igor Pavlovsky}

\section*{Coupon Collector's Problem}
Recall that the problem concerns a prudent shopper who tries, in several attempts, to collect a complete set of $N$ different coupons. Each attempt provides the collector with a coupon randomly chosen from $N$ known kinds, and there is an unlimited supply of coupons of each kind. It is easy to estimate the expected waiting time to collect all $N$ coupons:
$$\E{\mbox{time to collect $N$ coupons}} = 1+\frac{N}{N-1}+\frac{N}{N-2}+\dots+N = N(\log N+\gamma+O(\frac{1}{N}))$$
Similarly,
\begin{align}
\E{\mbox{time to collect $\frac{N}{2}$ coupons}} &= 1+\frac{N}{N-1}+\frac{N}{N-2}+\dots+\frac{N}{\frac{N}{2}+1} \notag\\
&= N(\log N+\gamma+O(\frac{1}{N}) - \log\frac{N}{2}-\gamma-O(\frac{1}{N})) \notag\\
&=N\log2+O(1) \notag
\end{align}

Let's explore the problem further. Suppose our collector attempts to obtain coupons $T=\alpha N$ times. We'd like to know how many different kinds of coupons he can be expected to have, and also how many of these are not repeated. For such estimates, we need the following tool:
\begin{theorem}{\bf (Chernoff bound)}
Let $X_i$, $i=1\dots n$, be independent Poisson trials, with outcomes $1$ and $0$ with probabilities $p_i$ and $1-p_i$ respectively. Set $X=\sum_{i=1}^{n} X_i$, $\mu=\E{X}=\sum p_i$. Then for every $\delta>0$, the following bounds hold:
\begin{align}
\mathrm{Pr}[X>(1+\delta)\mu]&<\left(\frac{e^{\delta}}{(1+\delta)^{1+\delta}}\right)^{\mu} \notag\\
\mathrm{Pr}[X<(1-\delta)\mu]&<e^{-\mu\delta^2/2} \notag
\end{align}
\hfill\rule{2mm}{2mm}
\end{theorem}

In our situation, at every step
\begin{align}
\mathrm{Pr}[\mbox{got a coupon we already have}] &< \alpha\notag\\
\mathrm{Pr}[\mbox{got a new coupon}] &>1-\alpha \notag
\end{align}
Consider the worst-case {\it independent}-trials processes defined by the above inequalities transformed into equalities. Bounds on these processes will give us the desired bounds for the coupon collector's problem. Clearly,
\begin{align}
\E{\mbox{number of repeated coupons}}&<\alpha T \notag\\
\E{\mbox{number of different coupons}}&>(1-\alpha)T \notag
\end{align}

Therefore, by Chernoff bounds,
\begin{align}
\mathrm{Pr}[\mbox{\# rep coupons}>(1+\delta)\alpha T] &< \ep_1^T \notag\\
\mathrm{Pr}[\mbox{\# diff coupons}<(1-\delta)(1-\alpha)T] &< \ep_2^T \notag
\end{align}
where $\ep_1$, $\ep_2$ depend on $\alpha$ and $\delta$. Now, the event [\# non-repeated coupons $<A-B$] is contained in the union of the events [\# diff coupons$<A$] $\cup$ [\# rep coupons $>B$]. Hence,
$$\mathrm{Pr}[\mbox{\# non-rep coupons}<(1-\delta)(1-\alpha)T-(1+\delta)\alpha T]<\ep_1^T+\ep_2^T<\ep^T$$
for large $T$ and some $\ep$ dependent on $\alpha$ and $\delta$. Recalling that $T=\alpha N$, conclude

\begin{theorem}{}
After $\alpha N$ steps, the number of non-repeated coupons accumulated by the collector is greater than $cN$ with probability $>1-\ep^N$ for large N. Here $\alpha, c, \ep>0$, one of $\alpha$ or $c$ may be chosen arbitrarily, and the other two parameters are produced by the theorem.
\hfill\rule{2mm}{2mm}
\end{theorem}

\section*{Mixing Time of Random Walks}

We have finally arrived at our goal
\begin{theorem}{}
Let ${X_t}$ be a lazy random walk on $G$ starting at $1$, with a random generating set of size $k$. Denote by $\mathrm{sep}(T)$ the separation distance after T steps. Then exists a constant $c>0$ such that $\mathrm{sep}(c\log\left| G\right| )<\ep$ with probability $>1-\delta-\gamma$, provided that $k=2\log\left| G\right|+2\log\frac{1}{\ep}+2\log\frac{1}{\delta}+\log\frac{1}{\gamma}$.
\end{theorem}
\begin{proof}
Combine the \erd--R\'{e}nyi machine and coupon collector's problem to ensure enough non-repeated generators. Check parameters, done.
\end{proof}

\vspace{1cm}

Our next aim is to prove that random Cayley graphs are expanders. We begin with a few observations on matrices and random walks.
Let $A$ be the transition matrix for the random walk $X_{t+1}=X_t\cdot g_i$ on $G$ with generators $g_1, \dots , g_k$. If at each step the generator $g_i$ is chosen uniformly, then the entries of $A$ are numbers $0$ and $\frac{1}{k}$. Let $v=e_1$ be the initial state vector (begin at $1$). The vector $A^tv$ gives the probability distribution on $G$ after $t$ steps, and can be written as
$$A^t v = u + \lambda_1^t w_1 + \lambda_2^t w_2 + \dots$$
where $\lambda_1\geq\lambda_2\geq\dots$ are the eigenvalues of $A$. If these eigenvalues are real, they clearly must lie between $-1$ and $1$ for the distribution to converge to the uniform probability distribution $U$.


\end{document}