\iffalse

\section{Why the Mean?}

In these final Notes, we've taken it for granted that expectation is
important, and we've developed a bunch of techniques for calculating
expectations, but we haven't really explained why.  One important reason
is that the technique of estimation by sampling, which we illustrated just
for binomial sampling, has far-reaching generalizations beyond the
fraction-of-voters by polling we examined in previous Notes.

For example, suppose instead of the fraction of voters favoring one
candidate, we wanted to estimate the average age, income, family size, or
other measure of a population.  Then the same idea works: suppose we
determine a random process for selecting people.  Then the selected
person's age, income, and so on are random variables whose expected values
are the actual average age or income of the population.  Now if we
actually select a random sample of people, we can use the average of
people in the sample as an estimate for the true average in the whole
population.  Many fundamental results of probability theory explain
exactly how the reliability of such estimates improves as the sample size
increases.  We don't have time left to explore such results any further,
but we hope you've gotten the basic idea from the results we have
presented.
\fi


\hyperdef{expect}{mean}{\section{Expect the Mean}}
A random variable may never take a value anywhere near its expected value,
so why is its expected value important?  The reason is suggested by a
property of gambling games that most people recognize intuitively.
Suppose your gamble hinges on the roll of two dice, where you win if the
sum of the dice is seven.  If the dice are fair, the probabilty you win is
$1/6$, which is also your expected number of wins in one roll.  Of course
there's no such thing as $1/6$ of a win in one roll, since either you win
or you don't.  But if you play \emph{many times}, you would expect that
the \emph{fraction} of times you win would be close to $1/6$.  In fact, if
you played a lot of times and found that your fraction of wins wasn't
pretty close to $1/6$, you would become pretty sure that the dice weren't
fair.

More generally, if we independently sample a random variable many times
and compute the average of the sample values, then we really can expect
this average to be close to the expectation most of the time.  In this
section we work out a fundamental theorem about how repeated samples of a
random variable \emph{deviate from the mean}.  This theorem provides an
explanation of exactly how sampling can be used to test hypotheses and
estimate unknown quantities.

\iffalse
The first result is Markov's Theorem, which gives a simple, but typically
coarse, upper bound on the probability that the value of a random variable
is more than a certain multiple of its mean.  Markov's result holds if we
know nothing about a random variable except what its mean is and that its
values are nonnegative.  Accordingly, Markov's Theorem is very general,
but also is much weaker than results which take into account more
information about the distribution of the variable.

In many situations, we not only know the mean, but also another numerical
quantity called the \emph{variance} of the random variable.  The second
basic result is Chebyshev's Theorem, which combines Markov's Theorem and
information about the variance to give more refined bounds.
\fi

\subsection{Markov's Theorem}
Markov's theorem is an easy result that gives a generally rough estimate
of the probability that a random variable takes a value \emph{much larger}
than its mean.

The idea behind Markov's Theorem can be explained with a simple example of
\emph{intelligence quotient}, \IQ.  This quantity was devised so that the
average \IQ\ measurement would be 100.  Now from this fact alone we can
conclude that at most 1/3 the population can have an \IQ\ of 300 or more,
because if more than a third had an \IQ\ of 300, then the average would
have to be \emph{more} than $(1/3)300 = 100$, contradicting the fact that
the average is 100.  So the probability that a randomly chosen person has
an \IQ\ of 300 or more is at most 1/3.  Of course this is not a very
strong conclusion; in fact no \IQ\ of over 300 has ever been recorded.
But by the same logic, we can also conclude that at most 2/3 of the
population can have an \IQ\ of 150 or more.  \IQ's of over 150 have
certainly been recorded, though again, a much smaller fraction than 2/3 of
the population actually has an \IQ\ that high.

But although these conclusions about \IQ\ are weak, they are actually the
\emph{strongest possible} general conclusions that can be reached about a
nonnegative random variable using \emph{only} the fact that its mean is
100.  For example, if we choose a random variable equal to 300 with
probability 1/3, and 0 with probability 2/3, then its mean is 100, and the
probability of a value of 300 or more really is 1/3.  So we can't hope to
get a better upper bound than 1/3 on the probability of a value
$\geq 300$.

\iffalse
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, \dots 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}
\fi

