\documentclass[11pt]{article}
\usepackage{macros-course-lectures}

\lectureformat

\showsolutionstrue

\newcommand{\IQ}{I.Q.\@\xspace}

\begin{document}

\lecture{notes14}{Bounding Large Deviations from the Mean}{December 3, 2001}{\stamp}

\iffalse
\reading{Ross, ``A First Course in Probability'', Prentice-Hall, Sections 4.8,
8.3, 8.5; Motwani \& Raghavan 4.1--3.}
\fi

\section{The Probability of at Least One Event}\label{sc: one}

\subsection{General Bounds on the Probability}

Let $A_1, A_2, \dots, A_N$ be events over the same sample space.  
Let the random variable $T$ be the number of these events that occur.
What is $\pr{T \geq 1}$, the probability that at least $1$ event occurs?
Because the event $[T \geq 1]$ is precisely the same as the event $\union
A_i$, Boole's Inequality implies:

\begin{proposition}\label{fact:union}
  Let $A_1, A_2, \dots, A_N$ be events over the same sample space, and
  let the random variable $T$ be the number of these events that occur.
  Then
\[
    \pr{T \geq 1}  \leq  \sum_{i=1}^n \pr{A_i}.
\]
\end{proposition}
In words, the probability that at least one of the events occurs is at
most the sum of the event probabilities.  Although
Proposition~\ref{fact:union} is obvious, and in a sense trivial, it can be
useful and so is well worth remembering.

Proposition~\ref{fact:union} is weak for events with sizable probabilities.
For example, if we flip a fair coin three times, then we can conclude that
the probability of flipping heads at least once is at most $1/2 + 1/2 +
1/2 = 3/2$, which is not front-page news.  But if the events $A_i$ all
have relatively low probability, then Proposition~\ref{fact:union} can be
useful.  A key advantage is that the events $A_i$ need not be
independent---the only tools that we used in the derivation were Markov's
Theorem and linearity of expectation, and neither of these requires
independence.  This makes the result easy to apply.

For example, suppose that we want to compute the probability of a meltdown
at MIT's nuclear reactor on Albany Street.  First, we enumerate all events
$A_i$ that could lead to a meltdown, \eg operator error, earthquake,
terrorist attack, meteor strike, \etc\ Next, we determine, as best we can,
the probability of each type of catastrophe alone.
Proposition~\ref{fact:union} allows us to ignore tricky independence
issues---such as whether the terrorist team might be kept from the reactor
by an earthquake.  Proposition~\ref{fact:union} then says that the
probability of a meltdown is at most the sum of these event probabilities.

In addition to this general \emph{upper} bound on $\pr{T \geq 1}$, there
is also a trivial \emph{lower} bound which can occasionally be useful:
\begin{proposition}
Let $A_1, A_2, \dots, A_N$ be events over the same sample space, and let
the random variable $T$ be the number of these events that occur.  Then
\[
\pr{T \geq 1} \geq \max_{1 \leq i \leq n} \pr{A_i}.
\]
\end{proposition}
In words, the probability that at least one of the events occurs is at
least as large as the probability that any particular one of them occurs.
This follows immediately from the fact each event, $A_i$, is subset of the
event $[T \geq 1]$.

Of course, if the events are known to be independent, then a lower bound
close to one holds, as we show next.

\subsection{The Probability of At Least One Independent Event}

If the events $A_i$ are mutually independent, we can be much more precise
about the probability that one or more of them occur.  In fact, we will
show that if we expect several events to occur, then almost certainly at
least one event will occur.  Another way to say this is that if we expect
more than one event to occur, then the probability that no event occurs is
practically zero.  Specifically, we have:

\begin{theorem}\label{th:none}
Let $A_1, A_2, \dots A_N$ be independent events, and let $T$ be the
number of these events that occur.  The probability that none of the
events occur is at most $e^{-\expect{T}}$.
\end{theorem}

Interestingly, Theorem~\ref{th:none} does not depend on $N$, the number of
events.  It gives the same bound whether there are 100 events each with
probability 0.1 or 1000 events each with probability 0.01.  In both cases,
the expected number of events is 10, and so the probability of no event
occurring is at most $e^{-10}$ or about 1 in 22,000.  Note that the actual
probabilities are somewhat different in these two cases, indicating that
the given bound is not always tight.

Theorem~\ref{th:none} can be interpreted as a sort of ``Murphy's Law'': if
we expect some things to go wrong, then something probably will.  For
example, suppose that we are building a microprocessor, and the
fabrication process is such that each transistor is faulty mutually
independently with a probability of one in a million.  This sounds good.
However, microprocessors now contain about ten million transistors, so the
expected number of faulty transistors is 10 per chip.  Since we expect
some things to go wrong, something probably will.  In fact,
Theorem~\ref{th:none} implies that the probability of a defect-free a chip
is less than 1 in 22,000!

There are two simple observations used in proving Theorem~\ref{th:none}.
First, by DeMorgan's Law:
\begin{equation}\label{DeM}
[T = 0] = \bar{A_1 \union A_2 \union \cdots \union A_N}
= \bar{A_1} \cap \bar{A_2} \cap \dots \cap \bar{A_N}
\end{equation}
Second, note that
\[
T = T_1 + T_2 + \dots + T_N,
\]
where $T_i$ is the indicator variable for the event $A_i$.  But
$\expect{T_i} = 1\cdot\pr{A_i} + 0\cdot \pr{\bar{A_i}} = \pr{A_i}$, so by
linearity of expectation, it follows that
\begin{equation}\label{Tsum}
\expect{T} = \sum_{i=1}^N \pr{A_i}.
\end{equation}

We also use the fact that 
\begin{equation}\label{1+xe}
1 + x \leq e^x
\end{equation}
for all $x$, which follows from the Taylor expansion
\[
e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots.
\]

\begin{proof}
\begin{align*}
\pr{T = 0}
  & =  \pr{\bar{A_1} \cap \bar{A_2} \cap \dots \cap \bar{A_N}} & \text{(by~(\ref{DeM}))}\\
  & =  \prod_{i=1}^n \pr{\bar{A_i}} & \text{(mutual independence)}\\
  & =  \prod_{i=1}^n 1 - \pr{A_i} & \text{(complement rule)}\\
  & \leq  \prod_{i=1}^n e^{-\pr{A_i}} & \text{(by~(\ref{1+xe}))}\\
  & =  e^{-\sum_{i=1}^n \pr{A_i}} & \text{(exponent algebra)}\\
  & =  e^{-\expect{T}} & \text{(by~(\ref{Tsum})).}
\end{align*}
\end{proof}


\section{Chernoff Bounds}

\subsection{Probability of at least \emph{k} events}

Now we consider the more general question than the probability that one
event occurs, namely, the probability that $k$ events occur, still
assuming mutual independence of the events $A_i$.  In other words, what is
$\pr{T \geq k}$, given that the events $A_i$ are mutually independent?

For example, suppose we want to know the probability that at least $k$
heads come up in $N$ tosses of a coin.  Here $A_i$ is the event that the
coin is heads on the $i$th toss, $T$ is the total number of heads, and
$\pr{T \geq k}$ is the probability that at least $k$ heads come up.

As a second example, suppose that we want the probability of a student
answering at least $k$ questions correctly on an exam with $N$
questions.  In this case, $A_i$ is the event that the student answers
the $i$th question correctly, $T$ is the total number of questions
answered correctly, and $\pr{T \geq k}$ is the probability that the
student answers at least $k$ questions correctly.

