\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{32}{3 December 2001}{Igor Pak}{Dennis Clark}

\section*{Proving Bias}

In this lecture, we set out to demonstrate that there are examples where
the product replacement algorithm produces bias in its output. Continuing
with the example of last time, we let $G=A_n^{n!/8}$, $G=<g_1,\dots g_k>$,
$Q$ the probability distribution of $g_1$ in a random generating
$k$-tuple, and $U$ the uniform distribution.

Then, we have:

\begin{theorem} Let $k=o(n)$. Then $||Q-U|| \rightarrow 1$ as
$n\rightarrow\infty$.\end{theorem}

\begin{proof} Let $B\subset G$ such that $Q(B) \rightarrow0$ and
$U(B)=\frac{|B|}{|G|} \rightarrow 1$ as $n\rightarrow\infty$. The
existence of such a set was demonstrated last class. Then
\begin{equation}
||Q-U||=\max_{B \subset G} |Q(B)-U(B)| \rightarrow 1
\end{equation}
as $n\rightarrow \infty$, as needed.
\end{proof}

But we need to do better than this. If we were federal inspectors
attempting to prove boxes of group elements to be non-uniform, only
knowing that elements in those boxes were unlikely to belong to $B$ would
not be good enough. We need the following theorem.

\begin{theorem} Let $k=o(n)$. Then there exists a word $w(x_1 \dots x_r)$
of length $o(\log\log |G|)^c$ such that $w[Q]=1$ with high probability
(i.e. probability $>1-\frac{1}{n^{\alpha_n}}$) and $w[U]\neq 1$ with high
probability.\end{theorem}

The proof comes in three parts. One part is like last time, one part is a statistical story,
and one part is combinatorics. We'll do the not-too-combinatorial combinatorial part first.

\begin{proof}
We're going to try to implement something like predicate logic in $H=A_n$. Our basic predicate will be
the compare-to-identity predicate.

Let $A$ be the event $h_1=1$ and $B$ be the event $h_2=1$, where $h_1$ and
$h_2$ are elements drawn according to some distribution $P$ you don't
know. Then, it would be almost right to say that $A\vee B$ is given by
$[h_1,h_2]=1$ with high probability, and $A\wedge B=h_1h_2$ with high
probability.

Now, we take an element $h$ to another element $v$, where
\begin{equation}
v=(h)^{u_1}(h_1)^{u_2}\dots(h_r)^{u_r}\end{equation}
wheter the $u_i$ are sampled uniformly and independently, and the $h_j$ are independently sampled from
$P$. The product should be nearly uniform if $h\neq 1$.

Let $v_1,v_2$ both be either the identity or random with high probability. Then we get
$v_1v_2=1$ with high probability if and only if both elements are $1$ with high probability.
We then compute:
\begin{equation}
Pr([v_1,v_2]=1)=\frac{\# conj.classes(H)}{|H|}<\frac{2\# partitions of n}{\frac{n!}{2}}.
\end{equation}
This is approximately equal to $\frac{1}{n^{\alpha_n}} \rightarrow 0$.
\end{proof}

Now we think of $h \rightarrow v_r$ as a random walk. The probability distribution of $h^{v_i}$ is
invariant on conjugacy classes.

Now we make a claim about the mixing time.

\begin{claim} Let $h=\sigma \in c_{\lambda}$ with high probability. Then the mixing time of a random
walk on $A_n$ with generating set $c_{\lambda}$ is less than
$diam^2(A_n, c_{\lambda})\log |A_n|\approx n\log n$.
\end{claim}
\begin{proof} First,
\begin{equation} diam(A_n, c_{\lambda})=\frac{n}{2} \end{equation}
where the generating set is pairs of transpositions, and
\begin{equation} diam(S_n, c_{\lambda}) \leq n-1\end{equation}
where the generating set is all transpositions. Also,
\begin{equation} diam(S_n, c_{(n)})=3\end{equation}

since any transposition is the product of two long cycles. Also, $\sigma$
is a product of two cycles, of length $\lambda_1,\lambda_2$, whose sum is
$k$. $S_k$ is given by two cylces, and $S_{2k}$ is given by 4.

Then the diameter is some polynomial in $n$, so we're done, since the
mixing time is polynomial in $n$. \end{proof}

Now, we go on to the statistical question: how do we demonstrate that
there is bias in some sample? We take our example from the idea of proving
discrimination to a judge, and we set it on $\alpha$- Centauri.

On $\alpha$-Centauri, there are three kinds of humanoids: red-haired ones,
blue-haired ones, and green-haired ones. The CSGHH (Centaurian Society for
Green Haired Humanoids) is suing company XYZ for hair-discrimination,
claiming that green-haired humanoids get paid less. The lawyers go to
court with statistics showing that the average pay for a green-haired
humanoid is $12.3$ units, while the average for other hair colors is
$12.5$ units. The number of employees at company XYZ is huge, so this is a
statistically significant difference, but it's difficult to convince a
judge of that. So the lawyers employ a never-before-seen argument, and win
the case. The argument runs as follows:

There are clearly two hypotheses: either there is or is not discrimination. Suppose not. Divide
the company randomly into small groups numbered with positive integers, and for each group
number $i$, let
\begin{equation}
\epsilon_i = \left\{ \begin{array}{ll}
    1   &   \mbox{if the group's highest earner has green hair} \\
    0   &   \mbox{otherwise}
            \end{array}
     \right.
\end{equation}

Let $p$ be the probability that the highest earner in a single group has green hair if there is
no discrimination, and take $l=\frac{1}{p}$. Then, divide the groups into blocks of $l$ and take
the and of small sets of blocks. Then or together these results in groups, and those in groups,
or those in groups, and continue alternating until you get the entire company:
\begin{equation}
[(\epsilon_1 \vee \dots \vee \epsilon_l)\wedge(\epsilon_{l+1}\vee \dots) \dots ]\wedge \dots
\end{equation}
The result will, with high probability, be $1$ if there is no discrimination, and $0$ otherwise.

This converts the problem into a similar combinatorial situation considered by Ajtai. We have a
sequence of ones and zeros, and we want to figure out if it has "too many" zeros. We take intervals
of appropriate length and proceed as above, giving a function that will tell if there are too many.
This is called bias amplification.

Back in our group theoretical world, we create the word $w$ based on the boolean formula we just
created, using our translation of logic into the group, and we're done. The word ends up being
close to what a group theorist would think of as a law on the group.

\end{document}