\documentclass{article}
\usepackage{amsmath,amssymb,amsfonts}
\usepackage{amsthm}
\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}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{example}{Example}
\renewenvironment{proof}{{\bf Proof:}}{\hfill\rule{2mm}{2mm}}
\newenvironment{mproof}[1]{{\bf #1}}{\hfill\rule{2mm}{2mm}}
\DeclareMathOperator{\Aut}{Aut}

\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{31}{30 October 2001}{Igor Pak}{D. Jacob Wildstrom}

\section*{Bias (continued)}

\begin{theorem}[P. Hall]

  For a simple group $H$ and $G=H^m$, it follows that $\langle
  g_1,\ldots,g_k\rangle=G$ if and only if  $\langle
  h_j^{(1)},h_j^{(2)},\ldots,h_j^{(k)}\rangle=H$ for all $j$ from $1$
  to $m$.
\end{theorem}

We shall henceforth work with $H=A_n$, $m=\frac{n!}8$,
$\varkappa=o(n)$, $G=H^m$, and $Q=Q_k$, which to refresh our memory,
is simply the probability distribution of $g_1$ in
$\bar{g}=(g_1,g_2,\ldots,g_k)\in\Gamma_k(G)$.

\begin{theorem}
  There is a subset $B$ of $G$ such that, as $n\rightarrow\infty$,
  $\frac{|B|}{|G|}\rightarrow 1$ but $Q(B)\rightarrow 0$.
\end{theorem}

That is to say that there is a huge subset (approaching the full set)
of $G$ which is hardly ever generated by a $k$-tuple of generators.

We claim that, roughly, if $k\geq k$, then the values of
$h_j=(h_j^{(1)},h_j^{(2)},\ldots,h_j^{(k)})$ are independent.

Then we have the lemma:

\begin{lemma}
  $|\Gamma_k(o)|=|\Gamma_k(H)|^m|(1-O(\frac1{n!}))$.
\end{lemma}
\begin{proof}
  The number of automorphisms of $\Gamma_k(H)$ is, as we discussed
  earlier, $\alpha_k(G)$, which must exceed
  $\frac{H^k}{2|\Aut(H)|}=\frac12\frac{(\frac n2)^k}{n!}=N$. Now,
  $|\Gamma_k(G)|$ is equal to the product of $|\Gamma_k(H)|^m$ and the
  probability that each generated $k$-tuple is in a distinct
  orbit. This we can easily calculate to be
  $(1-\frac1N)(1-\frac2N)\cdots(1-\frac mN)$, which exceeds $(1-\frac
  mN)^m$ and thus $(1-\frac{m^2}N)$. Using the equation $m=\frac{n!}8$
  and $N\geq\frac{(n!)^3}{32}$, the above factor can be easily shown
  to exceed $1-\frac1{2n!}$
\end{proof}

Let $A_n$ be generated by $(h_1^1,h_1^2,\ldots,h_1^k)$. We know that
with probability $\approx\frac1n$ (specifically,
$\frac1n\pm\frac1{n^3}$), $h_1^1$ moves the first element. What would
the specific probability tell us about $g_1$?

We start by looking at $\phi_k(A_n)$, which would be 1 minus the
probability of ``bad events''. What sort of ``bad events'' might we
have in mind? They can be characterized by $h_1,\ldots,h_k\in M$ for
some maximal subgroup $M$ of $H$. There are really only 3 types of
maximal subgroups in $H$: those with one fixed point, those with a
pair of elements forming an orbit, and those with two fixed
points. The probability of generating any of these is easily
calculated:
$$\phi_k(A_n)=1-\frac1{n^k}n-\frac1{n(n-1)^k}\binom n2+\frac1{2(n(n-1))^k}\binom n2=1-\frac 1{n^{k-1}}+O(\frac1{n^{2(k-1)}})$$

Let $\mathcal A$ be the event $(h_1,\ldots,h_k)\in\Gamma_k(H)$, and
$\mathcal B$ be the event that $h_1=1$. By the above, $\Pr(\mathcal
A)=1-\frac1{n^k-1}+O(\frac1{n^{2(k-1)}})$ and $\Pr(\mathcal B)=\frac1n$.

So what is $\Pr(\mathcal B|\mathcal A)$? Well, it is equal to
$\frac{\Pr(\mathcal A|\mathcal B)}{\Pr(A)}\Pr(B)$, and we may
interpret $\Pr(\mathcal A|\mathcal B)$ as such; either
$h_2,\ldots,h_k$ fix the first element or they fix an element not
equal to the first. Calculating the probabilities, it follows that
$$\Pr(\mathcal A|\mathcal B)=1-\frac2{n^{k-1}}+O(\frac1{n^{2(k-1)}})$$
and thus
$$\Pr(\mathcal B|\mathcal A)=\frac1n\left(\frac{1-\frac2{n^{k-1}}+O(\frac1{n^{2(k-1)}})}{1-\frac1{n^{k-1}}+O(\frac1{n^{2(k-1)}})}\right)=\frac1n\left(1-\frac1{n^{k-1}}+O(\frac1{n^{2(k-1)}})\right)$$
so $P=\frac1n-\frac1{nk}+O(\frac1{n^{2k-1}})$.

So, if we were to plot the number of generating sets giving us
$h_1(1)=1$ for $g$ uniform and $g_1\in\Gamma_k(G)$, we wil have peaks
at $\frac1n$ and $\frac1n-\frac1{n^k}$ respectively, and we may return
to our original result by choosing $B\subset G$ such that
$\{g=(h_1,\ldots,h_m)\}$ in which the number of generating sets in
which $h_i(1)=1$ exceeds $m(\frac1n-\frac1{2n^2})$. Using the Chernoff
bounds, we find that $|B|\approx |G|(1-\frac1{n!})\rightarrow 1$, and
that $Q_k(B)\approx\frac1{n!}\rightarrow0$.
\end{document}