\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{sublemma}[theorem]{Sublemma}
\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{5}{19 September 2001}{Igor Pak}{Dennis Clark}

\section*{Proof of a Lemma}

Our plan here is to prove the following lemma, needed in the fixed
proof of \erd -Turan's theorem:

\begin{lemma} Suppose $A=\{1\leq a_1 < a_2 < \dotsb <a_r \leq n\}$. Then:
\begin{equation}
Pr(\sigma \in S_n \text{has no cycles in A}) <
\frac{1}{\sum_{i=1}^r a_i}
\end{equation}
\end{lemma}

But we'll need a few sublemmas first.

\begin{sublemma}
\begin{equation}
E(\#\text{ of $l$-cycles in } \sigma \in S_n) = \frac{1}{l}
\end{equation}
\end{sublemma}

\begin{proof}
\begin{equation}
E=\binom{n}{l}\frac{(l-1)!(n-l)!}{n!}=\frac{1}{l}
\end{equation}
\end{proof}

\begin{sublemma} Assume $l \neq m$, and $l+m \leq n$. Then:
\begin{equation}
E(\# \ \text{of} \ l\text{-cycles} \, \cdot \,
\#  \ \text{of} \ m\text{-cycles in } \sigma \in
S_n)=\frac{1}{l\, m}
\end{equation}
\end{sublemma}

\begin{proof} First, we take the sum in the first equation over the
number of ways to split $n$ into an $l$-subset, and $m$-subset, and an
$n-m-l$ subset.

\begin{equation}
E=\sum Pr(\text{cycle at }l\text{-subset and cycle at }m\text{-subset})
\end{equation}

Then, recognize that all of the probabilities will be symmetric, so we
can just multiply appropriately:

\begin{eqnarray}
E & = & \binom{n}{l,m,n-l-m} \cdot \frac{(l-1)!(m-1)!(n-m-l)!}{n!} \\
& = & \frac{n!(l-1)!(m-1)!(n-m-l)!}{l!m!(n-m-l)!n!} \\
& = & \frac{1}{lm}
\end{eqnarray}
\end{proof}

As a corollary, we get:

\begin{corollary}
\begin{equation}
E(\#\text{ of cycles in } \sigma)=1+ \frac{1}{2} + \dots + \frac{1}{n}
\approx \log n + \gamma + O(\frac{1}{n})
\end{equation}
where $\gamma$ is a constant.
\end{corollary}

\begin{proof}
\begin{equation}
E=\sum_l E(\# \ \text{of} \ l\text{-cycles}) = \sum \frac{1}{l}
\end{equation}
\end{proof}

Another sublemma, here departing from \erd -Turan:

\begin{sublemma}
\begin{equation}
E\bigl((\# \ \text{of} \ l\text{-cycles})^2\bigr)=\left\{
\begin{array}{ll}
\frac{1}{l} & \text{if } 2l>n \\
\frac{1}{l} + \frac{1}{l^2} & \text{if } 2l \leq n
\end{array}
\right.\end{equation}\end{sublemma}

\begin{proof}

To start, observe that
\begin{equation}
E(\# \ \text{of} \ l\text{-cycles})=\frac{1}{l}\sum_{i=1}^n Pr(i \in
l\text{-cycle}) = \frac{1}{l}
\end{equation}
from the proof of Sublemma~2. This gives:
\begin{corollary}
$Pr(i \in l\text{-cycle})=\frac{1}{n}$.
\end{corollary}

Therefore the total number
of cycles is approimately $\log n$.
Similarly, \erd-Turan obtain
\begin{equation}
\log(\prod \text{cycle length}) \approx \frac{1}{2}\log^2 n
\end{equation}


So then we can observe that the square of the number of $l$-cycles is
precisely the number of ordered pairs of elements belonging to
$l$-cycles divided by $l^2$, which yields:

\begin{eqnarray}
E & = & \frac{1}{l^2}\sum_{i=1}^n\sum_{ij1}^n Pr(i \in l\text{-cycle and} j
\in l\text{-cycle}) \\
& = &  \frac{1}{l^2}(\sum_{i=1}^n Pr(i\in l\text{-cycle})+\sum_{i \neq
j}^n Pr(i\in l\text{-cycle})Pr(j\in l\text{-cycle} |i\in
l\text{-cycle} ))
\end{eqnarray}

We consider the sums one at a time. First, the first sum is equal to:
\begin{equation}
\frac{1}{l^2}\cdot n\cdot \frac{1}{n}=\frac{1}{l^2}
\end{equation}
from Corollary~6.

Let us consider now the second sum, which is
equal to
\begin{equation}
\frac{1}{l^2} \cdot n \cdot \frac{1}{n}\cdot(n-1)\left(\frac{l-1}{n-1} +
\frac{n-l}{n-1}\cdot\frac{1}{n-l}\right)
\end{equation}

The justification for the fractions inside the parentheses is as
follows: consider that the element $i$ is already in an $l$-cycle. We
want the probability that $j$ is in an $l$-cycle. First, the
probability that $j$ is in the same $l$-cycle as $i$ is simply
$\frac{l-1}{n-1}$, since $j$ can be in any of $n-1$ places, $l-1$ of
which are what we're looking for. The second summand is the
probability that $j$ is among the remaining points but is in an
$l$-cycle anyway, which can only happen if $l+l\leq n$. So we get the
following:
\begin{equation}
E((\# \ \text{of} \ l\text{-cycles})^2)= \left\{ \begin{array}{ll} \frac{1}{l^2}
+ \frac{1}{l^2}\cdot(l-1)  & \text{if } 2l>n \\ \frac{1}{l^2} +
\frac{1}{l^2}\cdot l & \text{if } 2l \leq n \end{array}\right.
\end{equation}

Which then gives us:

\begin{equation}
E=\left\{ \begin{array}{ll} \frac{1}{l} & \text{if } 2l>n \\
\frac{1}{l} + \frac{1}{l^2} & \text{if } 2l \leq n \end{array}\right.
\end{equation}
as needed.
\end{proof}

Then, we return at last to the proof of Lemma 1:

\begin{proof}

We first estimate the expected value of the number of $A$-cycles:

\begin{equation}
E(\# \ \text{of} \ A\text{-cycles})=\sum_{i=1}^r E(\# \text{ of
}a_i\text{-cycles})=\sum_{i=1}^r\frac{1}{a_i}
\end{equation}

This gives:

\begin{equation}
E((\# \ \text{of} \ A\text{-cycles})^2)=\sum_{i\neq j}^r E(\#
a_i\text{-cycles} \cdot \# a_j\text{cycles}) + \sum_{i=1}^r
E((\# a_i\text{-cycles})^2)
\end{equation}

Applying the two main sublemmas to the two sums yields:
\begin{equation}
\leq 2\sum_{1\leq i<j\leq r} \frac{1}{a_i a_j} +
\sum_i\left(\frac{1}{a_i^2}+\frac{1}{a_i}\right) = \sum_i\frac{1}{a_i} +
\left(\sum_i\frac{1}{a_i}\right)^2
\end{equation}

Now, let $X$ be a random variable describing the number of
$A$-cycles. We have
\begin{eqnarray}
Var(\# \ \text{of} \ A\text{-cycles})  =   Var(X) =
E(X^2)-(E(X))^2 \\
 =
\left(\sum_i\frac{1}{a_i} +
\left(\sum_i\frac{1}{a_i}\right)^2\right) -
\left(\sum_{i}\frac{1}{a_i}\right)^2
 = \sum_{i}\frac{1}{a_i}
\end{eqnarray}

From here and Chebyshev inequality we get the following:
\begin{eqnarray}
Pr(X=0) & = & Pr(X+E(X) \leq E(X)) \\
 & \leq & \frac{Var(X)}{(E(X)^2)} \\
 & \leq & \frac{\sum\frac{1}{a_i}}{(\sum\frac{1}{a_i})^2} \\
& \leq & \left(\sum_i\frac{1}{a_i}\right)^{-1}
\end{eqnarray}

which proves the lemma.
\end{proof}

\end{document}