There is an important difference between these two examples.  In the first
example, all events $A_i$ have equal probability, \ie the coin is as likely
to come up heads on one flip as on another.  So $T$ has a binomial
distribution whose tail bounds we have already characterized in
\href{http://theory.lcs.mit.edu/classes/6.042/fall01/lectures/l12.pdf}{Notes
12}.

In the second example, however, some exam questions might be more
difficult than others.  If Question 1 is easier than Question 2, then the
probability of event $A_1$ is greater than the probability of event $A_2$.
In this section we develop a method to handle this more general situation
in which the events $A_i$ may have different probabilities.

We will prove that the number of events that occur is almost never
much greater than the expectation.  This result is called the Chernoff
Bound.  For example, if we toss $N$ coins, the expected number of
heads is $N/2$ heads.  The Chernoff Bound implies that for
sufficiently large $N$, the number of heads is almost always not much
greater than $N/2$.

A nice feature of the Chernoff Bound is that we do not even need to
know the probability of each event $A_i$ or even the number of events
$N$; rather, we need only the expected number of events that occur and
the fact that the events are mutually independent.

\subsection{Statement of the Bound}

We state Chernoff's Theorem in terms of Bernoulli variables instead of
events.  However, we can regard $T_i$ as an indicator for the event $A_i$.
\begin{theorem}[Chernoff Bound] \label{Chbnd}
  Let $T_1, T_2, \dots, T_N$ be mutually independent Bernoulli
  variables, and let $T = T_1 + T_2 + \cdots + T_N$.  Then for all $c
  \geq 1$, we have
\begin{equation}\label{Chbndeq}
  \pr{T \geq c \expect{T}} \leq e^{- (c\ln c -c + 1) \expect{T}}.
\end{equation}
\end{theorem}

\iffalse
(A similar bound holds for $\pr{T \leq c \expect{T}}$, where $c < 1$; we
omit this here.)  See Motwani & Raghavan text.
\fi

The formula for the exponent in the bound is a little awkward.  The
situation is simpler when $c = e = 2.718\dots$.  In this case, $c\ln c - c
+ 1 = e \ln e - e + 1 = e\cdot 1 - e +1 =1$, so we have as an immediate
corollary of Theorem~\ref{Chbnd}:
\begin{corollary}\label{cor:ebound}
Let $T_1, T_2, \dots, T_N$ be mutually independent Bernoulli variables,
and let $T = T_1 + T_2 + \cdots + T_N$.  Then
\[
\pr{T \geq e \expect{T}} \leq e^{- \expect{T}}.
\]
\end{corollary}
We will prove the Chernoff Bound shortly.  First, let's see an example of
how it is used.

\subsection{Example: Pick 4}

There is a lottery game called Pick 4.  In this game, each player
picks 4 digits, defining a number in the range 0 to 9999.  A winning
number is drawn each week.  The players who picked the winning number
win some cash.  A million people play the lottery, so the expected
number of winners each week is
\[
\frac{1}{10,000} \cdot 1,000,000 = 100.
\]
However, on some lucky day thousands of people might all pick the winning
number, costing the lottery operators loads of money.  How likely is this?

Assume that all players pick numbers uniformly and mutually
independently.  Let $T_i$ be an indicator variable for the event that
the $i$th player picks the winning number.  Let $T = T_1 + T_2 +
\cdots + T_N$.  Then $T$ is the total number of players that pick the
winning number.  As noted above, an average of 100 people win each
week, so $\expect{T} = 100$.  We can use Corollary~\ref{cor:ebound} to
bound the probability that number of winners is greater than 272 as
follows:
\begin{displaymath}
  \pr{T \geq 272} \leq \pr{T \geq e\expect{T}} \leq e^{- Ex(T)} = e^{-100}.
\end{displaymath}
The probability of 272 or more people winning is absurdly small!  It
appears that the lottery operators should not worry that ten thousand
people will pick correctly one day!

But there is a catch.  The assumption that people choose Pick 4
numbers uniformly and mutually independently is empirically false;
people choose certain ``favorite'' numbers far more frequently than
others.

Chernoff used this fact in devising a scheme to actually make money on
the lottery.  In this case, a fraction of all money taken in by the
lottery was divided up equally among the winners.  A bad strategy
would be to pick a popular number.  Then, even if you pick the winning
number, you must share the cash with many other players.  A better
strategy is to pick a lot of unpopular numbers.  You are just as
likely to win with an unpopular number, but will not have to share
with anyone.  Chernoff found that peoples' picks were so highly
correlated that he could actually turn a 7\% profit by picking
unpopular numbers!

\subsection{The constant in the exponent}

For general $c$, what can we say about the factor $c\ln c -c +1$ in the
exponent?  First, note that when $c=1$, the exponent factor equals $1
\cdot 0 - 1 + 1 = 0$.  This means that the Chernoff bound cannot say
anything useful about the probability simply of exceeding the mean.
However, the exponent factor increases with $c$ for $c > 1$.  This follows
because its derivative respect to $c$ is positive:
\[
\frac{d(c\ln c - c + 1)}{dc} = (\frac{c}{c} + \ln c) - 1 = \ln c > 0
\]
when $c>1$.  In particular, for any $c>1$, the factor $(c\ln c -c + 1)$ in
the exponent is positive.

Let's consider the case of $c$ close to 1, say $c=1+\epsilon$.  Then a
Taylor expansion gives:
\begin{align*}
c\ln c - c + 1  &= (1+ \epsilon) \ln(1+\epsilon) - (1+\epsilon) + 1\\
  &= (1+ \epsilon) (\epsilon- \frac{\epsilon^2}{2}+ \frac{\epsilon^3}{3}-
  \frac{\epsilon^4}{4} + \cdots) - \epsilon\\
  &= (\epsilon - \frac{\epsilon^2}{2}+ \frac{\epsilon^3}{3}-
  \frac{\epsilon^4}{4} + \cdots) + (\epsilon^2 - \frac{\epsilon^3}{2}+ \frac{\epsilon^4}{3}-
  \frac{\epsilon^5}{4} + \cdots) - \epsilon\\
  & = \frac{\epsilon^2}{2} - \frac{\epsilon^3}{2 \cdot 3} + 
  \frac{\epsilon^4}{3 \cdot 4} -   \frac{\epsilon^5}{4 \cdot 5} +\cdots.
\end{align*}
In particular, for very small $\epsilon$, we have $c\ln c - c + 1 \approx
\epsilon^2/2$.  In fact one can prove the following:
\begin{lemma}
  For any $0< \epsilon < 1$, 
  $\pr{T \geq (1+\epsilon) \expect{T}} < e^{-\epsilon^2 \expect{T}/3}$.
\end{lemma}
In other words, the probability of deviation above the mean by a fraction
$\epsilon$ decays \emph{exponentially} in the expected value, for any
$\epsilon > 0$.

Another useful observation is that the Chernoff bound starts to ``kick
in'' when $\epsilon \approx 1/\sqrt{\expect{T}}$.  In other words, the
typical deviation of our random variable is going to be about the
square root of its expectation.  This is in line with our analysis of
binomial random variables: the number of heads in $n$ unbiased coin
flips has expectation $n/2$, but has standard deviation $\sqrt{n}/2$,
or roughly the square root of the expectation. 

