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

\onlystudents

\begin{document}

\lecture{tail bounds}{Variance and Bounds on Tails of
Distributions}{10 May 2001}

\forlecture{
\noindent
Topics for today:
\begin{itemize}
\item
Variance
\item
Markov's Theorem
\item
Chebyshev's Theorem
\item
Chernoff Bounds
\end{itemize}

\reading{Rosen Section 4.4, 4.5; \\
Ross, ``A First Course in Probability'', Prentice-Hall, Sections 4.6,
8.2, 8.5}
}


\section{Overview}

So far, our work on random variables has focused on the \emph{mean},
or \emph{expectation}.  But the mean isn't the only interesting
statistic.  We might like to know the probability that the value of
the random variable is within a certain bound $b$ of the mean, or more
than $b$ away from the mean.

For instance, suppose that the 6 million voters in Florida perform a
random experiment to determine whether they vote for Bush or for Gore.
E.g., each voter may toss a coin independently;
or they may form groups and toss one coin for each group; 
or half may decided ahead of time, with an even split, and the other
half may toss independent coins;
or maybe the Florida Supreme Court tosses one coin for the whole
state.
There are many possibilities.
Anyway, we might want to know the likelihood that the number of 
Floridians who voted for Bush is within 300 of the mean.

The first result is Markov's Theorem, which gives a simple but coarse
upper bound on the probability that the value of the random variable
is more than a certain multiple of the mean.
Then we move to Chebyshev's Theorem, which gives a more refined result
that takes into account the variance of the distribution as well as
the mean. 
Finally, we give ``Chernoff Bounds'', which give still more
refined results, taking into account still more information. 
These deal with the situation where the distribution is of a particular
form---resulting from a series of independent experiments (e.g.,
voters all tossing independent coins).