\begin{theorem}[Markov's Theorem]\label{markovthm}
  If R is a nonnegative random variable, then for all $x > 0$
  \begin{displaymath}
    \pr{R \geq x} \leq \frac{\expect{R}}{x}.
  \end{displaymath}
\end{theorem}

\iffalse

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{\expect{R}}{6} = \frac{3.5}{6} = 0.583\dots
\]
This conclusion is true, but weak.  The actual probability of rolling
a 6 is $1/6 = 0.166\dots$.

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 nonnegativity.  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{\expect{\text{heads}}}{75} =
\frac{50}{75} = \frac{2}{3}.
\]
Markov's Theorem says that the probability of 75 or more heads is at
most $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{\expect{\text{heads}}}{100} =
\frac{50}{100} = \frac{1}{2}.
\]
If the coins 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 $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, $\expect{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
$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{\expect{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, that is, 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]$.
\fi

\begin{proof}%[Proof of Markov's Theorem]
We will show that $\expect{R} \geq x \pr{R \geq x}$.  Dividing
both sides by $x$ gives the desired result.

So let $I_x$ be the indicator variable for the event $[R \geq x]$, and
consider the random variable $x I_x$.  Note that
\[
R \geq x I_x,
\]
because at any sample point, $w$,
\begin{itemize}
\item if $R(\omega) \geq x$ then $R(\omega) \geq x = x\cdot 1 = x I_x(\omega)$, and
\item if $R(\omega) < x$ then $R(\omega) \geq 0 = x \cdot 0 = xI_x(\omega)$.
\end{itemize}
Therefore,
\begin{align*}
\expect{R} & \geq \expect{x I_x} & (\text{since } R \geq xI_x)\\
   & = x \expect{I_x} & \text{(linearity of $\expect{\cdot}$)}\\
   & = x \pr{I_x=1}  &  \text{($I_x$ is an indicator)}\\
   & = x \pr{R \geq x}.  &  (\text{def\ of $I_x$})
\end{align*}
\end{proof}

Markov's Theorem is often expressed in an alternative form, stated
below as an immediate corollary.
\begin{corollary}
If R is a nonnegative random variable, then for all $c \geq 1$
\begin{equation*}
\pr{R \geq c \cdot \expect{R}}  \leq  \frac{1}{c}.
\end{equation*}
\end{corollary}
\begin{proof}
In Markov's Theorem, set $x = c \cdot \expect{R}$.
\iffalse
This gives:
\[
\pr{R \geq c \cdot \expect{R}} \leq \frac{\expect{R}}{c \cdot \expect{R}} =
\frac{1}{c}.
\]
\fi
\end{proof}


\subsection{Applying Markov's Theorem}

Let's consider the Hat-Check problem again.  Now we ask what the
probability is that $x$ or more men get the right hat, this is, what the
value of $\pr{G \geq x}$ is.

We can compute an upper bound with Markov's Theorem.  Since we know
$\expect{G}=1$, Markov's Theorem implies
\[
\pr{G \geq x} \leq \frac{\expect{G}}{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 similar to the Hat-Check problem.  In
this case, $n$ people are eating appetizers arranged on a circular,
rotating Chinese banquet 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 $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 previous notes that $\expect{R} = 1$.  
Then of course $\expect{R} = 1$ (right?), so
applying Markov's Theorem, we find:
\begin{displaymath}
  \pr{R \geq n} \leq \frac{\expect{R}}{n} = \frac{1}{n}\,.
\end{displaymath}
So for the Chinese appetizer problem, 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 in the case
that all permutations are equally likely.  But the probability of this
event is $1/(n!)$.  So for this case, Markov's Theorem gives a probability
bound that is way off.

\subsubsection{Markov's Theorem for Bounded Variables}

Suppose we learn that the average \IQ\ among MIT students is 150 (which is
not true, by the way).  What can we say about the probability that an MIT
student has an \IQ\ of more than 200?  Markov's theorem immediately tells
us that no more than $150/200$ or $3/4$ of the students can have such a
high \IQ.  Here we simply applied Markov's Theorem to the random variable,
$R$, equal to the \IQ\ of a random MIT student to conclude:
\[
\pr{R > 200} \leq \frac{\expect{R}}{200}= \frac{150}{200} = \frac{3}{4}.
\]

But let's observe an additional fact (which may be true): no MIT student
has an \IQ\ less than 100.  This means that if we let $T \eqdef R-100$,
then $T$ is nonnegative and $\expect{T} = 50$, so we can apply Markov's
Theorem to $T$ and conclude:
\[
\pr{R > 200} = \pr{T > 100} \leq \frac{\expect{T}}{100}= \frac{50}{100} =
\frac{1}{2}.
\]
So only half, not 3/4, of the students can be as amazing as they think
they are.  A bit of a relief!

More generally, we can get better bounds applying Markov's Theorem to
$R-l$ instead of $R$ for any lower bound $l>0$ on $R$.

Similarly, if we have any upper bound, $u$, on a random variable, $S$,
then $u-S$ will be a nonnegative random variable, and applying Markov's
Theorem to $u-S$ will allow us to bound the probability that $S$ is much
\emph{less} than its expectation.

\iffalse

Suppose we know that $R \geq \ell$, then can we do better?
Let $T=R-\ell$.  Note that $T \geq 0$.  So, we can use Markov's
Theorem on $T$, to say that 
\begin{eqnarray*}
\pr{R  \geq x }   & = &   \pr{T \geq x -\ell} 
  \leq 
  \frac{\expect{T}}{x -\ell} 
  =   \frac{\expect{R - \ell}}{x - \ell}
  =   \frac{\expect{R} - \ell}{x - \ell} \\
  %& < &  \frac{\expect{R}}{x}
\end{eqnarray*}
%$\pr{R - \ell \geq x} = \pr{T \geq x} 
%\leq 
%\frac{\expect{T}}{x} 
%= \frac{\expect{R - \ell}}{x} =
%= \frac{\expect{R}{x} - \ell/x$
This gives a somewhat better bound on the probability that
$R$ goes crazy!  

\fi


\iffalse
\subsection{Why \emph{R} Must be Nonnegative}

Remember that Markov's Theorem applies only to nonnegative random
variables!  The following example shows that the theorem is false if this
restriction is removed.  Let $R$ be -10 with probability $1/2$ and 10 with
probability $1/2$.  Then we have:
\[
\expect{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{\expect{R}}{5} = \frac{0}{5} = 0.
\end{displaymath}
This is the wrong answer!  Obviously, $R$ is at least 5 with
probability $1/2$.  

On the other hand, we can still apply Markov's Theorem indirectly to
derive a bound on the probability that an arbitrary variable like $R$ is 5
more.  Namely, given any random variable, $R$ with expectation 0 and
values $\geq -10$, we can conclude that $\pr{R \geq 5} \le 2/3$.
\begin{proof}
Let $T \eqdef R+10$.  Now $T$ is a nonnegative random variable with
expectation $\expect{R + 10} = \expect{R}+10= 10$, so Markov's Theorem
applies and tells us that $\pr{T \geq 15} \le 10/15 = 2/3$.  But $T \geq
15$ iff $R \geq 5$, so $\pr{R \geq 5} \leq 2/3$, as claimed.
\end{proof}

\subsection{Deviation Below the Mean}

Markov's Theorem says that a random variable is unlikely to greatly exceed
the mean.  Correspondingly, there is a theorem that says a random variable
is unlikely to be much smaller than its mean.

\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 - \expect{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{align}
\pr{R \leq x} &  = \pr{l - R \geq l - x}\notag\\
 & \leq \frac{\expect{l - R}}{l - x}. & \text{(by Markov' Theorem)}\label{LR}
\end{align}
Applying Markov's Theorem in line~(\ref{LR}) is permissible
since $l - R$ is a nonnegative random variable and $l - x > 0$.
\end{proof}

For example, suppose that the class average on the 6.042 midterm was
75/100.  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.
\fi

\iffalse

\subsubsection{Using Markov To Analyze Non-Random Events [Optional]}
\begin{optional}

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 $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 = \set{s_1,
s_2, \dots, 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 1/2$.  To see why this means (with certainty) that at most
$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*}
So, if $\pr{R \leq 50} \leq 1/2$, then the number of students
with score 50 or less is at most $n/2$.

\end{optional}
\fi

\subsection{Chebyshev's Theorem}

We have separate versions of Markov's Theorem for the probability of
deviation \emph{above} the mean and \emph{below} the mean, but often we
want bounds that apply to \emph{distance} from the mean in either
direction, that is, bounds on the probability that $\abs{R - \expect{R}}$
is large.

It is a bit messy to apply Markov's Theorem directly to this problem,
because it's generally not easy to compute $\expect{\ \abs{R -
\expect{R}}\ }$.  However, since $\abs{R}$ and hence $\abs{R}^k$ are
nonnegative variables for any $R$, Markov's inequality also applies to the
event $[\abs{R}^k \geq x^k]$.  But this event is equivalent to the event
$[\abs{R} \geq x]$, so we have:

\begin{lemma}\label{lem:Markov2}
For any random variable~$R$, any positive integer~$k$, and any $x > 0$,
\[
\pr{\abs{R} \geq x} \leq \frac{\expect{\abs{R}^k}}{x^k}.
\]
\end{lemma}

The special case of this Lemma for $k=2$ can be applied to bound the
random variable, $\abs{R - \expect{R}}$, that measures $R$'s deviation
from its mean.  Namely
\begin{equation}\label{chebE2}
\pr{\abs{R - \expect{R}} \geq x}
  = \pr{(R - \expect{R})^2 \geq x^2} \leq \frac{\expect{(R - \expect{R})^2}}{x^2},
\end{equation}
where the inequality~(\ref{chebE2}) follows by applying
Lemma~\ref{lem:Markov2} to the nonnegative random variable, $(R -
\expect{R})^2$.  Assuming that the quantity $\expect{(R - \expect{R})^2}$
above is finite, we can conclude that the probability that $R$ deviates
from its mean by more than~$x$ is $O(1/x^2)$.

\begin{definition}\label{defvar}
The \emph{variance}, $\variance{R}$, of a random variable, $R$, is:
\[
\variance{R} \eqdef \expect{(R - \expect{R})^2}.
\]
\end{definition}

So we can restate~(\ref{chebE2}) as
\begin{theorem}[Chebyshev]\label{chebthm}
Let $R$ be a random variable, and let $x$ be a positive real number.
Then
\[
\pr{\abs{R - \expect{R}} \geq x} \leq \frac{\variance{R}}{x^2}.
\]
\end{theorem}

The expression $\expect{(R - \expect{R})^2}$ for variance is a bit
cryptic; the best approach is to work through it from the inside out.  The
innermost expression, $R - \expect{R}$, is precisely the deviation of $R$
above its mean.  Squaring this, we obtain, $(R - \expect{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.  So
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.

\subsubsection{Variance in Two Gambling Games}

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

\textbf{Game A:} We win \$2 with probability $2/3$ and lose \$1 with probability
$1/3$.

\textbf{Game B:} We win \$1002 with probability $2/3$ and lose \$2001 with
probability $1/3$.

Which game is better financially?  We have the same probability, 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
2/3 and -1 with probability 1/3.  We can compute the
expected payoff for each game as follows:
\begin{eqnarray*}
\expect{A} = 2 \cdot \frac{2}{3} + (-1) \cdot \frac{1}{3} = 1, \\
\expect{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 not apparent in their expected value,
but is captured by variance.  We can compute the $\variance{A}$ by working
``from the inside out'' as follows:
\begin{eqnarray*}
A - \expect{A}
        & = &   \left\{
                \begin{array}{cl}
                        1 & \text{ with probability } \frac{2}{3} \\
                        -2 & \text{ with probability } \frac{1}{3}
                \end{array}
                \right. \\
(A - \expect{A})^2
        & = &   \left\{
                \begin{array}{cl}
                        1 & \text{ with probability } \frac{2}{3} \\
                        4 & \text{ with probability } \frac{1}{3}
                \end{array}
                \right. \\
\expect{(A - \expect{A})^2}
        & = &   1 \cdot \frac{2}{3} + 4 \cdot \frac{1}{3} \\
\variance{A} & = & 2.
\end{eqnarray*}

Similarly, we have for $\variance{B}$:
\begin{eqnarray*}
B - \expect{B}
        & = &   \left\{
                \begin{array}{cl}
                        1001 & \text{ with probability } \frac{2}{3} \\
                        -2002 & \text{ with probability } \frac{1}{3}
                \end{array}
                \right. \\
(B - \expect{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. \\
\expect{(B - \expect{B})^2}
        & = &   1,002,001 \cdot \frac{2}{3} + 4,008,004 \cdot \frac{1}{3} \\
\variance{B} & = & 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
\$10  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{Standard Deviation}

Because of its definition in terms of the square of a random variable, the
variance of a random variable may be very far from a typical deviation
from the mean.  For example, in Game B above, the deviation from the mean
is 1001 in one outcome and -2002 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{definition}
The \emph{standard deviation}, $\sigma_R$, of a random variable, $R$, is
the square root of the variance:
\[
\sigma_R \eqdef \sqrt{\variance{R}} = \sqrt{\expect{(R - \expect{R})^2}}.
\]      
\end{definition}

So 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
canceling the square on the inside.

\begin{example}
The standard deviation of the payoff in Game B is:
\[
    \sigma_B  = \sqrt{\variance{B}} = \sqrt{2,004,002} \approx 1416.
\]

The random variable~$B$ actually deviates from the mean by either
positive 1001  or negative 2002; therefore, the standard
deviation of 1416 describes this situation reasonably well.
\end{example}

Intuitively, the standard deviation measures the ``width'' of the ``main
part'' of the distribution graph, as illustrated in
Figure~\ref{fig:stdev}.
\begin{figure}
  \centerline{\includegraphics[height=2in]{figures/stdev}}
  \caption{The standard deviation of a distribution indicates how wide the
    ``main part'' of it is.}
  \label{fig:stdev}
\end{figure}

There is a useful, simple 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{\abs{R - \expect{R}} \geq c \sigma_R} \leq \frac{1}{c^2}.
\]
\end{corollary}
Here we see explicitly how the ``likely'' values of $R$ are clustered in
an $O(\sigma_R)$-sized region around $\expect{R}$, confirming that the
standard deviation measures how spread out the distribution of $R$ is
around its mean.

\begin{proof}
  Substituting $x = c \sigma_R$ in Chebyshev's Theorem gives:
  \begin{displaymath}
    \pr{\card{R - \expect{R}} \geq c \sigma_R}
    \leq
    \frac{\variance{R}}{(c \sigma_R)^2}
    =  \frac{\sigma_R^2}{(c \sigma_R)^2}
    = \frac{1}{c^2}.
  \end{displaymath}
\iffalse
  The last equality holds because variance is the square of standard
  deviation: $\variance{R} = \sigma_R^2$.
\fi

\end{proof}

\subsubsection{The IQ\ Example}\label{IQsec}

Suppose that, in addition to the national average \IQ\ being 100, we also
know the standard deviation of \IQ's is 10.  How rare is an \IQ\ of 300 or
more?

Let the random variable, $R$, be the \IQ\ of a random person.  So we are
supposing that $\expect{R} = 100$, $\sigma_R = 10$, and $R$ is
nonnegative.  We want to compute $\pr{R \geq 300}$.

We have already seen that Markov's Theorem~\ref{markovthm} gives a coarse
bound, namely,
\[
  \pr{R \geq 300} \leq \frac{1}{3}.
\]
Now we apply Chebyshev's Theorem to the same problem:
\[
\pr{R \geq 300} = \pr{\abs{R - 100} \geq 200} \leq
\frac{\variance{R}}{200^2} = \frac{10^2}{200^2} = \frac{1}{400}.
\]
The purpose of the first step is to express the desired probability in the
form required by Chebyshev's Theorem; the equality holds because $R$ is
nonnegative.  Chebyshev's Theorem then yields the inequality.

So Chebyshev's Theorem implies that at most one person in four hundred has
an \IQ\ of 300 or more.  We have gotten a much tighter bound using the
additional information, namely the variance of $R$, than we could get
knowing only the expectation.

\subsection{Properties of Variance}

The definition of variance of $R$ as $\expect{(R - \expect{R})^2}$ may
seem rather arbitrary.
\iffalse
The 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
$\expect{R - \expect{R}}$?

The problem with this definition is that the positive and negative
deviations from the mean exactly cancel.  By linearity of expectation,
we have:
\[
  \expect{R - \expect{R}} = \expect{R} - \expect{\expect{R}}.
\]
Since $\expect{R}$ is a constant, its expected value is itself. Therefore
\[
\expect{R - \expect{R}} = \expect{R} - \expect{R} = 0.
\]
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
canceling by taking an absolute value.\fi A direct measure of average
deviation would be $\expect{\ \abs{R - \expect{R}}\ }$.  But variance has
some valuable mathematical properties which the direct measure does not,
as we explain below.

\iffalse
For example, for independent random variables, the variance of a sum
is the sum of the variances; that is, $\variance{R_1 + R_2} =
\variance{R_1} + \variance{R_2}$.  We will prove this fact below.
\fi

\subsubsection{A Formula for Variance}

Applying linearity of expectation to the formula for variance yields a convenient
alternative formula.
\begin{theorem}\label{alt:var}
\[
\variance{R} = \expect{R^2} - \expectsq{R},
\]
for any random variable, $R$.
\end{theorem}
Here we use the notation $\expectsq{R}$ as shorthand for $(\expect{R})^2$.

\iffalse
Remember that $\expect{R^2}$ is generally not equal to $\expectsq{R}$.  We
know the expected value of a product is the product of the expected values
for independent variables, but not in general.  And $R$ is not independent
of itself unless it is constant.\fi

\begin{proof}
Let $\mu = \expect{R}$.  Then
\begin{align*}
\variance{R} & =   \expect{(R - \expect{R})^2}
               & \text{(Def~\ref{defvar} of variance)}\\
        & = \expect{(R - \mu)^2} & \text{(def of $\mu$)}\\
        & = \expect{R^2 - 2  \mu R + \mu^2} \\
        & = \expect{R^2} - 2 \mu \expect{R} + \mu^2 
                & \text{(linearity of expectation)}\\
        & = \expect{R^2} - 2 \mu^2 + \mu^2
              &  \text{(def of $\mu$)}\\
        & = \expect{R^2} - \mu^2\\
        & = \expect{R^2} - \expectsq{R}.
                  &  \text{(def of $\mu$)}
\end{align*}
\end{proof}

For example, if $B$ is a Bernoulli variable where $p\eqdef \pr{B=1}$, then
\begin{equation}\label{bv}
\variance{B} = p-p^2 = p(1-p).
\end{equation}
\begin{proof}
Since $B$ only takes values 0 and 1, we have $\expect{B}=p\cdot 1 + (1-p)
\cdot 0 = p$.  Since $B = B^2$, we also have $\expect{B^2} = p$,
so~\eqref{bv} follows immediately from Theorem~\ref{alt:var}.
\end{proof}

\iffalse
\begin{optional}

Theorem~\ref{alt:var} 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*}
  \expect{R^2} = \frac{1}{6} (1^2 + 2^2 + 3^2 + 4^2 + 5^2 + 6^2) = \frac{91}{6}, \\
  \expectsq{R} = \left(3 \frac{1}{2}\right)^2 = \frac{49}{4}, \\
  \variance{R}  = \expect{R^2} - \expectsq{R}
  = \frac{91}{6} - \frac{49}{4} = \frac{35}{12}.
\end{gather*}

This result is particularly useful when we want to estimate the variance
of a random variable from a sequence $x_1,x_2,\dots,x_n$, of sample values
of the variable.

\begin{definition}
For any sequence of real numbers $x_1,x_2,\dots,x_n$, define the
\emph{sample mean}, $\mu_n$, and the \emph{sample variance}, $v_n$, of the
sequence to be:
\begin{eqnarray*}
\mu_n  & \eqdef & \frac{\sum_{i=1}^n x_i}{n},\\
v_n  & \eqdef & \frac{\sum_{i=1}^n (x_i - \mu_n)^2}{n}.
\end{eqnarray*}
\end{definition}
Notice that if we define a random variable, $R$, which is equally likely
to take each of the values in the sequence, that is $\pr{R = x_i} = 1/n$
for $i = 1,\dots,n$, then $\mu_n = \expect{R}$ and $v_n = \variance{R}$.
So Theorem~\ref{alt:var} applies to $R$ and lets us conclude that
\begin{equation}\label{vn:alt}
v_n = \frac{\sum_{i=1}^n x_i^2}{n} - \left(\frac{\sum_{i=1}^n x_i}{n}\right)^2.
\end{equation}
This leads to a simple procedure for computing the sample mean and
variance while reading the sequence $x_1,\dots,x_n$ from left to right.
Namely, 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, starting with
the values $x_1$ and $x_1^2$.  Then, as we get to the next number, $x_i$,
we add it to the first sum and add its square, $x_{i}^2$, to the second
sum.  After a single pass through the sequence $x_1,\dots,x_n$, we wind up
with the values of the two sums $\sum_{i=1}^n x_i$ and $\sum_{i=1}^n
x_i^2$.  Then we just plug these two values into~(\ref{vn:alt}) to find
the sample variance.

\end{optional}
\fi

\iffalse

\subsubsection{Expectation Squared [Optional]}

\begin{optional}

The alternate definition of variance given in Theorem~\ref{alt:var} has
a cute implication:
\begin{corollary}
If $R$ is a random variable, then $\expect{R^2} \geq \expectsq{R}$.
\end{corollary}
\begin{proof}
We first defined $\variance{R}$ as an average of a squared expression, so
$\variance{R}$ is nonnegative.  Then we proved that $\variance{R} =
\expect{R^2} - \expectsq{R}$.  This implies that $\expect{R^2} -
\expectsq{R}$ is nonnegative.  Therefore, $\expect{R^2} \geq
\expectsq{R}$.
\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}
\expect{R^2} = \expectsq{R} \text{  iff  } \expect{R^2} - \expectsq{R} = 0
\text{  iff  } \variance{R} = 0.
\end{displaymath}

\end{optional}
\fi

\iffalse

\subsubsection{Zero Variance}

When does a random variable, $R$, have zero variance?\dots when the random
variable \emph{never} deviates from the mean!
\begin{lemma}\label{zvar}
The variance of a random variable, $R$, is zero if and only if $\pr{R =
\expect{R}} = 1$.
\end{lemma}

So saying that $\variance{R}=0$ is almost the same as saying that $R$ is
constant.  Namely, it takes the constant value equal to its expectation on
all sample points with nonzero probability.  (It can take on any finite
values on sample points with zero probability without affecting the
variance.)

\begin{proof}
By the definition of variance,
\[
\variance{R} = 0\qiff \expect{(R - \expect{R})^2} = 0.
\]
The inner expression on the right, $(R - \expect{R})^2$, is always
nonnegative because of the square.  As a result, $\expect{(R -
\expect{R})^2} = 0$ if and only if $\pr{(R - \expect{R})^2 \neq 0}$ is
zero, which is the same as saying that $\pr{(R - \expect{R})^2 = 0}$ is
one.  That is,
\[
\variance{R} = 0 \qiff \pr{(R - \expect{R})^2 = 0} = 1.
\]
But the $(R - \expect{R})^2 = 0$ and $R = \expect{R}$ are different
descriptions of the same event.  Therefore,
\[
\variance{R} = 0 \qiff \pr{R = \expect{R}} =1.
\]
\end{proof}
\fi

\subsubsection{Dealing with Constants}

It helps to know how to calculate the variance of $aR+b$:

\begin{theorem}\label{var.const}
Let $R$ be a random variable, and $a$ a constant. Then
\begin{equation}\label{a2R}
\variance{a R} = a^2 \variance{R}.
\end{equation}
\end{theorem}

\begin{proof}
Beginning with the definition of variance and repeatedly applying
linearity of expectation, we have:
\begin{align*}
\variance{aR}
    & \eqdef \expect{(aR-\expect{aR})^2}\\
    & = \expect{(aR)^2 -2aR\expect{aR} + \expectsq{aR}}\\
    & = \expect{(aR)^2} -\expect{2aR\expect{aR}} + \expectsq{aR}\\
    & = a^2\expect{R^2} -2\expect{aR}\expect{aR} + \expectsq{aR}\\
    & = a^2\expect{R^2} -a^2\expectsq{R}\\
    & = a^2\paren{\expect{R^2} - \expectsq{R}}\\
    & = a^2\variance{R} & \text{(by Theorem~\ref{alt:var})}
\end{align*}
\end{proof}

It's even simpler to prove that adding a constant does not change the
variance, as the reader can verify:
\begin{theorem}\label{var+const}
Let $R$ be a random variable, and $b$ a constant. Then
\begin{equation}\label{R+b}
\variance{R+b} = \variance{R}.
\end{equation}
\end{theorem}

\insolutions{
\begin{proof}
\begin{align*}
\variance{R+b} & \eqdef \expect{((R+b) - \expect{R+b})^2}\\
               & =  \expect{((R+b) - (\expect{R}+ b))^2}\\
               & =  \expect{(R - \expect{R})^2}\\
               & = \variance{R}.
\end{align*}
\end{proof}
}

Recalling that the standard deviation is the square root of variance, we
immediately get:
\begin{corollary}
The standard deviation of $a R + b$ equals $\abs{a}$ times the standard
deviation of $R$:
\[
\sigma_{aR+b} = \abs{a}\sigma_{R}.
\]
\end{corollary}


\subsubsection{Variance of a Sum}

In general, the variance of a sum is not equal to the sum of the variances,
but variances do add for \emph{independent} variables.  In fact,
\emph{mutual} independence is not necessary: \emph{pairwise} independence
will do.  This is useful to know because there are some important
situations involving variables that are pairwise independent but not
mutually independent.

\iffalse
\begin{theorem}\label{indvar}
If $R_1$ and $R_2$ are independent random variables, then
\begin{equation}\label{vR+R}}
\variance{R_1 + R_2} = \variance{R_1} + \variance{R_2}.
\end{equation}
\end{theorem}

\begin{proof}
We may assume that $\expect{R_i} = 0$ for $i=1,2$, since we could always
replace $R_i$ by $R_i-\expect{R_i}$ in equation~\eqref{vR+R}.  This
substitution preserves the independence of the variables, and by
Theorem~\ref{var+const}, does not change the variances.

Now by Theorem~\ref{alt:var}, $\variance{R_i} = \expect{R_i^2}$ and
$\variance{R_1+R_2} = \expect{(R_1+R_2)^2}$, so we need only prove
\begin{equation}\label{E2R+R}
\expect{(R_1+R_2)^2} = \expect{R_1^2} + \expect{R_2^2}.
\end{equation}
But~\eqref{ follows from linearity of expectation and the fact that
\begin{equation}\label{rrind}}
\expect{R_1R_2} = \expect{R_1}\expect{R_2}
\end{equation}
since $R_1$ and $R_2$ are independent:
\begin{align*}
\expect{(R_1+R_2)^2}
   & = \expect{R_1^2+2R_1R_2 +R_2^2}\\
   & = \expect{R_1^2}+2\expect{R_1R_2} +\expect{R_2^2}\\
   & = \expect{R_1^2}+2\expect{R_1}\expect{R_2} +\expect{R_2^2}
             & \text{(by~\eqref{rrind})}\\
   & = \expect{R_1^2}+2\cdot 0 \cdot 0 +\expect{R_2^2}\\
   & =  \expect{R_1^2} + \expect{R_2^2}
\end{align*}
\fi

\iffalse
We will transform the left side into the right side.  We begin by
applying the alternate definition of variance.
\[
\variance{R_1 + R_2} = \expect{(R_1 + R_2)^2} - \expectsq{R_1 + R_2}.
\]

We will work on the first term and then the second term separately.
For the first term, note\begin{eqnarray*}
\expect{(R_1+R_2)^2}
& = &   \expect{R_1^2 + 2 R_1 R_2 + R_2^2} \\
& = &   \expect{R_1^2} + \expect{2 R_1 R_2} + \expect{R_2^2} \\
& = &   \expect{R_1^2} + 2 \expect{R_1} \expect{R_2} + \expect{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*}
\expectsq{R_1+R_2} & = & (\expect{R_1} + \expect{R_2})^2 \\
& = & \expectsq{R_1} + 2 \expect{R_1} \expect{R_2} + \expectsq{R_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*}
\variance{R_1 + R_2} & = &   (\expect{R_1^2} - \expectsq{R_1}) +
(\expect{R_2^2}) - \expectsq{R_2}) \\
& = &   \variance{R_1} + \variance{R_2}.
\end{eqnarray*}

\end{proof}

An independence condition is necessary.  If we ignored independence, then
we would conclude that $\variance{R + R} = \variance{R} + \variance{R}$.
However, by Theorem~\ref{var.const}, the left side is equal to $4
\variance{R}$, whereas the right side is $2 \variance{R}$.  This implies
that $\variance{R}=0$, which, by Lemma~\ref{zvar}, essentially only holds
if $R$ is constant.
\fi


\begin{theorem}\label{th:varsum}[Pairwise Independent Additivity of Variance]
If $R_1, R_2, \dots, R_n$ are \emph{pairwise} independent random
variables, then
\begin{equation}\label{vsum}
\variance{R_1 + R_2 + \cdots + R_n} = \variance{R_1} + \variance{R_2} +
  \cdots + \variance{R_n}.
\end{equation}
\end{theorem}

\begin{proof}
We may assume that $\expect{R_i} = 0$ for $i=1,\dots,n$, since we could
always replace $R_i$ by $\paren{R_i-\expect{R_i}}$ in
equation~\eqref{vsum}.  This substitution preserves the independence of
the variables, and by Theorem~\ref{var+const}, does not change the
variances.

Now by Theorem~\ref{alt:var}, $\variance{R_i} = \expect{R_i^2}$ and
$\variance{R_1+R_2+\cdots+R_n} = \expect{(R_1+R_2+\cdots+R_n)^2}$, so we
need only prove
\begin{equation}\label{E2R+R}
\expect{(R_1+R_2+\cdots+R_n)^2} = \expect{R_1^2} + \expect{R_2^2} + \cdots
+ \expect{R_n^2}
\end{equation}
But~\eqref{E2R+R} follows from linearity of expectation and the fact that
\begin{equation}\label{rrind}
\expect{R_iR_j} = \expect{R_i}\expect{R_j} = 0 \cdot 0 = 0
\end{equation}
for $i \neq j$, since $R_i$ and $R_j$ are independent.
\begin{align*}
\expect{(R_1+R_2+\cdots+R_n)^2}
   & = \expect{\sum_{1\leq i,j \leq n} R_iR_j}\\
   & = \sum_{1\leq i,j \leq n} \expect{R_iR_j}\\
   & = \sum_{1 \leq i \leq n} \expect{R_i^2}
             + \sum_{1 \leq i \neq j \leq n} \expect{R_iR_j}\\
   & = \sum_{1 \leq i \leq n} \expect{R_i^2}
            + \sum_{1 \leq i \neq j \leq n} 0 
             & \text{(by~\eqref{rrind})}\\
   & =  \expect{R_1^2} + \expect{R_2^2} + \cdots + \expect{R_n^2}.
\end{align*}

\iffalse
By linearity of expectation, we have
\begin{align}
\expect{\biggl(\sum_{i=1}^n R_i\biggr)^2} &
    = \expect{\sum_{i=1}^n \sum_{j=1}^n R_i R_j} \notag\\
   &  = \sum_{i=1}^n \sum_{j=1}^n \expect{R_i R_j} & \text{(linearity)}\notag\\
   & = \sum_{1\le i \neq j \le n} \expect{R_i}\expect{R_j} + \sum_{i=1}^n
     \expect{R_i^2}.
       & \text{(pairwise independence)} \label{ER2}
\end{align}
In~(\ref{ER2}), we use the fact that the expectation
of the product of two independent variables is the product of their
expectations.

Also,
\begin{align}
\expectsq{\sum_{i=1}^n R_i} & = \biggl(\expect{\sum_{i=1}^n R_i}\biggr)^2 \notag\\
  &  = \biggl(\sum_{i=1}^n \expect{R_i}\biggr)^2 &\text{(linearity)} \notag\\
  &  = \sum_{i=1}^n \sum_{j=1}^n \expect{R_i} \expect{R_j}\notag\\
  & = \sum_{1\le i \neq j \le n} \expect{R_i}\expect{R_j} + \sum_{i=1}^n
     \expectsq{R_i}.\label{E2R}
\end{align}
So,
\begin{align*}
\variance{\biggl(\sum_{i=1}^n R_i\biggr)}
   & =  \expect{\biggl(\sum_{i=1}^n R_i\biggr)^2} -
\expectsq{\sum_{i=1}^n R_i}  & \text{(Theorem~\ref{alt:var})}\\
   &  = \sum_{1\le i \neq j \le n} \expect{R_i} \expect{R_j}
        + \sum_{i=1}^n \expect{R_i^2} - \\
   & \quad \paren{\sum_{1\le i \neq j \le n} \expect{R_i}\expect{R_j}
        + \sum_{i=1}^n \expectsq{R_i}}
      & \text{(by~(\ref{ER2}) and~(\ref{E2R}))}\\
   & = \sum_{i=1}^n \expect{R_i^2} - \sum_{i=1}^n \expectsq{R_i}\\
   & = \sum_{i=1}^n (\expect{R_i^2} - \expectsq{R_i})
             & \text{(reordering the sums)}\\
   & = \sum_{i=1}^n \variance{R_i}. & \text{(Theorem~\ref{th:alt})}
\end{align*}
\fi

\end{proof}

Now we have a simple way of computing the variance of a variable, $J$,
that has an $(n,p)$-binomial distribution.  We know that $J =
\sum_{k=1}^n I_k$ where the $I_k$ are mutually independent 0-1-valued
variables with $\pr{I_k=1}=p$.  The variance of each $I_k$ is $p(1-p)$
by~\eqref{bv}, so by linearity of variance, we have
\begin{lemma*}[Variance of the Binomial Distribution]
If $J$ has the $(n,p)$-binomial distribution, then
\begin{equation}\label{p1p}
\variance{J} = n \variance{I_k} = np(1-p).
\end{equation}
\end{lemma*}

%\subsection{Applying Chebyshev's Theorem}

\subsection{Estimation by Random Sampling}

\subsubsection{Polling again}

In Notes 12, we used bounds on the binomial distribution to determine
confidence levels for a poll of voter preferences of Franken vs.\ Coleman.
Now that we know the variance of the binomial distribution, we can use
Chebyshev's Theorem as an alternative approach to calculate poll size.

The setup is the same as in Notes 12: we will poll $n$ randomly chosen
voters and let $S_n$ be the total number in our sample who preferred
Franken.  We use $S_n/n$ as our estimate of the actual fraction, $p$, of
all voters who prefer Franken.  We want to choose $n$ so that our estimate
will be within $0.04$ of $p$ at least 95\% of the time.

Now $S_n$ is binomially distributed, so from~\eqref{p1p} we have
\[
\variance{S_n}  = n(p(1-p)) \leq n \cdot \frac{1}{4} = \frac{n}{4}\label{n4}
\]
The bound of 1/4 follows from the fact that $p(1-p)$ is maximized when $p
= 1-p$, that is, when $p=1/2$ (check this yourself!).

Next, we bound the variance of $S_n/n$:
\begin{align}
\variance{\frac{S_n}{n}}
       & = \paren{\frac{1}{n}}^2 \variance{S_n}
                     & \text{(by~\eqref{a2R})}\notag\\
       & \leq \paren{\frac{1}{n}}^2 \frac{n}{4} & \text{(by~\eqref{n4})}\notag\\
       & = \frac{1}{4n}\label{1/4n}
\end{align}
Now from Chebyshev and~\eqref{1/4n} we have:
\begin{equation}\label{CK}
\pr{\abs{\frac{S_n}{n} - p} \geq 0.04}
    \leq \frac{\variance{S_n/n}}{(0.04)^2}
       = \frac{1}{4n(0.04)^2} = \frac{156.25}{n}
\end{equation}

To make our our estimate with  95\% confidence, we want the righthand
side of~\eqref{CK} to be at most 1/20.  So we choose $n$ so that
\[
\frac{156.25}{n} \leq \frac{1}{20},
\]
that is,
\[
n \geq 3,125.
\]

You may remember that in Notes 12 we calculated that it was actually
sufficient to poll only 664 voters ---many fewer than the 3,125 voters we
derived using Chebyshev's Theorem.  So the bound from Chebyshev's Theorem
is not nearly as good as the bound we got earlier.  This should not be
surprising.  In applying the Chebyshev Theorem, we used only a bound on
the variance of $S_n$.  In Notes 12, on the other hand, we used the fact
that the random variable $S_n$ was binomial (with known parameter, $n$,
and unknown parameter, $p$).  It makes sense that more detailed
information about a distribution leads to better bounds.  But even though
the bound was not as good, this example nicely illustrates an approach to
estimation using Chebyshev's Theorem that is more widely applicable than
binomial estimations.

\subsubsection{Matching Birthdays}

There are important cases where the relevant distributions are not binomial
because the mutual independence properties of the voter preference example
do not hold.  In these cases, estimation methods based on the Chebyshev
bound may be the best approach.  Birthday Matching is an example: suppose
we have 100 students in a classroom.  What is the probability that there is
a pair of students with the same birthday?  The answer to this question
surprises most people: it turns out it is virtually certain, namely
0.999999.  Before we explain this answer, we better explain our probability
model.

\begin{itemize}

\item Let $n$ be the number of students in the class.

\item Let $d$ be the number of days in the year.

\item Let $D$ be the number of pairs of students with the same birthday.

\end{itemize}

Ignoring leap years, $d= 365$, but we'll really study the case when $d$ is
an arbitrary positive integer.  Our first assumption is that the
probability that a randomly chosen student has a given birthday is $1/d$.
This assumption is not really true, since more babies are born at certain
times of year.  However, our analysis of this problem applies to many
situations in Computer Science that are unaffected by leap days, snow days
or Spring fever, so we won't dwell on those complications.  We'll also
assume that the $n$ students in the class are chosen randomly from the
population of students, with each student equally likely to be chosen, and
choices made independently.

A sensible sample space to model this experiment consists of all ways of
assigning birthdays to the students in the class.  There are $d^n$ such
assignments, since the first person can have $d$ different birthdays, the
second person can have $d$ different birthdays, and so forth.
Furthermore, every such assignment is equally probable by our assumption
that birthdays are equally likely and independent of each other.

Now the event that some two students have the same birthday can be
expressed as $[D>0]$.  It turns out to be be easier to calculate the
complement event $[D=0]$ that everyone has a distinct birthday, which is
good enough since $\pr{D>0} = 1 - \pr{D=0}$.  At this point we have all the
assumptions needed to calculate this probability explicitly, but instead we
will ask a somewhat different question: \emph{how many} matching pairs of
birthdays should we expect, and what is the \emph{probability of getting
close} to this expected number?

Now it will be easy to calculate the expected number of pairs of students
with matching birthdays.  Then we can take the same approach as we did in
estimating voter preferences to get an estimate of the probability of
getting a number of pairs close to the expected number.

But notice that, unlike the situation with voter preferences, having
matching birthdays for different pairs of students are not mutually
independent events.  For example, knowing that Alice and Bob have matching
birthdays, and also that Ted and Alice have matching birthdays obviously
implies that Bob and Ted have matching birthdays.  On the other hand,
knowing that Alice and Bob have matching birthdays tells us nothing about
whether Alice and Carol have matching birthdays, namely, these two events
really are independent.  So even though the events that various pairs of
students have matching birthdays are not mutually independent, indeed not
even three-way independent, they are \emph{pairwise} independent.

%We already observed this
%phenomenon for the case of matching pairs among three coins in
%\href{http://theory.lcs.mit.edu/classes/6.042/fall03/handouts/ln10.pdf}
%{Notes 10}, \S12.7.  

This will allow us to apply the same reasoning to Birthday Matching as we
did for voter preference.  Namely, let $B_1,B_2,\dots,B_n$ be the birthdays
of $n$ independently chosen people, and let $E_{i,j}$ be the indicator
variable for the event that the $i$th and $j$th people chosen have the same
birthdays, that is, the event $[B_i = B_j]$.  According to our probabillity
model, the $B_i$'s are mutually independent variables, and hence the
$E_{i,j}$'s are \emph{pairwise} independent variables, which is all we will
need.  Also, the expectations of $E_{i,j}$ for $i \neq j$ equals the
probability that $B_i = B_j$, namely, $1/d$.

Now, $D$, the number of matching pairs of birthdays among the $n$
choices is simply the sum of the $E_{i,j}$'s:
\begin{equation}\label{Vn}
D \eqdef \sum_{1\le i < j \le n} E_{i,j}.
\end{equation}
So by linearity of expectation
\[
\expect{D} = \expect{\sum_{1\le i < j \le n} E_{i,j}} = 
               \sum_{1\le i < j \le n} \expect{E_{i,j}} =
               \binom{n}{2}\cdot \frac{1}{d}.
\]
Also, by Theorem~\ref{th:varsum}, the variances of pairwise independent
variables are additive, so
\[
\variance{D} = \variance{\sum_{1\le i < j \le n} E_{i,j}} = 
               \sum_{1\le i < j \le n} \variance{E_{i,j}} =
               \binom{n}{2} \cdot \frac{1}{d}\paren{1-\frac{1}{d}}.
\]

In particular, for a class of $n= 100$ students with $d=365$ possible
birthdays, we have $\expect{D} \approx 14$ and $\variance{D} < 14 (1-
1/365) < 14$.  So by Chebyshev's Theorem
\[
\pr{\abs{D - 14} \geq x} < \frac{14}{x^2}.
\]

Letting $x=6$, we conclude that there is a better than 50\% chance that in
a class of 100 students, the number of pairs of students with the same
birthday will be between 8 and 20.  

%In fact, there turned out to be
%\emph{exactly} the 16 matches expected in the class this term!

\iffalse
Add another calculation, say for a 6.001 class of 400, or for uniform
selection of numbers from 1 to 1,000,000.
\fi

\hyperdef{pairwise}{independent}{\subsection{Pairwise Independent Sampling}}

The reasoning we used above to analyze voter polling and matching
birthdays is very similar.  We summarize it in slightly more general form
with a basic result we call the Pairwise Independent Sampling Theorem.  In
particular, we do not need to restrict ourselves to sums of zero-one
valued variables, or to variables with the same distribution.  For
simplicity, we state the Theorem for pairwise independent variables with
possibly different distributions but with the same mean and variance.

\begin{theorem*}[Pairwise Independent Sampling]
Let $G_1, \dots, G_n$ be pairwise independent variables with the same
mean, $\mu$, and deviation, $\sigma$ .  Define
\begin{equation}\label{ln14.Sn}
S_n \eqdef \sum_{i=1}^n G_i.
\end{equation}
Then
\[
\pr{\abs{\frac{S_n}{n} - \mu} \geq x}
    \leq \frac{1}{n} \paren{\frac{\sigma}{x}}^2.
\]
\end{theorem*}

\begin{proof}
We observe first that the expectation of $S_n/n$ is $\mu$:
\begin{align*}
\expect{\frac{S_n}{n}} & = \expect{\frac{\sum_{i=1}^n G_i}{n}}
         & \text{(def of $S_n$)}\\
 & = \frac{\sum_{i=1}^n \expect{G_i}}{n} 
     & \text{(linearity of expectation)}\\
 & = \frac{\sum_{i=1}^n \mu}{n}\\
 & = \frac{n\mu}{n} = \mu.
\end{align*}

The second important property of $S_n/n$ is that its variance is the
variance of $G_i$ divided by $n$:
\begin{align}
\variance{\frac{S_n}{n}} & =  \paren{\frac{1}{n}}^2 \variance{S_n}
          & \mbox{(by~\eqref{a2R})}\notag\\
 & =  \frac{1}{n^2} \variance{\sum_{i=1}^n G_i} 
          & \text{(def of $S_n$)}\notag\\
 & =  \frac{1}{n^2} \sum_{i=1}^n \variance{G_i}
        & \text{(pairwise independent additivity)}\notag\\
 & =  \frac{1}{n^2}\cdot n\sigma^2 =  \frac{\sigma^2}{n}.\label{Snu}
\end{align}

This is enough to apply Chebyshev's Bound and conclude:
\begin{align*}
\pr{\abs{\frac{S_n}{n} - \mu} \geq x} & \leq \frac{\variance{S_n/n}}{x^2}.
       & \text{(Chebyshev's bound)}\\
    & = \frac{\sigma^2/n}{x^2} & \text{(by~(\ref{Snu}))}\\
    & = \frac{1}{n} \paren{\frac{\sigma}{x}}^2.
\end{align*}

\end{proof}

The Pairwise Independent Sampling Theorem provides a precise general
statement about how the average of independent samples of a random
variable approaches the mean.  In particular, it proves what is known as
the Law\footnote{This is the \emph{Weak} Law of Large Numbers.  As you
might suppose, there is also a Strong Law, but it's outside the scope of
6.042.} of Large Numbers: by choosing a large enough sample size, $n$, we
can get arbitrarily accurate estimates of the mean with confidence
arbitrarily close to 100\%.

\endinput