\subsection{Proof of the Bound}

The Chernoff Bound uses an ingenious trick along the lines of the way we
derived Chebyshev's Bounds:
\begin{equation}\label{TcT}
  \pr{T \geq c \expect{T}} = \pr{c^T \geq c^{c \expect{T}}}
  \leq \frac{\expect{c^T}}{c^{c \expect{T}}}
\end{equation}
The first step may be a shocker; we exponentiate both sides of the
inequality in the probability by $c$.  Since the new inequality describes
the same event as the old, the probabilities are the same.  The second
step uses Markov's Theorem.

Recall that Markov's Theorem sometimes gives weak bounds and sometimes
gives tight bounds.  The motivation for the first step is to alter the
distribution of the random variable $T$ to hit the ``sweet spot'' of
Markov's Theorem.  That is, Markov's Theorem gives a tighter bound on
the random variable $c^T$ than on the original variable $T$.  We used
the same trick in Chebyshev's theorem: we looked at the expectation of
$T^2$ instead of that of $T$, because that gave us more powerful
results.

All that remains is to evaluate $\expect{c^T}$.  To do this we need a Lemma:
\begin{lemma}\label{RSfg}
If $R$ and $S$ are independent random variables, and $f$ and
$g$ are \emph{any} real-valued functions on the reals, then $f(R)$ and
$g(S)$ are independent random variables.
\end{lemma}
We leave the proof of Lemma~\ref{RSfg} as a routine exercise.