\section{Markov's Theorem}

We want to consider the problem of bounding the probability that the
value of a random variable is far away from the mean. Our first
theorem, Markov's theorem, gives a very rough estimate, based only on
the value of the mean. Note that very different distributions can
still have the same mean.
\begin{example}
  Suppose that we roll a fair die.  This gives a random variable
  uniformly distributed on $1, 2, \ldots 6$.  The mean, or expected
  value, is 3.5.  Of course, this random variable never takes on
  exactly the expected value; in fact, the outcome deviates from the
  mean by at least 0.5 with probability 1.  Furthermore, there is a
  $\frac{2}{3}$ probability that the outcome deviates from the mean by
  at least 1.5 (roll 1, 2, 5, or 6), a $\frac{1}{3}$ probability that
  the outcome deviates by at least 2.5 (roll 1 or 6), and zero
  probability that the outcome deviates by more than 2.5.
\end{example}
\begin{example}
  A random variable with the binomial distribution is much less likely
  to deviate far from the mean.  For example, suppose we flip 100
  fair, mutually independent coins and count the number of heads.  The
  expected number of heads is 50.  There is an 8\% chance that the
  outcome is exactly the mean, and the probability of flipping more
  than 75 heads or fewer than 25 is less than 1 in a billion.
\end{example}
The probability distribution functions for the two preceding examples
are graphed in Figure~\ref{fig:uniform} and Figure~\ref{fig:binom2}.
There is a big difference!  For the uniform distribution, the graph is
flat; that is, outcomes far from the mean are as likely as outcomes
close to the mean.  However, the binomial distribution has a peak
centered on the expected value and the tails fall off rapidly.  This
shape implies that outcomes close to the expected value are vastly
more likely than outcomes far from the expected value.  In other
words, a random variable with the binomial distribution rarely
deviates far from the mean.
\begin{figure}
  \centerline{\includegraphics[height=2in]{figures/uniform}}
  \caption{This is a graph of the uniform distribution arising from
    rolling a fair die.  Outcomes within the range of the distribution
    are equally likely, regardless of distance from the mean.}
  \label{fig:uniform}
\end{figure}
\begin{figure}
  \centerline{\includegraphics[height=2in]{figures/binom2}}
  \caption{This is a rough graph of the binomial distribution given by
    the number of heads that come up when we flip 100 fair, mutually
    independent coins.  Outcomes close to the mean are much more
    likely than outcomes far from the mean.}
  \label{fig:binom2}
\end{figure}

On the other hand, we can define a random variable that always
deviates substantially from its expected value.  Suppose that we glue
100 coins together, so that with probability 1/2 all are heads and
with probability 1/2 all are tails.  The graph of the probability
distribution function for the number of heads is shown in
Figure~\ref{fig:nasty}.  While the expected value of this random
variable is 50, the actual value is always 0 or~100.
\begin{figure}
  \centerline{\includegraphics[height=2in]{figures/nasty}}
  \caption{This is the nasty distribution corresponding to the number
    of heads that come up when we flip 100 coins that are all glued
    together. The outcome always differs from the mean by at
    least~50.}
  \label{fig:nasty}
\end{figure}

Even in this last example, however, the random variable is twice the
mean with probability only $1/2$.  In fact, we will see that this is a
worst-case distribution with respect to deviation from the mean.



\subsection{Theorem Statement and Some Applications}

Markov's Theorem says that a non-negative random variable cannot
greatly exceed its mean.
\begin{theorem}[Markov's Theorem]
  If R is a non-negative random variable, then for all $x > 0$
  \begin{displaymath}
    \Pr(R \geq x) \leq \frac{\Ex(R)}{x}\,.
  \end{displaymath}
\end{theorem}
Markov's Theorem is often in expressed in an alternative form, stated
below as a corollary.
\begin{corollary}
  If R is a non-negative random variable, then for all $c > 0$
  \begin{eqnarray*}
    \Pr(R \geq c \cdot \Ex(R)) & \leq & \frac{1}{c}
  \end{eqnarray*}
\end{corollary}
\begin{proof}
  In Markov's Theorem, set $x = c \cdot \Ex(R)$.  This gives:
  \[
  Pr(R \geq c \cdot Ex(R)) \leq \frac{Ex(R)}{c \cdot \Ex(R)} = \frac{1}{c}
  \]
\end{proof}
Before we prove Markov's Theorem, let's apply it to the three examples
in the preceding subsection.  First, let the random variable~$R$ be
the number that comes up when we roll a fair die.  By Markov's
Theorem, the probability of rolling a 6 is at most:
\[
\Pr(R \geq 6) \leq \frac{\Ex(R)}{6} = \frac{3.5}{6} = 0.583\ldots
\]
This conclusion is true, but weak.  The actual probability of rolling
a 6 is $\frac{1}{6} = 0.166\ldots$.

This is typical of Markov's Theorem.  The theorem is easy to apply
because it requires so little information about a random variable,
only the expected value and non-negativity.  But as a consequence,
Markov's Theorem often leads to weak conclusions like the one above.

Suppose that we flip 100 mutually independent, fair coins.  Markov's
Theorem says that the probability of throwing 75 or more heads is at
most:
\[
\Pr(\text{heads} \geq 75) \leq \frac{\Ex(\text{heads})}{75} =
\frac{50}{75} = \frac{2}{3}
\]
Markov's Theorem says that the probability of 75 or more heads is at
most $\frac{2}{3}$, but the actual probability is less than 1 in a
billion!

These two examples show that Markov's Theorem gives weak results for
well-behaved random variables; however, the theorem is actually tight
for some nasty examples.  Suppose we flip 100 fair coins and use
Markov's Theorem to compute the probability of getting all heads:
\[
\Pr(\text{heads} \geq 100) \leq \frac{\Ex(\text{heads})}{100} =
\frac{50}{100} = \frac{1}{2}
\]
If the coins in are mutually independent, then the actual probability
of getting all heads is a miniscule 1 in $2^{100}$.  In this case,
Markov's Theorem looks very weak.  However, in applying Markov's
Theorem, we made no independence assumptions.  In fact, if all the
coins are glued together, then probability of throwing all heads is
exactly $\frac{1}{2}$.  In this nasty case, Markov's Theorem is
actually tight!



\subsection{Proof of Markov's Theorem}

Let $R$ be the weight of a person selected randomly and uniformly.
Suppose that an average person weighs 100 pounds; that is, $\Ex(R) =
100$.  What is the probability that a random person weighs at least
200 pounds?

There is insufficient information for an exact answer.  However, we
can safely say that the probability that $R \geq 200$ is most
$\frac{1}{2}$.  If more than half of the people weigh 200 pounds or
more, then the average weight would exceed 100 pounds, even if
everyone else weighed zero!  Markov's Theorem gives the same result:
\begin{displaymath}
  \Pr(R \geq 200) \leq \frac{\Ex(R)}{200} = \frac{100}{200} = \frac{1}{2}
\end{displaymath}
Reasoning similar to that above underlies the proof of Markov's
Theorem. Since expectation is a weighted average of all the outcomes
of the random variable, \ie\ a sum over all the variables the random
variable can assume, we can give a lower bound on the expectation by
removing some of the terms from the sum defining the expectation; this
new sum can then be modified into an expression involving the
probability of an event in the tail $\{R \geq x\}$.
\begin{proof}[Proof of Markov's Theorem]
  We must prove that if R is a non-negative random variable, then for
  all $x > 0$,
  \begin{displaymath}
    \Pr(R \geq x) \leq \frac{\Ex(R)}{x}\,.
  \end{displaymath}
  We will show that $\Ex(R) \geq x \cdot \Pr(R \geq x)$.  Dividing
  both sides by $x$ gives the desired result. We do this by studying
  the random variable $x I_{\{R \geq x\}}$. Clearly, $R \geq x I_{\{R
    \geq x\}}$; if $R(w) \geq x$ then $x I_{\{R \geq x\}}(w) = x$, and
  if $R(w) < x$ then $x I_{\{R \geq x\}}(w) = 0$. Therefore,
  \begin{displaymath}
    \Ex(R) \geq \Ex(x I_{\{R \geq x\}})
    = x \Ex(I_{\{R \geq x\}}) = x \Pr(R \geq x).
  \end{displaymath}
  The inequality follows since $R \geq x I_{\{R \geq x\}}$. Then we
  pull~$x$ out of the expectation, and finally we use the fact that
  the expectation of an indicator variable for some event is equal to
  the probability of that event.
\end{proof}



\section{More Examples of Markov's Theorem}

Suppose that $N$ men go to a dinner party and check their hats.  At
the end of the night, each man is given his own hat back with
probability $\frac{1}{N}$.  What is the probability that $x$ or more
men get the right hat?

We can compute an upper bound with Markov's Theorem.  Let the random
variable $R$ be the number of men that get the right hat.  In a
previous lecture, we used linearity of expectation to show that
$\Ex(R) = 1$.  By Markov's Theorem, the probability that $x$ or more
men get the right hat is:
\[
\Pr(R \geq x) \leq \frac{\Ex(R)}{x} = \frac{1}{x}
\]
For example, there is no better than a 20\% chance that 5 men get the
right hat, regardless of the number of people at the dinner party.

The Chinese Appetizer problem is very similar.  In this case, $N$
people are eating Chinese appetizers arranged on a circular, rotating
tray.  Someone then spins the tray so that each person receives a
random appetizer.  What is the probability that everyone gets the same
appetizer as before?

There are $N$ equally likely orientations for the tray after it stops
spinning.  Everyone gets the right appetizer in just one of these $N$
orientations.  Therefore, the correct answer is $\frac{1}{N}$.

But what probability do we get from Markov's Theorem?  Let the random
variable $R$ be the number of people that get the right appetizer.  We
showed in a previous lecture that $\Ex(R) = 1$.  Applying Markov's
Theorem, we find:
\begin{displaymath}
  \Pr(R \geq N) \leq \frac{\Ex(R)}{N} = \frac{1}{N}\,.
\end{displaymath}
In this case, Markov's Theorem is tight!

On the other hand, Markov's Theorem gives the same $1/N$ bound for the
probability everyone gets their hat in the hat check problem.  But in
reality, the probability of this event is $1/N!$.  So Markov's Theorem
is \emph{incredibly} loose.



\subsection{Why $R$ Must be Non-Negative}

The proof of Markov's Theorem requires that the random variable $R$ be
non-negative.  The following example shows that the theorem is false
if this restriction is removed.  Let $R$ be -10 with probability
$\frac{1}{2}$ and 10 with probability $\frac{1}{2}$.  Then we have:
\[
\Ex(R) = -10 \cdot \frac{1}{2} + 10 \cdot \frac{1}{2} = 0
\]
Suppose that we now tried to compute $\Pr(R \geq 5)$ using Markov's
Theorem:
\begin{displaymath}
  \Pr(R \geq 5) \leq \frac{\Ex(R)}{5} = \frac{0}{5} = 0.
\end{displaymath}
This is the wrong answer!  Obviously, $R$ is at least 5 with
probability $\frac{1}{2}$.  Remember that Markov's Theorem applies
only to non-negative random variables!



\subsection{Deviation Below the Mean}

Markov's Theorem says that a random variable is unlikely to greatly
exceed the mean.  There a similar theorem that says a random variable
is unlikely to be very small.
\begin{theorem}
  \label{th:below}
  Let $L$ be a real number and let $R$ be a random variable such that $R
  \leq L$.  For all $x < L$, we have:
  \[
  \Pr(R \leq x) \leq \frac{L - \Ex(R)}{L - x}
  \]
\end{theorem}
\begin{proof}
  The event that $R \leq x$ is the same as the event that $L - R \geq L
  - x$.  Therefore:
  \begin{displaymath}
    \Pr(R \leq x) = \Pr(L - R \geq L - x) \leq \frac{\Ex(L - R)}{L - x}\,.
  \end{displaymath}
  In the second step, we applied Markov's Theorem.  This is
  permissible since $L - R$ is a non-negative random variable and $L -
  x > 0$.
\end{proof}
For example, suppose that the class average on the 6.042 midterm was
75\%.  What fraction of the class scored below 50\%?

There is not enough information here to answer the question exactly,
but Theorem~\ref{th:below} gives an upper bound.  Let $R$ be the score
of a random student.  Since 100\% is the highest possible score, we
can set $L = 100$ to meet the condition in the theorem that $R \leq
L$.  Applying Theorem~\ref{th:below}, we find:
\begin{displaymath}
  \Pr(R \leq 50) \leq \frac{100 - 75}{100 - 50} = \frac{1}{2}\,.
\end{displaymath}
That is, at most half of the class scored 50\% or worse.  This makes
sense; if more than half of the class scored 50\% or worse, then the
class average could not be 75\%, even if everyone else scored 100\%.
As with Markov's Theorem, Theorem~\ref{th:below} often gives weak
results.  In fact, based on the data given, the entire class could
have scored above 50\%.



\subsection{Using Markov To Analyze Non-Random Events}

In the previous examples, we used a theorem about a random variable to
conclude facts about non-random data.  For example, we concluded that
if the average score on a test is 75\%, then at most $\frac{1}{2}$ the
class scored 50\% or worse.  There is no randomness in this problem,
so how can we apply Theorem~\ref{th:below} to reach this conclusion?

The explanation is not difficult.  For any set of scores $S = \{ s_1,
s_2, \ldots, s_n \}$, we introduce a random variable $R$ such that
\[
\Pr(R = s_i) = \frac{\text{(\# of students with score $s_i$)}}{n}
\]
We then use Theorem~\ref{th:below} to conclude that $\Pr(R \leq 50\%)
\leq \frac{1}{2}$.  To see why this means (with certainty) that at most
$\frac{1}{2}$ of the students scored 50\% or less, we observe that
\begin{eqnarray*}
  \Pr(R \leq 50\%)
  & = & \sum_{s_i \leq 50\%} \Pr(R = s_i) \\
  & = & \sum_{s_i \leq 50\%} \frac{\text{(\# of students with score $s_i$)}}{n} \\
  & = & \frac{1}{n} \text{(\# of students with score 50\% or less)} \\
\end{eqnarray*}
Therefore $\Pr(R \leq 50\%) \leq \frac{1}{2}$ implies that the number of
students with score 50\% or less is at most $\frac{n}{2}$.



\subsection{The probability of at least one event}
\label{sc: one}

Let $A_1, A_2, \ldots, 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?
We can obtain a weak upper bound on this probability using 
Markov's Theorem:
\begin{displaymath}
  \Pr(T \geq 1)  \leq \frac{\Ex(T)}{1}
\end{displaymath}
Markov's Theorem applies because the random variable $T$ is non-negative.
All that remains is to compute $\Ex(T)$, the expected number of events
that occur.  We do this by introducing an indicator variable $T_i$
for each event $A_i$; that is, $T_i = 1$ if event $A_i$ occurs, and
$T_i = 0$ if event $A_i$ does not occur.  Then $T$, the total number
of events that occur, is the sum of these indicator variables:
\begin{displaymath}
  T = T_1 + T_2 + \ldots + T_N
\end{displaymath}
We compute the expected value of $T$ as follows:
\begin{eqnarray*}
\Ex(T)  & = & \Ex(T_1 + T_2 + \ldots + T_N) \\
        & = & \Ex(T_1) + \Ex(T_2) + \ldots + \Ex(T_N) \\
        & = & \Pr(A_1) + \Pr(A_2) + \ldots \Pr(A_N)
\end{eqnarray*}
In the first step, we take the expected value of both sides of the
preceding equation.  The second step uses linearity of expectation.
In the last step, we use the fact that the expected value of an
indicator variable is the probability that the indicator is 1.

Substituting the expression for $\Ex(T)$ into the inequality from
Markov's Theorem gives the following bound on the probability that some
event occurs:
\begin{fact}
  \label{fact:union}
  Let $A_1, A_2, \ldots, A_N$ be events over the same sample space, and
  let the random variable $T$ be the number of these events that occur.
  Then
  \begin{eqnarray*}
    \Pr(T \geq 1) & \leq & \sum_{i=1}^n \Pr(A_i).
  \end{eqnarray*}
\end{fact}
This is a formula well worth remembering.  In words, the probability
that at least one of the events occurs is at most the sum of the event
probabilities.

This result 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
$\frac{1}{2} + \frac{1}{2} + \frac{1}{2} = \frac{3}{2}$, which is not
front-page news.

Nevertheless, Fact~\ref{fact:union} is useful if the events $A_i$ all
have relatively low probability.  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 plant on Albany Street.  First, we enumerate
all events $A_i$ that could lead to a meltdown, e.g. operator error,
earthquake, terrorist attack, meteor strike, etc.  Next, we somehow
determine the probability of each type of catastrophe.  Then
Fact~\ref{fact:union} says that the probability of a meltdown is at
most the sum of these event probabilities.  Thankfully, we can totally
ignore tricky independence issues such as, what if the terrorist team
is wiped out by a meteor strike?

The previous method gives an upper bound on $\Pr(T \geq 1)$.  We can
get a lower bound by computing the maximum of $\Pr(A_i)$ over all $i$.

\begin{fact}
  Let $A_1, A_2, \ldots, 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{fact}
The left side is $\Pr(A_1 \cup A_2 \cup \ldots \cup A_n)$.  Since
every event $A_i$ is a subset of the union $A_1 \cup A_2 \cup
\ldots \cup A_n$, we have $\Pr(A_1 \cup A_2 \cup \ldots \cup A_n) \geq
\Pr(A_i)$ for all $i$.  In particular, this holds for the $i$ that
maximizes $\Pr(A_i)$.

We will be able to get a better lower bound in the case where the
events are independent.  We will come back to this in tutorial.



\section{Variance}

It is a bit messy to use Markov's inequality directly to bound the
probabilty that $|R - E(R)| \geq x$, since we then would have to
compute $\Ex(|R - E(R)|)$. Note, however, that Markov's inequality
also applies to the event $\{|R|^k \geq x^k\}$---since $|R|$ is a
non-negative variable, this event is equivalent to the event $\{|R|
\geq x\}$.
\begin{corollary}
  \label{cor:Markov2}
  For any random variable~$R$, any positive integer~$k$ and any $x >
  0$,
  \begin{displaymath}
    \Pr(|R| \geq x) \leq \frac{\Ex(|R|^k)}{x^k}\,.
  \end{displaymath}
\end{corollary}
This corollary has an interesting consequence. Let us apply it to the
case $k = 2$:
\begin{displaymath}
  \Pr\bigl(|R - \Ex(R)| \geq x\bigr)
  = \Pr\bigl((R - \Ex(R))^2 \geq x^2\bigr)
  \leq \frac{\Ex\bigl((R - \Ex(R))^2\bigr)}{x^2}\,,
\end{displaymath}
where the inequality follows from Corollary~\ref{cor:Markov2} applied
to the random variable $|R - \Ex(R)|$ and $k = 2$. Apparently, we can
bound the probability that the random variable~$R$ deviates from its
mean by more than~$x$ by an expression decreasing as $1 / x^2$
multiplied by the constant $\Ex((R - \Ex(R))^2)$. This constant is
called the \emph{variance of~$R$}.
\begin{defin*}
  The variance of a random variable $R$ is denoted $\Var(R)$ and is
  defined as follows:
  \[
  \Var(R) = \Ex((R - \Ex(R))^2)
  \]
\end{defin*}
The expression $\Ex((R - \Ex(R))^2)$ is a bit cryptic; the best
approach is to work through it from the inside out.  The innermost
expression, $R - \Ex(R)$, is precisely the deviation of $R$ from the
mean.  Squaring this, we obtain, $(R - \Ex(R))^2$.  This is a random
variable that is near 0 when $R$ is close to the mean and is a large
positive number when $R$ deviates far above or below the mean.  The
variance is just the average of this random variable, $\Ex((R -
\Ex(R))^2)$.  Therefore, intuitively, if $R$ is always close to the mean,
then the variance will be small.  If $R$ is often far from the mean,
then the variance will be large.  For this reason, variance is useful
in studying the probability that a random variable deviates far from
the mean.

\subsection{Example: Gambling Games}

The relevance of variance is apparent when we compare the following
two gambling games.

\begin{description}
\item{Game A:} We win \$2 with probability $\frac{2}{3}$ and lose \$1
with probability $\frac{1}{3}$.
\item{Game B:} We win \$1002 with probability $\frac{2}{3}$ and lose
\$2001 with probability $\frac{1}{3}$.
\end{description}

Which game is more better financially?  We have the same probability
($\frac{2}{3}$) of winning each game, but that does not tell the whole
story.  What about the expected return for each game?  Let random
variables $A$ and $B$ be the payoffs for the two games.  For example,
$A$ is 2 with probability $\frac{2}{3}$ and -1 with probability
$\frac{1}{3}$.  We can compute the expected payoff for each game as
follows:

\begin{eqnarray*}
\Ex(A) = 2 \cdot \frac{2}{3} + (-1) \cdot \frac{1}{3} = 1 \\
\Ex(B) = 1002 \cdot \frac{2}{3} + (-2001) \cdot \frac{1}{3} = 1
\end{eqnarray*}

The expected payoff is the same for both games, but they are obviously
very different!  This difference is hidden by expected value, but
captured by variance.  We can compute the $\Var(A)$ and $\Var(B)$ by
working ``from the inside out'' as follows:

\begin{eqnarray*}
A - \Ex(A)
        & = &   \left\{
                \begin{array}{cl}
                        1 & \text{ with probability } \frac{2}{3} \\
                        -2 & \text{ with probability } \frac{1}{3}
                \end{array}
                \right. \\
(A - \Ex(A))^2
        & = &   \left\{
                \begin{array}{cl}
                        1 & \text{ with probability } \frac{2}{3} \\
                        4 & \text{ with probability } \frac{1}{3}
                \end{array}
                \right. \\
\Ex(A - \Ex(A))^2
        & = &   1 \cdot \frac{2}{3} + 4 \cdot \frac{1}{3} \\
\Var(A) & = & 2
\end{eqnarray*}

\begin{eqnarray*}
B - \Ex(B)
        & = &   \left\{
                \begin{array}{cl}
                        1001 & \text{ with probability } \frac{2}{3} \\
                        -2002 & \text{ with probability } \frac{1}{3}
                \end{array}
                \right. \\
(B - \Ex(B))^2
        & = &   \left\{
                \begin{array}{cl}
                        1,002,001 & \text{ with probability } \frac{2}{3} \\
                        4,008,004 & \text{ with probability } \frac{1}{3}
                \end{array}
                \right. \\
\Ex(B - \Ex(B))^2
        & = &   1,002,001 \cdot \frac{2}{3} + 4,008,004 \cdot \frac{1}{3} \\
\Var(A) & = & 2,004,002
\end{eqnarray*}

The variance of Game A is 2 and the variance of Game B is more than
two million!  Intuitively, this means that the payoff in Game A is
usually close to the expected value of \$1, but the payoff in Game B
can deviate very far from this expected value.

High variance is often associated with high risk.  For example, in ten
rounds of Game A, we expect to make \$10, but could conceivably lose
\$20 instead.  On the other hand, in ten rounds of game B, we also
expect to make \$10, but could actually lose more than \$20,000!

\subsection{Why Variance?}

The definition of variance looks rather arbitrary:
\[
\Var(R) = \Ex((R - \Ex(R))^2)
\]
This says that variance is the average \emph{of the square} of the
deviation from the mean.  (For this reason, variance is sometimes
called the ``mean squared deviation''.)  But why bother squaring?  Why
not simply compute the average deviation from the mean?  That is, why
not define variance to be $\Ex(R - \Ex(R))$?

The problem with this definition is that the positive and negative
deviations from the mean exactly cancel.  By linearity of expectation,
we have:
\begin{displaymath}
  \Ex(R - \Ex(R)) = \Ex(R) - \Ex(\Ex(R))
\end{displaymath}
Since $\Ex(R)$ is a constant, its expected value is itself. Therefore
\begin{displaymath}
  \Ex(R - \Ex(R)) = \Ex(R) - \Ex(\Ex(R)) = \Ex(R) - \Ex(R) = 0.
\end{displaymath}
By this definition, every random variable has zero variance. That is
not useful!  Because of the square in the conventional definition,
both positive and negative deviations from the mean increase the
variance; positive and negative deviations do not cancel.

Of course, we could also prevent positive and negative deviations from
cancelling by taking an absolute value.  That is, we could define
variance to be $\Ex(|R - \Ex(R)|)$.  There is no great reason not to
use this definition.  However, the conventional version of variance
has some pleasant mathematical properties that the absolute value
variant does not.  For example, for independent random variables, the
variance of a sum is the sum of the variances; that is, $\Var(R_1 +
R_2) = \Var(R_1) + \Var(R_2)$.  We will prove this fact in the last
section.

Nevertheless, due to squaring, the variance of a random variable may
be very far from a typical deviation from the mean.  For example, in
Game B the deviation from the mean is 1000 in one outcome and -2003 in
the other.  But the variance is a whopping 2,004,002.  From a
dimensional analysis viewpoint, the ``units'' of variance are wrong:
if the random variable is in dollars, then the expectation is also in
dollars, but the variance is in square dollars.  For this reason, people
often describe random variables using standard deviation instead of
variance:

\begin{defin*}
The \emph{standard deviation} of a random variable R is denoted
$\sigma_R$ and defined as the square root of the variance:

\[
\sigma_R = \sqrt{\Var(R)} = \sqrt{\Ex((R - \Ex(R))^2)}
\]      
\end{defin*}

The standard deviation is the square root of the mean of the square of
the deviation, or the ``root mean square'' for short.  It has the same
units (dollars in our example) as the original random variable and as
the mean.  Intuitively, it measures the ``expected (average) deviation
from the mean,'' since we can think of the square root on the outside
as cancelling the square on the inside.
\begin{example}
  The standard deviation of the payoff in Game B is:
  \begin{displaymath}
    \sigma_B  = \sqrt{\Var(B)} = \sqrt{2,004,002} \approx 1416
  \end{displaymath}
  The random variable~$B$ actually deviates from the mean by either
  positive 1000 or negative 2003; therefore, the standard deviation of
  1416 describes the situations reasonably well.
\end{example}
As can be seen in the next Figure~\ref{fig:stdev}, the standard
deviation measures the ``width'' of the main part of the distribution
graph.
\begin{figure}
  \centerline{\includegraphics[height=2in]{figures/stdev}}
  \caption{The standad deviation of a distribution says how wide the
    ``main'' part of it is.}
  \label{fig:stdev}
\end{figure}



\subsection{An Alternative Definition of Variance}

There is an equivalent way to define the variance of a random variable
that is less intuitive, but often easier to use in both calculations
and proofs.  This alternative definition is stated below in the form of
a theorem.
\begin{theorem}
  \label{th:alt}
  If $R$ is a random variable, then $\Var(R) = \Ex(R^2) - \Ex(R)^2$.
\end{theorem}
Remember that $\Ex(R^2)$ is generally not equal to $\Ex(R)^2$.  The
expected value of a product is the product of the expected values only
for independent variables, and $R$ is generally not independent of
itself.
\begin{proof}
  Write $\mu = \Ex(R)$.  Then
  \begin{eqnarray*}
    \Var(R)
        & = &   \Ex((R - \mu)^2) \\
        & = &   \Ex(R^2 - 2 R \cdot \mu + \mu^2) \\
        & = &   \Ex(R^2) - \Ex(2 R \cdot \mu) + \Ex(\mu^2) \\
        & = &   \Ex(R^2) - 2 \Ex(R) \cdot \mu + \mu^2 \\
        & = &   \Ex(R^2) - 2 \Ex(R)^2 + \Ex(R)^2 \quad
           \text{(definition of $\mu$)}\\
        & = &   \Ex(R^2) - \Ex(R)^2
  \end{eqnarray*}
  The first step uses the definition of variance.  In the second step,
  we multiply out the squared term.  The third step uses linearity of
  expectation.  There are two transformations on the fourth line.  In
  the second term, we pull the constant $2 \mu$ out of the
  expectation.  In the third term, we use the fact that the
  expectation of a constant, namely $\mu^2$, is that constant.  The
  final step is simplification.
\end{proof}
This theorem gives a convenient way to compute the variance of a
random variable: find the expected value of the square and subtract
the square of the expected value.  For example, we can compute the
variance of the outcome of a fair die as follows:
\begin{gather*}
  \Ex(R^2) = \frac{1}{6} (1^2 + 2^2 + 3^2 + 4^2 + 5^2 + 6^2) = \frac{91}{6} \\
  \Ex(R)^2 = \left(3 \frac{1}{2}\right)^2 = \frac{49}{4} \\
  \Var(R)  = \Ex(R^2) - \Ex(R)^2
  = \frac{91}{6} - \frac{49}{4} = \frac{35}{12}
\end{gather*}



\subsection{Computing Variance on the Fly}

Suppose that there is a random variable $R$ defined on a uniform
sample space.  Now someone begins reading off the value of the random
variable at each sample point.  Each value is read exactly once.  How
can we compute the variance?

This problem might come up in practice if we wanted to compute the
variance of a huge set of numbers archived on tapes.  In effect, we
``hear'' each number just once, since we want to avoid multiple passes
through the data!

With our original definition of variance, this problem is difficult.  If
the values of the variable are $x_1, x_2, \ldots x_n$, then we must
compute:
\begin{displaymath}
  \Var(R)
  = \Ex((R - \Ex(R))^2)
  = \frac{(x_1 - \Ex(R))^2 + (x_2 - \Ex(R))^2 + \ldots + (x_n - \Ex(R))^2}{n}
\end{displaymath}
One approach would be to keep a running sum of the values in the
numerator.  When we are given value $x_i$, we compute $(x_i -
\Ex(R))^2$ and add it to the running sum.  At then end, we divide the
running sum by $n$ to obtain the variance.  The problem with this
approach is that we do not know the value of $\Ex(R)$ until after we
have seen all of the data!  Therefore, we need \emph{two} passes, one
to compute $\Ex(R)$ and a second to compute the variance.

A better approach is to use the second definition of variance.  This
requires that we compute:
\begin{eqnarray*}
\Var(R)
        & = & \Ex(R^2) - \Ex(R)^2 \\
        & = & \frac{x_1^2 + x_2^2 + \ldots + x_n^2}{n} -
                \left(\frac{x_1 + x_2 + \ldots + x_n}{n}\right)^2
\end{eqnarray*}
Now the problem is much easier.  We maintain a sum of all numbers seen
and also maintain a sum of the squares of all numbers seen.  That is,
we store two values, $x_1 + x_2 + \ldots + x_i$ and $x_1^2 + x_2^2 +
\ldots + x_i^2$.  Then, when we get the $(i+1)$-st number, we add $x_{i+1}$
to the first sum and $x_{i+1}^2$ to the second sum.  After all numbers
are heard, we can plug these two summations into the definition above
to find the variance.  Now finding the variance requires only a single
pass through the data!


\subsection{A Cute Corollary}

The alternate definition of variance given in Theorem~\ref{th:alt} has
a cute implication:
\begin{corollary}
  If $R$ is a random variable, then $\Ex(R^2) \geq \Ex(R)^2$.
\end{corollary}
\begin{proof}
  We first defined $\Var(R)$ as an average of a squared expression, so
  $\Var(R)$ is non-negative.  Then we proved that $\Var(R) = \Ex(R^2)
  - \Ex(R)^2$.  This implies that $\Ex(R^2) - \Ex(R)^2$ is
  non-negative.  Therefore, $\Ex(R^2) \geq \Ex(R)^2$.
\end{proof}
In words, the expectation of a square is at least the square of the
expectation. The two are equal exactly when the variance is zero:
\begin{displaymath}
  \Ex(R^2) = \Ex(R)^2 \iff \Ex(R^2) - \Ex(R)^2 = 0 \iff \Var(R) = 0
\end{displaymath}



\subsection{Zero Variance}

When does a random variable $R$ have zero variance?  When the random
variable \emph{never} deviates from the mean!
\begin{theorem}
  The variance of a random variable $R$ is zero if and only if $R =
  \Ex(R)$ for all outcomes with positive probability.
\end{theorem}
The final phrase is a technicality; for an outcome with zero
probability, $R$ can take on any value without affecting the variance.
\begin{proof}
  By the definition of variance, $\Var(R) = 0$ is equivalent to the
  condition $\Ex((R - \Ex(R))^2) = 0$.
  
  The inner expression, $(R - \Ex(R))^2$, is always non-negative
  because of the square.  As a result, $\Ex((R - \Ex(R))^2) = 0$ if an
  only if $(R - \Ex(R))^2 = 0$ for all outcomes with positive
  probability.  Now, the conditions $(R - \Ex(R))^2 = 0$ and $R =
  \Ex(R)$ are also equivalent.  Therefore, $\Var(R) = 0$ iff $R =
  \Ex(R)$ for all outcomes with positive probability.
\end{proof}



\subsection{Dealing with Constants}

The following theorem describes how the variance of a random variable
changes when it is scaled or shifted by a constant.
\begin{theorem}
  \label{th:const}
  Let $R$ be a random variable, and let $a$ and $b$ be constants. Then
  \[
  \Var(a R + b) = a^2 \Var(R)
  \]
\end{theorem}
This theorem makes two points.  First, adding a constant $b$ to a
random variable does not affect the variance.  Second, multiplying a
random variable by a constant $a$ changes the variance by an $a^2$
factor.
\begin{proof}
  We will transform the left side into the right side.  The first step
  is to expand $\Var(a R + b)$ using the alternate definition of
  variance.
  \begin{displaymath}
    \Var(a R + b) = \Ex((a R + b)^2) - \Ex(a R + b)^2
  \end{displaymath}
  We will work on the first term and then the second term.   For the
  first term, note that
  \begin{eqnarray*}
    \Ex((aR+b)^2) 
    & = &   \Ex(a^2 R^2 + 2 a b R + b^2) \\
    & = &   (\Ex(a^2 R^2) + \Ex(2 a b R) + \Ex(b^2))\\
    & = &   (a^2 \Ex(R^2) + 2 a b \Ex(R) + b^2)
  \end{eqnarray*}
  In the first step, we multiply out the squared expression in the
  first term.  The second step uses linearity of expectation, and in
  the third step, we pull all constants out of expectations.  Now we
  work on the second term:
  \begin{eqnarray*}
    \Ex(aR+b)^2
    & = &  (a \Ex(R) + b)^2 \\
    & = &  (a^2 \Ex(R)^2 + 2 a b \Ex(R) + b^2)
  \end{eqnarray*}
  In the first step, we pull the constants out of the expectation.  In
  the second step, we multiply out the square.

  Finally, we substract that (expanded) second term from the first.
  Cancelling terms, we find:
  \begin{eqnarray*}
    \Var(a R + b)
    & = &   a^2 \Ex(R^2) - a^2 \Ex(R)^2 \\
    & = &   a^2 (\Ex(R^2) - \Ex(R)^2) \\
    & = &   a^2 \Var(R)
  \end{eqnarray*}
\end{proof}
A similar rule holds for the standard deviation when a random variable
is adjusted by a constant.  Recall that standard deviation is the
square root of variance.  Therefore, adding a constant $b$ to a random
variable does not change the standard deviation.  Multiplying a random
variable by a constant $a$ multiplies the standard deviation by $a$.



\subsection{Variance of a Sum}

Earlier, we claimed that for independent random variables, the
variance of a sum is the sum of the variances.  This is stated formally
and proved below.
\begin{theorem}
  If $R_1$ and $R_2$ are independent random variables, then
  \[
  \Var(R_1 + R_2) = \Var(R_1) + \Var(R_2)
  \]
\end{theorem}
\begin{proof}
  We will transform the left side into the right side.  We begin by
  applying the alternate definition of variance.
  \begin{displaymath}
    \Var(R_1 + R_2) = \Ex((R_1 + R_2)^2) - \bigl(\Ex(R_1 + R_2)\bigr)^2
  \end{displaymath}
  We will work on the first term and then the second term separately.
  For the first term, note
  \begin{eqnarray*}
    \Ex((R_1+R_2)^2)
    & = &   \Ex(R_1^2 + 2 R_1 R_2 + R_2^2) \\
    & = &   (\Ex(R_1^2) + \Ex(2 R_1 R_2) + \Ex(R_2^2)) \\
    & = &   (\Ex(R_1^2) + 2 \Ex(R_1) \Ex(R_2) + \Ex(R_2^2)) 
  \end{eqnarray*}
  First, we multiply out the squared expression.  The second step uses
  linearity of expectation.  In the last step, we break the
  expectation of the product $R_1 R_2$ into a product of expectations;
  this is where we use the fact that $R_1$ and $R_2$ are independent.
  Now we work on the second term.
  \begin{eqnarray*}
    \bigl(\Ex(R_1+R_2)\bigr)^2
    & = & (\Ex(R_1) + \Ex(R_2))^2 \\
    & = & (\Ex(R_1)^2 + 2 \Ex(R_1) \Ex(R_2) + \Ex(R_2)^2) \\
  \end{eqnarray*}
  The first step uses linearity of expectation, and in the second step
  we multiply out the squared expression.  Now we subtract the
  (expanded) second term from the first. Cancelling and rearranging
  terms, we find that
  \begin{eqnarray*}
    \Var(R_1 + R_2)
    & = &   (\Ex(R_1^2) - \Ex(R_1)^2) +
    (\Ex(R_2^2)) - \Ex(R_2)^2) \\
    & = &   \Var(R_1) + \Var(R_2)
  \end{eqnarray*}
\end{proof}
The independence condition in the theorem is necessary.  If we ignored
this condition and took $R_1$ and $R_2$ to be the same random
variable, then we would conclude that $\Var(R + R) = \Var(R) +
\Var(R)$.  However, by Theorem~\ref{th:const}, the left side is equal
to $4 \Var(R)$, whereas the right side is $2 \Var(R)$.  Therefore, if
we remove the condition that $R_1$ and $R_2$ be independent, then the
theorem is false.

The preceding theorem extends to a collection of \emph{pairwise
  independent} random variables.  Recall that pairwise independence is
actually a much weaker condition than mutual independence.
\begin{theorem}
  \label{th:varsum}
  If $R_1, R_2, \ldots, R_n$ are pairwise independent random variables,
  then
  \[
  \Var(R_1 + R_2 + \ldots + R_n) = \Var(R_1) + \Var(R_2) + \ldots + \Var(R_n)
  \]
\end{theorem}
\begin{proof}
  We use the formula $\Var(R) = \Ex(R^2) - (E(R))^2$.
  \begin{displaymath}
    \Ex\Biggl(\biggl(\sum_{i=1}^n R_i\biggr)^2\Biggr)
    = \Ex\biggl(\sum_{i=1}^n \sum_{j=1}^n R_i R_j\biggr)
    = \sum_{i=1}^n \sum_{j=1}^n \Ex(R_i R_j).
  \end{displaymath}
  If $i = j$, $\Ex(R_i R_j) = \Ex(R_i^2)$, and if $i \neq j$, $\Ex(R_i
  R_j) = \Ex(R_i) \Ex(R_j)$ since $R_1, R_2, \ldots, R_n$ are pairwise
  independent.
  \begin{displaymath}
    \Biggl(\Ex\biggl(\sum_{i=1}^n R_i\biggr)\Biggr)^2
    = \biggl(\sum_{i=1}^n Ex(R_i)\biggr)^2
    = \sum_{i=1}^n \sum_{j=1}^n \Ex(R_i) \Ex(R_j).
  \end{displaymath}
  Putting the pieces together, the terms containing $\Ex(R_i)
  \Ex(R_j)$ cancel, which gives
  \begin{displaymath}
    \Var\biggl(\sum_{i=1}^n R_i\biggr)
    = \sum_{i=1}^n \Ex(R_i^2) - \sum_{i=1}^n \bigl(\Ex(R_i)\bigr)^2
    = \sum_{i=1}^n \Var(R_i).
  \end{displaymath}
\end{proof}



\subsection{Variance of a Binomial Distribution}

We now have enough tools to find the variance of a binomial
distribution.  Recall that if a random variable $R$ has a binomial
distribution, then
\[
\Pr(R = k) = \binom{n}{k} p^k (1-p)^{n-k}
\]
where $n$ and $p$ are parameters such that $n \geq 1$ and $0 < p < 1$.

We can think of $R$ as the sum of $n$ independent Bernoulli variables.
For example, we can regard $R$ as the number of heads that come up
when we toss $n$ independent coins, where each coin comes up heads
with probability $p$.  Formally, we can write $R = R_1 + R_2 + \cdots
+ R_n$ where
\begin{displaymath}
  R_i = \begin{cases}
    1 & \text{with probability $p$,} \\
    0 & \text{with probability $1-p$.}
  \end{cases}
\end{displaymath}
Now we can compute the variance of the binomially distributed
variable~$R$.
\begin{eqnarray*}
\Var(R)
        & = &   \Var(R_1) + \Var(R_2) + \ldots + \Var(R_n) \\
        & = &   n \Var(R_i) \\
        & = &   n (\Ex(R_i^2) - \Ex(R_i)^2) \\
        & = &   n (\Ex(R_i) - \Ex(R_i)^2) \\
        & = &   n (p - p^2)
\end{eqnarray*}
The first equation uses Theorem~\ref{th:varsum}, and the second uses
the fact that all variables $R_i$ are identically distributed and
therefore have the same variance.  We then expand $\Var(R_i)$ using
the alternate definition of variance.  In the fourth step, we observe
that $R_i^2$ and $R_i$ are the same random variable.  This is always
true for a Bernoulli random variable, because $0^2 = 0$ and $1^2 = 1$.
The last step uses the fact that the expectation of a Bernoulli
variable is the probability that the variable is 1; in this case,
$R_i$ is 1 with probability $p$.

This shows that the binomial distribution has variance $p (1 - p) n$
and standard deviation $\sqrt{p (1- p) n}$.  In the special case of an
unbiased binomial distribution ($p = \frac{1}{2}$), the variance is
$\frac{n}{4}$ and the standard deviation is $\frac{\sqrt{n}}{2}$.



\section{Chebyshev's Theorem}

Markov's Theorem uses too little information about a random variable
to always give good bounds on deviation from the mean.  With more
information, we can obtain tighter bounds. 
Chebyshev's Theorem takes the variance into account.

\subsection{Theorem statement and proof}

%Chebyshev's Theorem formalizes the intuition that the variance
%describes the tendency of a random variable to deviate from the mean.  
\begin{theorem}
Let $R$ be a random variable, and let $x$ be a positive real number.
Then
\[
\Pr(|R - \Ex(R)| \geq x) \leq \frac{\Var(R)}{x^2}
\]
\end{theorem}
\begin{proof}
The proof uses Markov's Theorem.
Note that the event $|R - \Ex(R)| \geq x$ is the same as the event $(R
- \Ex(R))^2 \geq x^2$, since the latter inequality is obtained by
squaring both sides of the former and both sides of the former are
positive.  Therefore, these two events have equal probability:
\begin{eqnarray*}
\Pr(|R - \Ex(R)| \geq x)
        & = &   \Pr((R - \Ex(R))^2 \geq x^2) \\
        &\leq&  \frac{\Ex((R - \Ex(R))^2)}{x^2} \\
        & = &   \frac{\Var(R)}{x^2}
\end{eqnarray*}
We can apply Markov's Theorem on the second line, since the random
variable $(R - \Ex(R))^2$ is non-negative.  The third step follows
from the definition of variance.
\end{proof}
There is a nice reformulation of Chebyshev's Theorem in terms of
standard deviation.
\begin{corollary}
  \label{cor:cheby}
  Let $R$ be a random variable, and let $c$ be a positive real number.
  \[
  \Pr(|R - \Ex(R)| \geq c \sigma_R) \leq \frac{1}{c^2}
  \]
\end{corollary}
\begin{proof}
  Substituting $x = c \sigma_R$ in Chebyshev's Theorem gives:
  \begin{displaymath}
    \Pr(|R - \Ex(R)| \geq c \sigma_R)
    \leq
    \frac{\Var(R)}{(c \sigma_R)^2}
    =
    \frac{1}{c^2}\,.
  \end{displaymath}
  The last equality holds because variance is the square of standard
  deviation; in particular, $\Var(R) = \sigma_R^2$.
\end{proof}



\subsection{Example}

Suppose that the average I.Q. is 100 and the standard deviation is 10.
How rare is an I.Q. of 200 or more?

Let the random variable $R$ be the I.Q. of a random person.  We are
supposing that $\Ex(R) = 100$ and $\sigma_R = 10$.  Furthermore, let's
assume that everyone has an I.Q. that is positive.  We want to compute
$\Pr(R \geq 200)$.

Since $R$ is non-negative, we can get an upper bound using Markov's
Theorem as shown below.
\begin{displaymath}
  \Pr(R \geq 200) \leq \frac{\Ex(R)}{200} = \frac{100}{200} = \frac{1}{2}\,.
\end{displaymath}
Markov's Theorem says that at most half of the people have I.Q. 200 or
more; this sounds like a very loose upper bound!  Suppose that we now
apply Chebyshev's Theorem to the same problem.
\begin{displaymath}
  \Pr(R \geq 200) = \Pr(|R - 100| \geq 100) \leq \frac{\Var(R)}{100^2}
  = \frac{10^2}{100^2} = \frac{1}{100}\,.
\end{displaymath}
The purpose of the first step is to express the desired probability in
the form required by Chebyshev's Theorem.  (There is equality because
$R$ is positive.)  We actually apply Chebyshev's Theorem in the second
step.  The remaining work is substitution and simplification.

Chebyshev's Theorem says that at most one person in a hundred has an
I.Q. of 200 or more.  Chebyshev's Theorem gives a much tighter bound
because it uses additional information, the variance of $R$.



\subsection{A One-Sided Bound}

Chebyshev's Theorem gives a ``two-sided bound''.  That is, it bounds
the probability that a random variable deviates \emph{above or below}
the mean by some amount.  What if we want only a one-sided bound?  For
example, what is the probability that a random variable deviates
\emph{above} the mean by some amount?

This question is often answered incorrectly.  The erroneous argument
runs as follows.  By Chebyshev's Theorem, $R$ deviates above or below
the mean by some amount with probability $p$.  Therefore, $R$ deviates
above the mean by this amount with probability $\frac{p}{2}$, and $R$
deviates below the mean by this amount with probability $\frac{p}{2}$.

The error in this argument is that a random variable may be more
likely to deviate above the mean than below.  For example, in the I.Q.
question, some people deviate 100 points above the mean; that is,
there are people with I.Q. greater than 200.  However, by assumption
everyone has a positive I.Q.; no one deviates 100 points below the
mean.  (The argument above is correct, however, for a probability
distribution function that is symmetric about the mean.)

The following theorem is analogous to Chebyshev's Theorem, but gives
(correct!) one-sided bounds.  We will not give a proof.
\begin{theorem}
  Let $R$ be a random variable, and let $x$ be a positive real number.
  \begin{gather*}
    \Pr(R - \Ex(R) \geq x) \leq \frac{\Var(R)}{\Var(R) + x^2}\,, \\
    \Pr(R - \Ex(R) \leq -x) \leq \frac{\Var(R)}{\Var(R) + x^2}\,.
  \end{gather*}
\end{theorem}
This theorem has a corollary analogous to Corollary~\ref{cor:cheby}.
\begin{corollary}
  \label{cor:cheby1}
  Let $R$ be a random variable, and let $c$ be a positive real number.
  \begin{gather*}
    \Pr(R - \Ex(R) \geq c \sigma_R) \leq \frac{1}{1 + c^2}\,, \\
    \Pr(R - \Ex(R) \leq - c \sigma_R) \leq \frac{1}{1 + c^2}\,.
  \end{gather*}
\end{corollary}
\begin{proof}
  Substitute $x = c \sigma_R$ in the preceding theorem.
\end{proof}
We can use this theorem to improve our solution to the I.Q. problem
just slightly.  Recall that $R$ is the I.Q. of a random person and
that $\Ex(R) = 100$ and $\sigma_R = 10$.
\begin{eqnarray*}
\Pr(R \geq 200)
        & = &           \Pr(R - 100 \geq 100) \\
        & \leq &        \frac{\Var(R)}{\Var(R) + 100^2} \\
        & = &           \frac{10^2}{10^2 + 100^2} \\
        & = &           \frac{1}{101}
\end{eqnarray*}
This shows that at most 1 person in 101 has an I.Q. of 200 or more.



\subsection{Exam Problems}

The following example shows the difference between one-sided and
two-sided bounds.  On the 6.042 final, what fraction of the class can
score two standard deviations or more \emph{above or below} the class
average?  Surprisingly, we can answer this question without any
assumptions about the range or distribution of scores!

In this case, we want a two-sided bound.  Let $R$ be the score of a
random student.  By Corollary~\ref{cor:cheby}, the probability is at
most:
\[
\Pr(|R - \Ex(R)| \geq 2 \sigma) \leq \frac{1}{2^2} = \frac{1}{4}
\]
What fraction of the class can score two standard deviations or more
\emph{above} the class average?  Now we want a one-sided bound.  By
Corollary~\ref{cor:cheby1}, the probability is at most:
\[
\Pr(R - \Ex(R) \geq 2 \sigma) \leq \frac{1}{1 + 2^2} = \frac{1}{5}
\]
This makes sense; the probability of deviating above the mean
($\frac{1}{5}$) should be smaller than the probability of deviating
above or below the mean ($\frac{1}{4}$).



\subsection{Deviation of an Unbiased Binomial Distribution}

Chebyshev's Theorem applies to any random variable.  However, for a
specific distribution, we can sometimes prove a stronger bound on
deviation from the mean.  For example, a very strong bound is possible
for an unbiased binomial distribution.
\begin{fact}
  \label{fct:binom}
  For a random variable $R$ with an unbiased binomial distribution
  \[
  \Pr(R - \Ex(R) \geq c \sigma_R) < e^{-c^2/2}
  \]
\end{fact}
Note that the bound in Chebyshev's Theorem is polynomial
($\frac{1}{c^2}$), but the bound above is exponential ($e^{-c^2/2}$).

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.

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 - \Ex(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
Corollary~\ref{cor:cheby1} is $\frac{1}{37}$.



\section{Chernoff Bounds}

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

Now let $A_1, A_2, \ldots, A_N$ be mutually independent events
over the same sample space.  Let the random variable $T$ be the number
of these events that occur.  What is the probability that at least $k$
events occur?  That is, what is $\Pr(T \geq k)$?
(This generalizes the question asked in Section \ref{sc: one} to $k$
events rather than $1$; however, note that we have also added the
assumption of mutual independence.)
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.  The
first example is a special case in that all events $A_i$ have equal
probability; that is, the coin is as likely to come up heads on one
flip as on another.  In particular, suppose that the coin comes up
heads with probability $p$.  Then all events $A_i$ have probability
$p$, and $T$ has the now-familiar binomial distribution:
\[
\Pr(T = k) = \binom{n}{k} p^k (1-p)^{n-k} = f_{n,p}(k)
\]
We studied the binomial distribution extensively two weeks ago.
Therefore, we already have an answer to the question posed above in
the special case where all events $A_i$ have equal probability.

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$.  This lecture focuses on questions of this more general
type in which the events $A_i$ may have different probabilities.

We will prove that the number of events that occur is almost always
not 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
$\frac{N}{2}$ heads.  The Chernoff Bound implies that for sufficiently
large $N$, the number of heads is almost always not much greater than
$\frac{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{The theorem}

The theorem is stated below 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]
  Let $T_1, T_2, \ldots, T_N$ be mutually independent Bernoulli
  variables, and let $T = T_1 + T_2 + \ldots + T_N$.  Then for all $c
  \geq 1$, we have
  \[
  \Pr(T \geq c \Ex(T)) \leq e^{- \alpha c \Ex(T)}
  \]
  where $\alpha = \ln c + \frac{1}{c} - 1$.
\end{theorem}
%(A similar bound holds for $\Pr(T \leq c \Ex(T))$, where $c < 1$; we
%omit this here.)
%[[[What's the exact statement of this?]]]
The formula for $\alpha$ is a little awkward.  The situation is
simpler when $c = e = 2.718\ldots$, as in the following corollary.
\begin{corollary}
  \label{cor:ebound}
  Let $T_1, T_2, \ldots, T_N$ be mutually independent Bernoulli
  variables, and let $T = T_1 + T_2 + \ldots + T_N$.
  \[
  \Pr(T \geq e \Ex(T)) \leq e^{- \Ex(T)}
  \]
\end{corollary}
\begin{proof}
  Setting $c = e$ in the Chernoff Bound gives:
  \begin{displaymath}
    \Pr(T \geq e \Ex(T))
    \leq e^{- (\ln e + \frac{1}{e} - 1) e \Ex(T)}
    = e^{- \Ex(T)}.
  \end{displaymath}
\end{proof}
We will prove the Chernoff Bound shortly.  First, let's see an
example of how it is used.



\subsection{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 +
\ldots + 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 $\Ex(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\Ex(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 constant $\alpha=\ln c +
\frac1c-1$ in the exponent?  First, note that when $c=1$, the constant
$\alpha=0$: the Chernoff bound cannot say anything useful about the
probability of exceeding the mean.  However, the constant is
increasing with $c>1$: the derivative with respect to $c$ is
\[
\frac{d\alpha}{dc} = \frac{1}{c}-\frac{1}{c^2} > 0
\]
when $c>1$.  Therefore, for \emph{any} $c>1$, you get some $\alpha>0$
in the exponent.  

In particular, consider the case of $c$ close to 1; let's say
$c=1+\epsilon$.  Then a Taylor expansion of $\alpha$ gives:
\begin{align*}
  \alpha &= \ln(1+\epsilon) + \frac{1}{1+\epsilon}-1\\
  &= (\epsilon-\epsilon^2/2+\epsilon^3/3-\cdots) +
  (1-\epsilon+\epsilon^2-\epsilon^3+\cdots) -1\\
  &= \frac12\epsilon^2-\frac23\epsilon^3-\frac34\epsilon^4+\cdots
\end{align*}
In particular, for very small $\epsilon$, we have 
$\alpha \approx \epsilon^2/2$.
In fact one can prove the following:
\begin{lemma}
  For any $\epsilon < 1$, 
  $\Pr(T \geq (1+\epsilon \Ex(T)) < e^{-\epsilon^2 \Ex(T)/3}$.
\end{lemma}
In other words, the probability of deviation by $\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{\Ex(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$,
our roughly the square root of the expectation. 



\subsection{Proof of the Chernoff Bound}

The Chernoff Bound has the most difficult proof of the course.
The intuition is in the first two steps; the rest is algebraic
chicanery.
\begin{displaymath}
  \Pr(T \geq c \Ex(T)) = \Pr(c^T \geq c^{c \Ex(T)})
  \leq \frac{\Ex(c^T)}{c^{c \Ex(T)}}
\end{displaymath}
The first step is a shocker; we raise both sides of the inequality in
the probability to the power $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 $\Ex(c^T)$.  This leads to a lot of
algebra.
\begin{eqnarray*}
\Ex(c^T)
        & = &   \Ex(c^{T_1 + T_2 + \ldots + T_N}) \\
        & = &   \Ex(c^{T_1}) \cdot \Ex(c^{T_2}) \cdots \Ex(c^{T_N}) \\
        & = &   \prod_{i=1}^N \Ex(c^{T_i})
\end{eqnarray*}
In the first step, we expand $T$ according to its definition.  The
second step is where we use the crucial independence assumption: since
the variables $T_i$ are independent, the variables $e^{cT_i}$ are also
independent, which means the expectation of the product is the product
of the expectations.  To simplify the product, we can rewrite
$\Ex(c^{T_i})$ as follows.
\begin{eqnarray*}
\Ex(c^{T_i})
        & = &   c^1 \Pr(T_i = 1) + c^0 \Pr(T_i = 0) \\
        & = &   c^1 \Pr(T_i = 0) + c^0 (1 - \Pr(T_i = 1)) \\
        & = &   1 + (c - 1) \Pr(T_i = 0) \\
        & \leq &
                e^{(c-1) \Pr(T_i = 1)} \\
        & = &
                e^{(c-1) \Ex(T_i)}
\end{eqnarray*}
The first step uses the definition of expected value.  The second step
uses the fact that the probability of an event is one minus the
probability of the complement.  The third step is simplification.  The
fourth line uses the inequality $1 + x \leq e^x$ which follows from
the Taylor series $e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} +
\ldots$.  The last line relies on the fact that the expected value of
a Bernoulli variable is equal to the probability that the variable is
1.

We can now substitute this bound on $\Ex(c^{T_i})$ into the product for
$\Ex(c^T)$.  The motivation for the approximation $1 + x \leq e^x$
used above is that terms of the form $e^x$ are easy to work with
inside a product.
\begin{eqnarray*}
\Ex(c^T)
        &\leq&  \prod_{i=1}^N e^{(c-1) \Ex(T_i)} \\
        & = &   e^{\sum_{i=1}^N (c-1) \Ex(T_i)} \\
        & = &   e^{(c-1) \sum_{i=1}^N \Ex(T_i)} \\
        & = &   e^{(c-1) \Ex\left(\sum_{i=1}^N T_i\right)} \\
        & = &   e^{(c-1) \Ex(T)}
\end{eqnarray*}
In the first step, we substitute the bound on $\Ex(c^{T_i})$ into the
expression for $\Ex(c^T)$.  The second equality follows from an
exponent rule.  In the third step, we pull the constant $(c-1)$ out of
the summation.  The fourth step uses linearity of expectation, and the
last step uses the definition of the random variable $T$.

Now we can substitute this bound on $\Ex(c^T)$ into the expression
derived from Markov's Theorem.  All of the remaining steps are
simplifications.
\begin{eqnarray*}
\Pr(T \geq c \Ex(T))
        & \leq &        \frac{e^{(c-1) \Ex(T)}}{c^{c \Ex(T)}} \\
        & = &   e^{(c-1) \Ex(T) - c \ln c \Ex(T)} \\
        & = &   e^{-(\ln c + \frac{1}{c} - 1) c \Ex(T)} \\
        & = &   e^{-\alpha c \Ex(T)} \quad \quad \text{ where }
                        \alpha = \ln c + \frac{1}{c} - 1
\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 + \ldots + 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, $\Ex(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 $\Ex(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 + \frac{1}{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.

In Section~\ref{sc: one} 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, however.  One
problem is that calls 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.

\end{document}