So now we have
\begin{align}
\expect{c^T}
        & =    \expect{c^{T_1 + T_2 + \cdots + T_N}} & \text{(def of $T$)}\notag\\
        & =    \expect{c^{T_1}} \cdot \expect{c^{T_2}} \cdots
        \expect{c^{T_N}}
            & \text{(mutual independence of the $T_i$'s and Lemma~\ref{RSfg})}\notag\\
        & =   \prod_{i=1}^N \expect{c^{T_i}}\label{cT3}
\end{align}
But
\begin{align}
\expect{c^{T_i}}
        & =    c^1 \pr{T_i = 1} + c^0 \pr{T_i = 0} & \text{(by def)}\notag\\
        & =    c \pr{T_i = 1} + (1 - \pr{T_i = 1}) & \text{(complement
        rule, since $T_i = 0$ iff $T_i \neq 1$)} \notag\\
        & =    1 + (c - 1) \pr{T_i = 1} \notag\\
        & \leq  e^{(c-1) \pr{T_i = 1}} & \text{(because~(\ref{1+xe})
        $1+x\leq e^x$)}\notag\\
        & =  e^{(c-1) \expect{T_i}} & \text{(since $T_i$ is an indicator variable)}.\label{boundEcT}
\end{align}

We can now substitute this bound~(\ref{boundEcT}) into~(\ref{cT3}).
\begin{align}
\expect{c^T}
        &\leq  \prod_{i=1}^N e^{(c-1) \expect{T_i}} & \text{(by~(\ref{cT3}) \&~(\ref{boundEcT}))}\notag\\
        & =    e^{\sum_{i=1}^N (c-1) \expect{T_i}} \notag\\
        & =    e^{(c-1) \sum_{i=1}^N \expect{T_i}} \notag\\
        & =    e^{(c-1) \expect{\sum_{i=1}^N T_i}} & \text{(linearity of expectation)}\notag\\
        & =    e^{(c-1) \expect{T}} & \text{(def of $T$)}\label{ec-1T}.
\end{align}

Now we can substitute this bound~(\ref{ec-1T}) into the Markov
inequality~(\ref{TcT}) we started with to obtain
\begin{equation}\label{ccT}
\pr{T \geq c \expect{T}} \leq \frac{e^{(c-1) \expect{T}}}{c^{c \expect{T}}}.
\end{equation}
Simplifying the righthand side of~(\ref{ccT}) completes the proof
of~(\ref{Chbndeq}):
\begin{eqnarray*}
\frac{e^{(c-1) \expect{T}}}{c^{c \expect{T}}}
        & = & \frac{e^{(c-1) \expect{T}}}{(e^{\ln c})^{c \expect{T}}}\\
        & = &   e^{(c-1) \expect{T} - c \ln c \expect{T}}\\
        & = &   e^{-(c\ln c - c + 1) \expect{T}}.
\end{eqnarray*}


\subsection{Example:  A Phone Network Problem}

Suppose that there is a phone network that handles a billion calls a
day.  Some of these call are routed through a certain switch.  The
exact number of calls passing through this switch is somewhat random
and fluctuates over time, but on average the switch handles a million
calls a day.

Our problem is to set the capacity of the switch; that is, we must
determine the number of calls that a switch is able to handle in a
day.  If we make the capacity too small, then some phone calls will
not go through.  On the other hand, if we make the capacity too large,
then we are wasting money.  Of course, we cannot rule out a freak
situation in which a huge number of calls are all coincidentally
routed through the same switch, thus overloading it.  However, we would like to guarantee that a switch is rarely
overloaded.

Assume that each call has some probability of passing through a
particular switch.  In particular, let $T_i$ be an indicator variable
for the event that the $i$th call passes through the switch.  That
is, $T_i = 1$ if the call is routed through the switch, and $T_i = 0$
if the call does not pass through the switch.  Then the total call
load on the switch is $T = T_1 + T_2 + \cdots + T_N$.  We do not know
the exact probability that the switch handles the $i$th call, but we
are given that the switch handles an average of a million calls a day;
that is, $\expect{T} = 1,000,000$.

We will make the crucial assumption that the random variables $T_i$
are mutually independent; that is, calls do or do not pass through the
switch mutually independently.

\subsubsection{How to Build One Switch}

We can now compute the probability that the load on a switch
fluctuates upwards by 1\% due to the randomness of calling patterns.
Substituting $c = 1.01$ and $\expect{T} = 1,000,000$ into the Chernoff
Bound gives:
\begin{eqnarray*}
\pr{\text{particular switch overloaded}}
        & = & \pr{T \geq 1.01 \cdot 1,000,000} \\
&\leq&  e^{-(1.01 \ln 1.01 -1.01 + 1) \cdot 1,000,000}\\
& < &   e^{-1.01 (0.00004934) \cdot 1,000,000}\\
& < &   2.3 \cdot 10^{-22}.
\end{eqnarray*}
The probability that the load on the switch ever rises by even 1\% is
unbelievably small!  (A terrorist attack on Albany Street during an
earthquake is far more likely.)  If we build the switch with capacity
only 1\% above the average load, then the switch will (almost) never
be overloaded.

The strength of this result relies on the huge expected number of
calls.  For example, suppose that the average number of calls through
the switch were 100 per day instead of 1,000,000.  Then every million
in the above calculation would be replaced by a hundred; no other
numbers change.  The final probability of overloading the switch would
then be bounded above not by $2.3 \cdot 10^{-22}$, but by $0.995$!  If
the switch handles only 100 calls on an average day, then the call
load can very often fluctuate upward by 1\% to 101 or more.

\subsubsection{How to Build the Network}

We now know that building 1\% excess capacity into a switch ensures
that it is effectively never overloaded.  The next problem is to
guarantee that no switch in the entire network is overloaded.  Suppose
that are 1000 switches, and every switch handles an average of a
million calls a day.

Previously, we saw that the probability that some event occurs is at
most the sum of the event probabilities.  In particular, the
probability that some switch is overloaded is at most the sum of the
probabilities that each of the 1000 switches is overloaded.
Therefore, we have:
\begin{displaymath}
  \pr{\text{some switch overloaded}}
  \leq 1000 \cdot \pr{\text{particular switch overloaded}}
  < 2.3 \cdot 10^{-19}.
\end{displaymath}
This means that building 1\% excess capacity into every switch is
sufficient to ensure that no switch is ever overloaded.

The above results are of limited practical value, becuae calls typically
do not pass through a switch mutually independently.  For example, after
an earthquake on Albany Street, everyone would call through the eastern
Cambridge switchboard to check on friends and family.  Furthermore, there
are many more phone calls on certain dates like Mother's Day.  On such
occasions, 1\% excess capacity is insufficient.

%\section{Chernoff bounds and binomial tails}

\section{A Generalized Chernoff Bound}

\iffalse

\subsection{Deviation of an Unbiased Binomial Distribution}

The Chernoff bound also applies to a sum of independent events with the
same probability, $1/2$.  This of course just means that the number of
events has an unbiased binomial distribution.  Although we already have
estimates on the tail of the binomial distribution in
\href{http://theory.lcs.mit.edu/classes/6.042/fall01/lectures/l12.pdf}{Notes
12}, it's instructive to apply the Chernoff-bound approach to this
familiar example.

\begin{theorem}\label{binom dev}
If $R$ has an unbiased binomial distribution, then for $c\geq 1$,
\[
\pr{R-\expect{R} \geq c\sigma_R} \leq e^{-c^2/2}.
\]
\end{theorem}

\textbf{From the Chernoff bound, we know that this probability is at most
$e^{-c \ln c}$.  The new bound, $e^{-c^2/2}$, is noticably smaller as $c$
increases.  CHECK THIS.}

For example, suppose that the 6.042 final consists entirely of
true/false questions\footnote{Ha!  Fat chance.} and students guess
answers uniformly and mutually independently.  A student's score on
each question is a uniform Bernoulli variable (0 or 1).  A student's
exam score is a sum of these Bernoulli variables, and so is a random
variable with an unbiased binomial distribution.

\textbf{REVISE TO USE CHERNOFF NOT CHEBY:} Given these assumptions, what
is the probability that a student scores two standard deviations above the
mean?  By Chebyshev's Theorem the probability is at most 1 in 4.  However,
we can get a better bound using the fact above.
\begin{displaymath}
  \pr{R - \expect{R} \geq 2 \sigma_R} < e^{-2^2/2} = e^{-2}
\end{displaymath}
The probability that a student scores 2 standard deviations above the
mean on this exam is less than 1 in 7.

The difference is more striking if we look at greater deviations.  For
example, the probability that a student scores 6 standard deviations above
the mean is at most $e^{-6^2/2} = e^{-18}$, which is less than one in 65
million.  The corresponding bound from Chebyshev's Theorem is
$1/37$.


\begin{proof}
Let $X_i \eqdef 2R_i - 1$ and $X \eqdef \sum_{i=1}^n X_i$.  So $X=2R-n$.

Now
\begin{eqnarray*} 
\pr{R-\expect{R} \geq c \sigma_R} &=& \pr{R-\frac{n}{2} \geq c \frac{\sqrt{n}}{2}}\\
  &=& \pr{2R-n \geq c \sqrt{n}}\\
  &=& \pr{X \geq c \sqrt{n}}.
\end{eqnarray*}
So we need only show that
\begin{equation}\label{Xcn}
\pr{X \geq c \sqrt{n}} \leq e^{-c^2/2}.
\end{equation}

But $X \geq c\sqrt{n}$ iff $e^{tX} \geq e^{tc\sqrt{n}}$
for every $t > 0$.  Applying Markov's inequality to $e^{tX}$, yields
\begin{equation}\label{etX}
\pr{e^{tX} \geq e^{tc\sqrt{n}}} \leq \frac{\expect{e^{tX}}}{e^{tc\sqrt{n}}}.
\end{equation}
Now
\begin{align}
\expect{e^{tX}} & = \expect{e^{t\sum_{i=1}^nX_i}} & \text{(def of $X$)}\notag\\
     & =  \expect{\prod_{i=1}^n e^{tX_i}} & \text{(exponent algebra)}\notag\\
     & =  [\expect{e^{tX_i}}]^n & \text{(mutual independence of $X_i$'s and Lemma~\ref{RSfg})}.\label{En}
\end{align}
Notice that from the Taylor expansions of $e^t$ and $e^{-t}$, we have
\[
\frac{e^t + e^{-t}}{2} \leq e^{t^2/2}.  
\]
Therefore
\begin{equation}\label{sinh}
\expect{e^{tX_i}} = \frac{e^t + e^{-t}}{2} \leq e^{t^2/2}.
\end{equation}
Combining~(\ref{sinh}) with~(\ref{En}) yields
\begin{equation}\label{et2}
\expect{e^{tX}} \leq (e^{t^2/2})^n.
\end{equation}

Finally, from~(\ref{et2}) and our initial Markov inequality~(\ref{etX}),
we conclude
\begin{equation}\label{etn}
\pr{X \geq c\sqrt{n}} \leq \frac{(e^{\frac{t^2}{2}})^n}{e^{tc\sqrt{n}}} = 
e^{\frac{t^2n}{2} - tc\sqrt{n}}.
\end{equation}
Since we can choose any positive $t$, we choose $t$ to minimize the
exponent in~(\ref{etn}).  A little calculus shows that the desired value
is $t = c/\sqrt{n}$.  Substituting this value of $t$ into~(\ref{etn}) and
simplifying yields~(\ref{Xcn}), as required.

\end{proof}

\subsection{Generalized Chernoff}  

The theorem from the previous section can be generalized as follows.  \fi

Chernoff's Theorem applies only to sums of Bernoulli (0-1-valued) random
variables.  It can, however, be extended to apply to sums of random
variables with considerably more arbitrary distributions.  We state one
such generalization in Theorem~\ref{GenCh} below.  We omit its proof,
noting only that the proof is similar to that of the Chernoff bound of
Theorem~\ref{Chbnd}.  Note that the bound of Theorem~\ref{GenCh} is not
quite as good as the Chernoff bound, but it is more general in what it
covers.

\begin{theorem}\label{GenCh}
Let $R_1,\ldots,R_n$ be independent random variables with
$0\leq R_i \leq 1$. Let $R=\sum_{i=1}^n R_i$.
Then 
\[
\pr{R - \expect{R} \geq c\sqrt{n}} \leq e^{-c^2/2}.
\]
\end{theorem}

\begin{example} Load balancing. 

A set of $n$ jobs have to be scheduled on a set of $m$ equally fast
processing machines.  The length (processing time) of the $i$th job is
some number $L_i$ in the range $[0,1]$.  We would like to schedule the
jobs on the machines so that the load on the machines is reasonably
balanced.  This means we would like the load on every machine to be not
much more than the average load $L \eqdef \sum_{i=1}^n L_i/m$.  Finding an
optimally balanced assignment is a notoriously time-consuming task even
when we know all the processing times.  But commonly, successive jobs have
to be assigned to machines without knowing how long the later jobs will
take, and in that case it is impossible to guarantee a balanced load.

We will approach this problem of load balancing using the simplest random
strategy: we independently assign each job to a randomly selected machine,
with each machine equally likely to be selected.  It turns out that for
many job scheduling problems, this strategy is almost certain to do very
well, even though it does not even take into account the number of jobs
nor their processing times.

To see why the simple random strategy does well, notice that, since each
job has probability $1/m$ of being assigned to any given machine, the
expected load on a machine is precisely $1/m$th of the total load.  That
is, the \emph{expected} load per machine is precisely the \emph{average}
load, $L$.  Now consider any machine, $P$, and define $R_i$ to be the time
$P$ spends processing the $i$th job.  That is, $R_i = L_i$ if the $i$th
job gets assigned to machine $P$, otherwise $R_i = 0$.  So the total load
on machine $P$ is $\sum_{i=1}^n R_i$.   From the generalized Chernoff
bound, we conclude
\[
\pr{\mbox{(load on machine $P$)} - L \geq c\sqrt{n}} \leq e^{-c^2/2}.
\]
Now by Boole's inequality,
\begin{eqnarray*}
\pr{\mbox{the load on some machine is } \geq L +  c\sqrt{n}}
    &\leq &
 \sum_{k=1}^m \pr{\mbox{(load on machine $k$)} \geq L + c\sqrt{n}} \\
&\leq & m e^{-c^2/2}.
\end{eqnarray*}

If we choose $c = \sqrt{2\ln m}+6$, say, so that $c^2/2 \geq \ln m + 18$, then
\begin{eqnarray*}
\lefteqn{\pr{\mbox{(load on each machine)} \leq L + c \sqrt{n}}}\\
 & \geq & 1 - m e^{-\ln m -18}\\
 & = & 1 - e^{\ln m} e^{-\ln m -18}\\
 & = & 1 - e^{-18} = 0.99999998\dots.
\end{eqnarray*}
Hence we can be 99.999998\% sure that every machine will have load at most
$L+(\sqrt{2\ln m }+6)\sqrt{n}$.  For many values of $n$ and $m$ this is
comes very close to balancing the loads on all the machines.  For example,
if $m=10$, $n=5000$, and $L=300$, the maximum load on any machine will
almost surely not exceed 332.  (In fact it is likely to be even less---we
have been fairly crude in our bounds.)

\end{example}

\iffalse

\section{The Exponential Distribution}

The exponential distribution is an important one that arises time and
again in the study of computer systems; you will see it in 6.033 for
example.  It arises naturally whenever you are interested in the
aggregate behavior of a large system.  So it's quite important to know
what it is.  Unfortunately, this distribution is a \emph{continuous}
probability distribution.  We don't have time to develop the theory
for these distributions, so some of what we now present will have to
be accepted without proof.

\subsection{Derivation}

Let's consider a particular example.  Consider a system such as a
computer that has a certain chance of failure at any given time.  We
are told that on average this system sees $\lambda$ failures per year,
and want to model the probability distribution associated with the
failure time of the system.  A particularly simple model is to break
time up into small intervals of some length $\delta$, and to suppose
that in each interval, the probability of the system failing, given
that it has not yet failed, is some constant $p$.  In other words, we
flip an independent coin in each interval, and the system fails when
the coin comes up heads.

Specifically, lets consider a time period of length $t$ (in which we
expect to see $\lambda t$ failures).  Let us break it up into $n$
intervals of length $t/n$.  If we declare a failure probability of $p$
in each interval, then the expected number of failures over our $n$
intervals will be $np$.  So in order to meet our goal of modelling
$\lambda t$ failures in time $t$, we set $np=\lambda t$, or $p=\lambda
t/ n$.

Now we can determine the probability that no failures have occurred by
time $t$ (small interval number $n$).  Let $S_i$ denote the event that
the system stays working in the $i$th interval, assuming that it
was working until then.  Then the probability that the system is
still working at interval $n$ is just the probability that it has no
failure by that time, which can be written as
\begin{align*}
\pr{S_1 \cap S_2\cap S_3\cap \cdots\cap  S_n}
&= \pr{S_1} \cdot \pr{S_2 \mid S_1} \cdot \pr{S_3 \mid S_1 \cap S_2}
  \cdots \pr{S_n \mid S_1 \cap S_2 \cdots \cap S_{n-1}}\\
&= (1-p)^{n}\\
&= (1-\lambda t/n)^{n}.
\end{align*}
Of course, there is no particularly ``natural'' choice for $n$.  It is
convenient to take $n$ arbitrarily large (resulting in infinitesimally
small intervals), and work with the limiting value:
\begin{align*}
\pr{S_1 \cap S_2\cap S_3\cap \cdots \cap  S_n}
&= (1-\lambda t/n)^{n} \\
&\approx e^{-\lambda t}.
\end{align*}
This formula meets some quick sanity checks.  In particular, the
probability that the failure time exceeds 0, \ie\ that the system is
initially working, is $e^{-0}=1$, while the probability of never
failing, \ie\ that the failure time is infinite, is $e^{-\infty}=0$.

Let us write $X$ for the time of first failure of our system.  We have
just argued that
\[
\pr{X > t} = e^{-\lambda t}.
\]
This distribution on $X$ is known as the \emph{exponential
  distribution}.  We're taking a bit of a leap here, by considering a
probability distribution on a continuous, real-valued random variable.
This raises disturbing questions---for example, what is $\pr{X=t}$ for
some particular $t$?  Answering this question carefully would force a
digression into calculus and measure theory.  We'll leave that to
another class, and simply forge ahead.

\subsection{Expectation of the Distribution}

Given our model, it is natural to ask about the expected time $\expect{X}$
of the first failure of our system.  This quantity is known as the
system's \emph{Mean Time to Failure (MTTF)}.  We don't really know how
to compute the expectation of a continuous random variable, but the
following analogy turns out to be true: just as for a random variable
$Y$ over the natural numbers, $\expect{Y} = \sum_k \pr{Y \ge k}$, it turns
out that
\begin{align*}
\expect{X} &= \int_0^\infty  \pr{X>t} dt\\
&= \int_0^\infty  e^{-\lambda t}\,dt\\
&= \left. -\frac{1}{\lambda} e^{-\lambda t} \right|_0^\infty\\
&= \frac{1}{\lambda}.
\end{align*}
In other words, given a failure rate of $\lambda$, we expect a failure
every $1/\lambda$ time steps, which seems quite reasonable.  We'll
state this as a theorem:

\begin{theorem}
If $X$ is exponentially distributed with rate $\lambda$, then
$\expect{X}=1/\lambda$.
\end{theorem}

\subsection{Memorylessness}


The fundamental assumption of the exponential distribution is
\emph{memorylessness}: we assume that the failure within any
particular interval is \emph{independent} of all the past history.
This is an extremely strong assumption.  It is certainly convenient,
and sometimes it even turns out to be true.  For example, the decay
time of a radioactive particle (which can be thought of as a
``failure'' of the particle) follows an exponential distribution.  The
particle has no memory of how long it has been in a nondecayed state;
if it undecayed now it has a small probability of decaying in the next
interval, regardless of the past.  The MTTF for a particle is related
to its half-life.  The half life of an isotope is the time it takes
for the amount of particles of that isotope to be reduced by half in
expectation; this is just the time $t$ such that probability of the
particle surviving is 1/2.  This requires $e^{-\lambda t} = 1/2$, or
$t=(\ln 2)/\lambda$.

Exponential distributions are also used to model the arrival of ``new
events''---a new packet at a computer, a new bus at a bus-stop, a
birth at a hospital.  In these models, the key memoryless assumption
must be evaluated carefully.  For example, many hardware products
suffer from ``infant mortality''---undetected manufacturing defects
cause frequent early failures, after which any product that survuves
this early winnowing is likely to turn out more reliable.  But even
when the assumptions turns out to be false, the exponential
distribution often provides a good first approximation for getting a
handle on the problem.

Another way to look at the memoryless property is the following.
Suppose we are told that no failure occurs after time $t$.  What can
we say about the probability that the computer is operating after time
$t+s$?  This is simply a conditional probability calculation:
\begin{align*}
\pr{X > t+s \mid X > t} &= \frac{\pr{X > t+s}}{\pr{X>t}}\\
&= \frac{e^{-\lambda(t+s)}}{e^{-\lambda t}}\\
&= e^{-\lambda s}\\
&= \pr{X>s}
\end{align*}
If we know the system survives until time $t$, then its probability
distribution is simply an exponential distribution based at time $t$,
rather than time $0$.

\subsection{Redundancy}

In an attempt to make systems more reliable, people sometimes yoke
several identical systems together.  For example, the space shuttle
has three identical computers working at all times.  If a single
computer fails and starts producing wrong answers, the other two can
join together to outvote it.  But if two fail, all bets are off.
Supposing the failure distribution for each computer is independent
and exponential with rate $\lambda$, this raises two interesting
questions: first, when might we expect the first failure of one of the
three computers, and second, when might we expect two failures, which
puts the shuttle out of commission?

Let $X_1$, $X_2$, and $X_3$ denote the failure times of the three
computers, and let $Y_1$ denote the failure time of the first to fail,
that is $Y_1=\min X_1, X_2, X_3$.  Then since the three random
variables $X_i$ are independent,
\begin{align*}
\pr{Y_1 > t} &= \pr{X_1 > t \, \cap X_2 > t \, \cap \, X_3 > t}\\
&= \pr{X_1 >t}\cdot \pr{X_2 > t} \cdot \pr{X_3 > t}\\
&= e^{-\lambda t} \cdot e^{-\lambda t} \cdot e^{-\lambda t}\\
&= e^{-3\lambda t}
\end{align*}

In other words, the random variable $Y_1$ is exponentially
distribution with rate $3\lambda$.  This makes sense: if 3 systems
each expected $\lambda$ failures per time step, then the 3 together
should expect 3 times as many failures.  Our expectation calculation
above immediately yields the expected time of the first failure:
$1/3\lambda$.  This is a specific instance of a general theorem.  Note
that this theorem applies even if the random variables have
\emph{distinct} rates:

\begin{theorem}
If $X_1,\dots,X_n$ are independent exponential random variables with
rates $\lambda_1,\dots,\lambda_n$, then $\min X_1,\dots,X_n$
is an exponential random variable with rate
$\lambda_1+\cdots+\lambda_n$
\end{theorem}


Now let's consider the second failure.  This is more complicated.
Suppose that we know the first failure is at time $t$, and that
computer 3 is the one that failed.  The second failure occurs when one
of the remaining two computers fails.  Let $Y_2$ denote the time of
this second failure.  We can analyze $Y_2$ by considering the
\emph{difference} $Y_2-Y_1$.  Our declaration that the first failure
occurred at $t$ means that we know $X_1>t$ and $X_2>t$.  By the
memoryless property of the exponential distribution, this means that
the failure times of the two remaining computers \emph{beyond time
  $t$} are exponentially distributed with rate $\lambda$.  It follows
that the \emph{minimum} of these two failure times beyond time time is
exponentially distributed with rate $2\lambda$.  Therefore, the
expected time that the two computers survive beyond time $t$ is
$1/2\lambda$.  It follows that the expected survival time of the
overall system is
\begin{align*}
\expect{Y_2} &= \expect{Y_1}+\expect{Y_2-Y_1}\\
&= 1/3\lambda + 1/2\lambda\\
&= 5/6\lambda
\end{align*}

This isn't even as good as the MTTF of $1/\lambda$ for a single
computer!  Perhaps the NASA builders are hoping that when computers
fail, they stop producing conflicting answers.  In this case the
shuttle can keep flying until the final computer fails.  Arguing as
above, the time for the last computer to fail once the other two have
failed is exponentially distributed with mean $\lambda$, meaning that
the MTTF for the entire set of 3 computers is
$1/3\lambda+1/2\lambda+1/\lambda = 11/6\lambda$, a modest improvement.
This type of replication has limited benefits, however: it is easy to
generalize and show that the MTTF for the last of $n$ replicas of the
system is only $H_n \approx \ln n$.
\fi

\section{The Poisson Approximation}

We've worked with the binomial distribution, which measures the
probability of $k$ special outcomes occur in a sequence of $n$ trials.  In
this section we'll consider a closely related and widely applicable
distribution known as the \emph{Poisson distribution}.  The Poisson
distribution is typically used to model the number of arrivals of
communication packets at a network node in a given time interval, the
number of decaying particles in a radioactive sample in a given time
interval, or the distribution of the number of failures of the system
over a particular time interval.  

Let's consider a particular example.  Suppose that we want to model the
arrival of packets at an internet router.  We know that on average the
router handles $\lambda=10^7$ packets per second.  Given this expected
value, how can we model the actual distribution of packet arrivals in a
second?  One possible model is to break up each second into tiny intervals
of size $\delta>0$ seconds, so there are a large number, $n = 1/\delta$,
of tiny intervals.  Then we declare that in each tiny interval, a packet
arrives with probability $\lambda\delta$ (this gives the right expected
number of arrivals).  Under this model, the number of intervals $X$ in
which a packet actually arrives has a binomial distribution:\footnote{Note
that this is not quite the same as counting the number of arrivals, since
more than one packet may arrive in a given interval.  But if the interval
is tiny, this is so unlikely that we can ignore the possiblity.}
\begin{equation}\label{pXk}
\pr{X=k} =
\binom{1/\delta}{k}(\lambda\delta)^k(1-\lambda\delta)^{1/\delta-k}
\end{equation}
Now we let $\delta$ become infinitesimally small (while
holding $k$ fixed) and make use of three approximations:
\begin{eqnarray*}
\binom{1/\delta}{k} &\approx & \frac{(1/\delta)^k}{k!}\\
(1-\lambda\delta)^{1/\delta} &\approx & e^{-\lambda}\\
1 - \delta k & \approx & 1.
\end{eqnarray*}
Plugging these approximations into~(\ref{pXk}) yields
\begin{align}
\pr{X=k} &=
\binom{1/\delta}{k}(\lambda\delta)^k(1-\lambda\delta)^{1/\delta-k}\notag\\
&=\binom{1/\delta}{k}(\lambda\delta)^k(1-\lambda\delta)^{(1-\delta k)/\delta}\notag\\
&\approx \frac{(1/\delta)^k}{k!} (\lambda\delta)^k e^{-\lambda}\notag\\
&= e^{-\lambda}\frac{\lambda^k}{k!}\label{Poisson density}
\end{align}
The probability distribution~(\ref{Poisson density}) is known as the
\emph{Poisson distribution}.  When talking as we are now about arrivals in
a system, we refer to the arrival behavior as a \emph{Poisson process}.

As a sanity check our distribution, the probability values over all $k$
had better sum to 1.  Using the Taylor expansion for $e^{\lambda}$, we
can verify that they do:
\[
\sum_{k \in \naturals} \pr{X=k} = \sum e^{-\lambda}\frac{\lambda^k}{k!}
= e^{-\lambda} \sum \frac{\lambda^k}{k!}
= e^{-\lambda}e^{\lambda} = 1.
\]

A further sanity check is that the expected number of arrivals in a second
is indeed $\lambda$, namely,
\begin{equation}\label{Elam}
\expect{X}= \lambda.
\end{equation}

Similarly, since the binomial distribution $f_{n,p}$ has variance
$np(1-p)$, we can expect that the Poisson distribution, as the limit as
$\delta$ vanishes of $f_{1/\delta,\lambda\delta}$, ought to have variance
\[
(1/\delta)(\lambda\delta)(1- \lambda\delta) = \lambda(1 - \lambda\delta)
\approx \lambda.
\]
The final approximation holds since $1 - \lambda\delta \approx 1$ for
vanishing $\delta$.  In other words,
\begin{equation}\label{Vlam}
\variance{X}= \lambda.
\end{equation}

Also, suppose we have two independent Poisson processes $X_1, X_2$
contributing arrival events at the respective rates $\lambda_1,\lambda_2$.
Intuitively, this ought to be the same as having a single process
producing independent arrivals at the rate $\lambda_1 + \lambda_2$.  This
explains another useful property of the Poisson distribution:
\begin{lemma}\label{lamsum}
If $X_1$ are $X_2$ are Poisson processes, then so is $X_1+X_2$.
\end{lemma}

Both equations~(\ref{Elam}) and~(\ref{Vlam}), and Lemma~\ref{lamsum}, are
easy to verify formally from the definitions of the Poisson distribution
and the Taylor series for $e$.

Finally, we can develop a Chernoff style bound for the probability that a
Poisson process deviates from its mean.  As in the proof of the Chernoff
bound, we have for \emph{any} random variable, $R \geq 0$, and constants
$c,t \geq 0$, that
\[
R \geq c\text{  iff  } e^{tR} \geq e^{tc}.
\]
So by Markov's inequality
\begin{equation}\label{moment Chernoff}
\pr{R \geq c} \leq \frac{\expect{e^{tR}}}{e^{tc}}
\end{equation}

For a Poisson process, $X$, we have
\begin{align}
\expect{e^{tX}} & =  \sum_{k \in \naturals} \frac{e^{tk}e^{-\lambda}\lambda^k}{k!}\notag\\
  &=  e^{-\lambda} \sum\frac{(\lambda e^t)^k}{k!}\notag\\
  & =  e^{-\lambda} e^{\lambda e^t}\notag\\
  & =  e^{\lambda (e^t -1)}. \label{Poisson moment}
\end{align}
So if $X$ is a Poisson process,
\begin{equation}\label{Xgc}
\pr{X \geq c} \leq e^{\lambda (e^t -1)}e^{-tc} = e^{\lambda (e^t -1) - tc}.
\end{equation}
To minimize the exponent, we choose $t = \ln (c/\lambda)$, which will be
positive as long as $c > \lambda$.  Substituting this value for $t$
into~(\ref{Xgc}), we conclude
\begin{equation}\label{Poisson deviation}
\pr{X \geq c} \leq e^{c\ln (\lambda/c) + c - \lambda}.
\end{equation}

Now letting, $c= c'\lambda$ in~(\ref{Poisson deviation}) and
using~(\ref{Elam}) yields
\begin{align*}
\pr{X \geq c'\expect{X}} & \leq e^{c'\lambda\ln (1/c') + c'\lambda - \lambda}\\
   & = e^{-c'\lambda\ln c' + c'\lambda - \lambda}\\
   & = e^{-(c'\ln c' - c' + 1)\lambda}\\
   & = e^{-(c'\ln c' - c' + 1)\expect{X}}.
\end{align*}
Notice that this is exactly the same as the Chernoff
bound~(\ref{Chbndeq}).  So we have another case where a Poisson process
behaves like a sum of independent indicator variables.

\iffalse
Exercise: Show that $\variance{X} = \lambda$.  \textbf{Is there intuition for this?}
\fi

\iffalse Noteworthy is the probability that $X=0$, that is, that no
arrivals occur in time $t$.  Plugging in $k=0$, we find that this is
$e^{-\lambda t}$.  This is consistent with our previous derivation of the
exponential distribution.  \fi

\section{Review of Markov, Chebyshev, Chernoff and Binomial bounds}

Let us review the methods we have for bounding deviation from the
mean via the following example.
Assume that \IQ is made up of thinkatons; each thinkaton fires
independently with a $10\%$ chance. We have 1000 thinkatons in all,
and \IQ is the number of thinkatons that fire. 
What is the probability of having Marilyn's IQ of 228?

So the \IQ is a Binomial distribution with $n=1000, p= 0.1$.  Hence
$\expect{\text{I.Q.}} = 100, \sigma_{\text{I.Q.}} =\sqrt{0.09 \times 1000}
= 9.48$.

An \IQ of 228 is $128/9.48 > 13.5$ standard deviations away.

Let us compare the methods we have for bounding the probability of this \IQ.

\begin{enumerate}
\item Markov: 
\[
\pr{\text{I.Q.} \geq 228} \leq \frac{100}{228} < 0.44
\]

\item Chebyshev:
\[
\pr{\text{I.Q. } - 100 \geq 128 } \leq \frac{1}{13.5^2+1} < \frac{1}{183}
\]

\item Chernoff: 
\[
\pr{\text{I.Q. } \geq 2.28 \times 100} \leq e^{-(2.28\ln 2.28 - 2.28 +1)100} \leq e^{-59.9}
\]

\item Binomial tails:
\[
\pr{\text{I.Q. } \geq 228} = \pr{1000-\text{I.Q. } \leq 772} =
F_{0.9,1000}(772) \leq e^{-72.5}
\]
Here we used the formula for the binomial tail from
\href{http://theory.lcs.mit.edu/classes/6.042/fall01/lectures/l12.pdf}{Notes
12} with $p = 0.9, n = 1000, \alpha = 0.772$.

\end{enumerate}

Note that the more we know about the distribution the better are the 
bounds we can obtain on the probability.


\section{The Central Limit Theorem}

\iffalse
We described the \emph{Weak} Law of Large Numbers in previous notes,
begging the question of what \emph{strong} law of large numbers we might
prove.  Roughly speaking, the strong law says that with probability 1, the
bound of the weak law will hold for all but a finite number of the $S_n$
\emph{simultaneously}---there will only be finitely many exceptions to it.
\fi

We close with a description of a fundamental result of probability theory
known as the \emph{Central Limit Theorem}.  This theorem substantially
refines the Weak Law of Large Numbers.

In the Weak Law we had $S_n \eqdef \sum_{i=1}^n G_i$ where $G_1, \dots,
G_i, \dots$ were mutually independent variables with same mean, $\mu$, and
deviation $\sigma$.  The Weak Law said that the probability that $S_n/n$
was outside an interval of fixed size $\epsilon >0$ around $\mu$ approached
0 as $n$ approached infinity.

The Central Limit Theorem describes not just the limiting behavior of
deviation from the mean of $S_n/n$, but actually describes a limiting
shape of the entire distribution for $S_n/n$.

\begin{definition}
For any random variable $R$ with finite mean, $\mu_R$, and
deviation, $\sigma_R$, let $R^*$ be the random variable
\[
R^* \eqdef \frac{R-\mu_R}{\sigma_R}.
\]
$R^*$ is called the ``normalized'' version of $R$.
\end{definition}
Note that $R^*$ has mean 0 and deviation 1.  In other words, $R^*$ is just
$R$ shifted and scaled so that its mean is 0 and its deviation and
variance are 1.

The Central Limit Theorem says that \emph{regardless} of the underlying
distribution of the variables $G_i$, so long as they are independent, the
distribution of $S^*_n$ converges to the same, \emph{normal},
distribution.  It is not surprising that this normal distribution---also
known as a \emph{Gaussian} distribution---plays a fundamental role in the
study of probability and statistics: as long as you are summing enough
random variables, you can pretend that the result is Gaussian.

\begin{definition}
The \emph{normal density function} is the function 
\[
n(x) = \frac{1}{\sqrt{2\pi}}e^{-x^2/2},
\]
and the \emph{normal distribution function} is its integral
\[
N(y) = \int_{-\infty}^y n(x)dx = \frac{1}{\sqrt{2\pi}}\int_{-\infty}^y
e^{-x^2/2}dx.
\]
\end{definition}

The function $n(x)$ defines the standard \emph{Bell curve}, centered about
the origin with height $1/\sqrt{2\pi}$ and about two-thirds of its area
within unit distance of the origin.  The normal distribution function
$N(y)$ approaches 0 as $y \rightarrow -\infty$.  As $y$ approaches zero
from below, $N(y)$ grows rapidly towards $1/2$.  Then as $y$ continues to
increase beyond zero, $N(y)$ rapidly approaches 1.

\begin{theorem}[Central Limit Theorem]
Let $S_n = \sum_{i=1}^n G_i$ where $G_1, \dots, G_i, \dots$ are
mutually independent variables with the same mean, $\mu$, and deviation,
$\sigma$, and let $S^*_n$ be the normalized version of $S_n$.  Then
\begin{equation}\label{normal}
\lim_{n\rightarrow\infty} \pr{S^*_n \leq \beta}= N(\beta)
\end{equation}
for any real number $\beta$.
\end{theorem}

\iffalse
It is clear that $N(x)$ is an increasing function of $x$, and that
$N(-\infty)=0$.  It can also be shown that $N(\infty)=1$.  Thus $N(x)$ can
be interpreted as the probability that a certain \emph{normally
distributed} random variable is less than $x$.  But this requires a study
of continuous distributions (with an uncountable number of sample points,
namely the real numbers).  We haven't developed the formal machinery for
that, so we will just think of $N(x)$ as a function.
\fi

To understand the Central Limit Theorem, it helps to see how it implies
the Weak Law of Large Numbers.  Note first that $\variance{S_n} =
n\sigma^2$ so $\sigma_{S_n} = \sigma\sqrt{n}$.  So,
\begin{eqnarray*}
\frac{S_n}{n} - \mu > \epsilon & \text{ iff } &
      S_n - n\mu > n\epsilon\\
      & \text{ iff }  & \frac{S_n - n\mu}{\sigma_{S_n}} > \frac{n\epsilon}{\sigma_{S_n}}\\
      &  \text{ iff } & S^*_n > \dfrac{\sqrt{n}\epsilon}{\sigma}.
\end{eqnarray*}
Now for any $\beta \in \reals$, we will have
\[
\frac{\sqrt{n}\epsilon}{\sigma} > \beta
\]
for all large $n$.  Hence, for any $\beta \in \reals$ and all large $n$,
\begin{equation} \label{Sne}
\pr{\frac{S_n}{n} - \mu > \epsilon} = \pr{S^*_n > \frac{\sqrt{n}\epsilon}{\sigma}}
    \leq \pr{S^*_n > \beta}.
\end{equation}
So by~(\ref{normal}),
\begin{equation}\label{limSne}
\lim_{n\rightarrow\infty} \pr{\frac{S_n}{n} - \mu > \epsilon}
\leq \lim_{n\rightarrow\infty} \pr{S^*_n > \beta} = 1 - N(\beta),
\end{equation}
for all real numbers $\beta$.  By choosing $\beta$ large enough, we can to
ensure that $N(\beta)$ is arbitrarily close to 1, so~(\ref{limSne}) implies
\[
\lim_{n\rightarrow\infty} \pr{\frac{S_n}{n} - \mu > \epsilon} = 0,
\]
which is the Weak Law of Large Numbers.

We will not prove the Central Limit Theorem, but will only note that a
standard proof rests on extending ideas we have already used in deriving
Chernoff bounds, in particular properties of $\expect{e^{tX}}$.  Regarded
as a function of $t$, $\expect{e^{tX}}$ is called the \emph{moment
generating function} of the random variable, $X$.  The Central Limit
Theorem can be proved using a more complete development of the properties
of moment generating functions, more than we have time for in 6.042.

Like the Weak Law of Large Numbers, the Central Limit Theorem as stated
cannot be applied to actual problems because the necessary information
about the rate of convergence is missing, that is, we need to know the
accuracy with which the limit $N(\beta)$ approximates the probability that
$S^*_n < \beta$.  For variables $G_1, G_2, \dots$ whose absolute value is
bounded by about 5, or are themselves are normal, a rule of thumb is
that~(\ref{normal}) holds to two or three decimal places when $\abs{\beta}
< 3$ and $n>30$.  But in situations such as those we have seen for
designing overload tolerance into systems, and also for ensuring the
quality of the solution to an optimization problem by a probabilistic
algorithm, we are typically more concerned with events that differ from
the mean by many standard deviations.  For estimating probabilities at
such distribution tails, Chernoff bounds are more accurate than those
based on normal distributions.  For this reason, Chernoff bounds play a
more prominent role in Computer Science than the Central Limit Theorem.

\end{document}


\iffalse
Notice that the random variables $S_n/n$
and $S_n$ have the same normalized density function:
\begin{eqnarray*}
S^*_n  & \eqdef & \frac{S_n - \mu_{S_n}}{\sigma_{S_n}}\\
      & = & \frac{S_n - n\mu}{\sigma\sqrt{n}}\\
      & = & \frac{S_n/n - \mu}{\sigma/\sqrt{n}}\\
      & = & \frac{S_n/n - \mu_{S_n/n}}{\sigma_{S_n/n}}\\
      & = & (S_n/n)^*.
\end{eqnarray*}
So

\begin{eqnarray*}
\pr{\frac{S_n}{n} - \mu < \epsilon} & = &
      \pr{\frac{S_n/n - \mu}{\sigma_{S_n/n}} < \frac{\epsilon}{\sigma_{S_n/n}}\\
      & = & \pr{(S_n/n)^* < \frac{\epsilon}{\sigma/\sqrt{n}}}\\
      & = & \pr{(S_n/n)^* < \frac{\epsilon\sqrt{n}}{\sigma}}\\
      & = & \pr{(S_n)^* < \frac{\epsilon\sqrt{n}}{\sigma}}\\
\frac{\sigma}{\sqrt{n}}}\\

 \pr{(S_n)^* < \epsilon}\\
         & = & \pr{(S_n/n)^* < \epsilon}\\
         & = & \pr{\frac{S_n/n - \mu}{\sigma/\sqrt{n}}< \epsilon}\\

\end{eqnarray*}
\fi
