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

\renewcommand{\coursecopyrightnames}
{\href{http://theory.lcs.mit.edu/~meyer}{Prof.~Albert~R.~Meyer}}

%\renewcommand{\coursecopyrightyear}{2002}

\begin{document}
\lecturenotes{13}{Deviation from the Mean}

\newcommand{\IQ}{I.Q.\@\xspace}
\newcommand{\ok}{\marginpar{OK?}}

\section{Expect the Mean}
We have seen several examples of random variables that never take a value
equal to their mean.  But experience suggests that we can \emph{expect}
the values of a variable to be \emph{near} its mean -- usually -- which is
why the mean is also called the ``expectation.''  In other words, the
values of a random variable \emph{probably} won't deviate \emph{very much}
from the mean.  In the next two weeks we will describe some basic results
about this central topic of \emph{deviation from the mean}, and we will
indicate how these results apply for testing hypotheses and
estimating by sampling.

In these Notes we develop two results.  The first 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.  Our second
basic result is Chebyshev's Theorem, which combines Markov's Theorem and
information about the variance to give more refined bounds.  We will also
examine properties of variance and ways to calculate it.

\section{Markov's Theorem}

Markov's theorem gives a generally rough estimate of the probability that
a random variable takes a value much larger than its mean.

The idea behind Markov's Theorem can be explained with a simple example of
\IQ measurement.  \IQ was devised so that the average \IQ measurement would
be 100.  Now from this fact alone we can conclude that at most 1/2 the
population can have an \IQ of 200 or more, because if more than half had
an \IQ of 200, then the average would have to be more than $(1/2)200 =
100$, contradicting the fact that the average is 100.  So the probability
that a randomly chosen person has an \IQ of 200 or more is at most 1/2.
Of course this is not a very strong conclusion; in fact no \IQ of over 200
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 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 200 with
probability 1/2, and 0 with probability 1/2, then its mean is 100, and the
probability of a value of 200 or more is really 1/2.  So we can't hope to
get a upper better bound on the probability of 200 than 1/2.

\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, \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}
\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\ldots
\]
This conclusion is true, but weak.  The actual probability of rolling
a 6 is $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 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, \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]$.
\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
if $R(w) \geq x$ at some sample point, $w$, then $x I_x(w) = x\cdot 1 =
x$, and if $R(w) < x$ then $x I_x(w) = x \cdot 0 = 0$.  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{R \geq x}.  &  (\text{by def. of $I_x$ because } \expect{I_x} = \pr{I_x =1})
\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{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 $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
previous  notes, we used linearity of expectation to show that
$\expect{R} = 1$.  By Markov's Theorem, the probability that $x$ or more
men get the right hat is:
\[
\pr{R \geq x} \leq \frac{\expect{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 $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$.  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.  But in
reality, the probability of this event is $1/(n!)$.  So for the hat check
problem, Markov's Theorem case gives probability bounds that are
way off.

\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.

\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

\section{Chebyshev's Theorem}

We have versions of Markov's Theorem for deviations above and below the
mean, but often we want bounds that apply in both directions, that is,
bounds on the probability that $\abs{R - \expect{R}}$ is large.

It is a bit messy to use Markov's inequality directly to bound the
probability that $\abs{R - \expect{R}} \geq x$, 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 from
Lemma~\ref{lem:Markov2} applied 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.

\subsection{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}

\section{Properties of Variance}

\subsection{Why Variance?}

The definition of variance of $R$ as $\expect{(R - \expect{R})^2}$ may
seem rather arbitrary.  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.  That is, we could define variance
to be $\expect{\abs{R - \expect{R}}}$.  There is no logical reason not to
use this definition.  However, the conventional version of variance has
some valuable mathematical properties which the absolute value version
does not.  We describe these properties in the following sections and use
them to determine the variance of some important probability
distributions.
\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

\subsection{An Alternative Definition of Variance}

There is an equivalent way to define the variance of a random variable
that is less intuitive, but is often easier to use in calculations
and proofs:
\begin{theorem}\label{th:alt}
\[
\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$.

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.
\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~(\ref{bv}) follows immediately from~(\ref{th:alt}).
\end{proof}

\begin{optional}

Theorem~\ref{th:alt} 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{th:alt} 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}

\iffalse

\subsubsection{Expectation Squared [Optional]}

\begin{optional}

The alternate definition of variance given in Theorem~\ref{th:alt} 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


\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 $R =
\expect{R}$ for all sample space outcomes with positive probability.
\end{lemma}

The final phrase is a technicality; for an outcome with zero probability,
$R$ can take on any finite value without affecting the variance.

\begin{proof}
By the definition of variance, $\variance{R} = 0$ is equivalent to the
condition $\expect{(R - \expect{R})^2} = 0$.
  
The inner expression, $(R - \expect{R})^2$, is always nonnegative because
of the square.  As a result, $\expect{(R - \expect{R})^2} = 0$ if an only
if $(R - \expect{R})^2 = 0$ for all outcomes with positive probability.
Now, the conditions $(R - \expect{R})^2 = 0$ and $R = \expect{R}$ are also
equivalent.  Therefore, $\variance{R} = 0$ iff $R = \expect{R}$ for all
outcomes with positive probability.
\end{proof}

\subsubsection{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
\begin{equation}\label{aRb}
\variance{a R + b} = a^2 \variance{R}.
\end{equation}
\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 changes the variance by a \emph{square factor}.

\begin{proof}
We will transform the left side of~(\ref{aRb}) into the right side.  The
first step is to expand $\variance{a R + b}$ using the alternate
definition of variance.
\[
\variance{a R + b} =
\expect{(a R + b)^2} - \expectsq{a R + b}.
\]
We will work on the first term and then the second term.  For the first
term, note that by linearity of expectation,
\begin{equation}\label{R2}
\expect{(aR+b)^2} = \expect{a^2 R^2 + 2 a b R + b^2} =
a^2 \expect{R^2} + 2 a b \expect{R} + b^2.
\end{equation}
Similarly for the second term:
\begin{equation}\label{2R}
\expectsq{aR+b} = (a \expect{R} + b)^2 = a^2 \expectsq{R} + 2 a b
\expect{R} + b^2.
\end{equation}

Finally, we subtract the expanded second term from the first.
\begin{align*}
\variance{a R + b} & = \expect{(a R + b)^2} - \expectsq{a R + b}
      & \text{(Theorem~\ref{th:alt})}\\
  & = a^2 \expect{R^2} + 2 a b \expect{R} + b^2 -\\
  &\quad (a^2 \expectsq{R} + 2 a b \expect{R} + b^2)
     & \text{(by~(\ref{R2}) and~(\ref{2R}))}\\
  & = a^2 \expect{R^2} - a^2 \expectsq{R}\\
  & = a^2 (\expect{R^2} - \expectsq{R})\\
  & = a^2 \variance{R} 
     & \text{(Theorem~\ref{th:alt})}
\end{align*}
\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$.  So
we have
\begin{corollary}
The standard deviation of $a R + b$ equals $a$ times the standard deviation
of $R$.
\end{corollary}

\subsection{Variance of a Sum}

Earlier, we claimed that for independent random variables, the variance of
a sum is the sum of the variances.
\iffalse

\begin{theorem}\label{indvar}
If $R_1$ and $R_2$ are independent random variables, then
\[
\variance{R_1 + R_2} = \variance{R_1} + \variance{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.
\[
\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}
\fi
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{th: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}, holds only if $R$ is
constant.

However, \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.  Matching birthdays is an example of this kind,
as we shall see below.

\begin{theorem}\label{th:varsum}[Pairwise Independent Additivity of Variance]
If $R_1, R_2, \ldots, R_n$ are \emph{pairwise} independent random
variables, then
\[
\variance{R_1 + R_2 + \ldots + R_n} = \variance{R_1} + \variance{R_2} +
  \cdots + \variance{R_n}.
\]
\end{theorem}
\begin{proof}
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 from previous Notes 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{th:alt})}\\
   &  = \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*}
\end{proof}


\section{Estimation by Random Sampling}

%\subsection{Applying Chebyshev's Theorem}

\subsection{I.Q. Example}\label{IQsec}

Suppose that, in addition to the average \IQ being 100, we also know the
standard deviation of \IQ's is 10.  How rare is an \IQ of 200 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 200}$.

We have already seen that Markov's Theorem~\ref{markovthm} gives a coarse
bound, namely,
\[
  \pr{R \geq 200} \leq \frac{1}{2}.
\]
Now we apply Chebyshev's Theorem to the same problem:
\[
\pr{R \geq 200} = \pr{\abs{R - 100} \geq 100} \leq
\frac{\variance{R}}{100^2} = \frac{10^2}{100^2} = \frac{1}{100}.
\]
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 a hundred has an
\IQ of 200 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.


\subsubsection{A One-Sided Bound (Optional)}

\begin{optional}
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 $p/2$, and $R$ deviates below the
mean by this amount with probability $p/2$.

While this argument is correct for a probability distribution function
that is symmetric about the mean, it is not correct for random variables
that are more likely to deviate above the mean than below.  For example,
in the \IQ question, some people deviate 100 points above the mean; that
is, there are people with \IQ greater than 200.  However, by assumption
everyone has a positive \IQ; no one deviates more than 100 points below
the mean.  For this reason it turns out we could actually improve the
bound of Section~\ref{IQsec} slightly---from 1 in 100 to 1 in 101.  In
general, there is a Chebyshev bound for the one-sided case that slightly
improves our two-sided bound, but we don't need to go into it.
\end{optional}

\iffalse

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 - \expect{R} \geq x} \leq \frac{\variance{R}}{\variance{R} + x^2}, \\
    \pr{R - \expect{R} \leq -x} \leq \frac{\variance{R}}{\variance{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 - \expect{R} \geq c \sigma_R} \leq \frac{1}{1 + c^2}, \\
    \pr{R - \expect{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 \IQ problem
just slightly.  Recall that $R$ is the \IQ of a random person and
that $\expect{R} = 100$ and $\sigma_R = 10$.
\begin{eqnarray*}
\pr{R \geq 200}
        & = &           \pr{R - 100 \geq 100} \\
        & \leq &        \frac{\variance{R}}{\variance{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 \IQ of 200 or more.

\subsection{Problem Scores}

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 - \expect{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 - \expect{R} \geq 2 \sigma} \leq \frac{1}{1 + 2^2} = \frac{1}{5}.
\]
This makes sense; the probability of deviating above the mean
(1/5) should be smaller than the probability of deviating
above or below the mean (1/4).
\fi

\subsection{Estimating Voting Preferences using Chebyshev's Theorem}

Suppose we want to estimate the fraction of the U.S. voting population who
would favor Al Gore over George Bush in the year 2004 presidential
election.  Let $p$ be this unknown fraction.  Let's suppose we have some
random process---say throwing darts at voter registration lists---which
will select each voter with equal probability.  We can define a Bernoulli
variable, $G_1$, by the rule that $G_1=1$ if the random voter most prefers
Gore, and $G_1=0$ otherwise.  So $\pr{G_1=1}=p$, and since $G_1=G_1^2$, we
have
\[
\expect{G_1^2} = \expect{G_1} = \prob{G_1=1} = p,
\]
and
\[
\variance{G_1} = \expect{G_1^2} - \expectsq{G_1} = p - p^2 = p(1-p).
\]

Now to estimate $p$, we take a large number, $n$, of random choices of
voters\footnote{We're choosing a random voter $n$ times \emph{with
replacement}.  That is, we don't remove a chosen voter from the set of
voters eligible to be chosen later; so we might choose the same voter more
than once in $n$ tries!  We would get a slightly better estimate if we
required $n$ \emph{different} people to be chosen, but doing so
complicates both the selection process and its analysis with little gain
in accuracy.}  and count the fraction who favor Gore.  That is, we define
$n$ variables $G_1, G_2, \dots, G_n$, where $G_i$ is interpreted to be the
indicator variable for the event that the $i$th chosen voter prefers Gore.
Since our choices are made independently, the $G_i$'s are independent.  So
formally, we model our estimation process by simply assuming we have $n$
mutually independent Bernoulli variables -- each with the same
probability, $p$, of being equal to 1.  Now let $S_n$ be their sum, that
is,
\begin{equation}\label{Sn}
S_n \eqdef \sum_{i=1}^n G_i.
\end{equation}
Then the random variable, $S_n/n$, describes the fraction of voters in our
sample who favor Gore.  The value of $S_n/n$ will be our estimate of $p$.

To understand why this estimate is useful, notice first that the expected
value of $S_n/n$ is exactly the actual fraction we're trying to estimate,
namely, $p$:
\begin{equation}
\expect{\frac{S_n}{n}} = p.
\end{equation}
\begin{proof}
\begin{align*}
\expect{\frac{S_n}{n}} & = \expect{\frac{\sum_{i=1}^n G_i}{n}}
         & \text{(by def.~(\ref{Sn}) of $S_n$)}\\
 &  = \frac{\sum_{i=1}^n \expect{G_i}}{n} 
     & \text{(linearity of expectation)}\\
 & = \frac{\sum_{i=1}^n p}{n}\\
 & = \frac{np}{n} = p.
\end{align*}
\end{proof}
The second property of $S_n/n$ is the crucial one: it's variance is $O(1/n)$:
\begin{equation}\label{Snu}
\variance{\frac{S_n}{n}} = \frac{\variance{G_1}}{n}.
\end{equation}
\begin{proof}
\begin{align*}
\variance{\frac{S_n}{n}} & =  \frac{1}{n^2} \variance{S_n}
          & \mbox{(Theorem~\ref{th:const})}\\
 & =  \frac{1}{n^2} \variance{\sum_{i=1}^n G_i} 
          & \text{(def~(\ref{Sn}) of $S_n$)}\\
 & =  \frac{1}{n^2} \sum_{i=1}^n \variance{G_i}
        & \text{(by Theorem~\ref{th:varsum} because $G_i$'s independent)}\\
 & =  \frac{1}{n^2}\cdot n\variance{G_1} =  \frac{\variance{G_1}}{n}.
\end{align*}
\end{proof}

Now Chebyshev's Theorem lets us bound the probability that our estimate is
actually close to $p$:
\begin{proposition}
\begin{equation}\label{Snx}
\pr{\abs{\frac{S_n}{n} - p} \geq x} \leq \frac{1}{4nx^2}.
\end{equation}
\end{proposition}
\begin{proof}
Note that $\variance{G_1} \leq 1/4$ because $\variance{G_1} = p(1-p)$,
and the maximum value of $p(1-p)$ is at $p=1/2$.  Now we calculate:
\begin{align*}
\pr{\abs{\frac{S_n}{n} - p} \geq x} & \leq \frac{\variance{S_n/n}}{x^2}
       & \text{(Chebyshev's bound, Theorem~\ref{chebthm})}\\
     & = \frac{\variance{G_1}/n}{x^2} & \text{(by~(\ref{Snu}))}\\
     & \leq \frac{1/4n}{x^2} = \frac{1}{4nx^2}.
\end{align*}
\end{proof}

In particular, suppose we want our estimate of $p$ to be closer than
$0.04$ at least 95\% of the time.  Namely, we want
\[
\pr{\abs{\frac{S_n}{n} - p} \geq 0.04} \leq \frac{1}{20}.
\]
Equation~(\ref{Snx}) now tells us how big an $n$ to choose, that is, how
many voters to select.  We need only choose $n$ so that
\[
\frac{156.25}{n} = \frac{1}{4n(0.04)^2} \leq \frac{1}{20},
\]
\ie $n \geq 3,125$.  So by selecting just a few \emph{thousand} voters, we
can get a close, reliable estimate (within 0.04 with probability 95/100)
of the fraction among the \emph{millions} of voters who favor Gore.

This method of estimation by sampling a quantity -- voting preference in
this example -- is a technique that can obviously be used to estimate many
other unknown quantities.  Chebyshev's Theorem can be used to determine
the quality of the estimate whenever the variance of the random sample is
known (or when the variance can itself be estimated).

Note that the total size of the voting population nowhere entered our
analysis.  This leads us to a remarkable conclusion: \emph{the actual size
of the voting population has no effect on the required poll size!}
Whether there are a few thousand, a few million, or a few billion people
in the country, polling only a few thousand is sufficient to get an
estimate with the accuracy specified above.

Actually, for this particular example, Chebyshev's Theorem gives weaker
bounds than we can obtain by other methods; a sample of considerably fewer
than 3,125 voters are needed to get the desired estimate.  This should not
be surprising, since the Chebyshev upper bound is simply the Markov bound
applied to the variable $((S_n/n)-p)^2$, and we've already seen that the
Markov bound can be much weaker than bounds derived using more complete
information about the distribution of a variable.

\subsection{Estimating Voter Preferences using Binomial Approximation}

We can improve on the Chebyshev bound for the voter preference example in
the previous section because we know that among $n$ voters, the number,
$S_n$, who prefer Gore has a binomial distribution $f_{n,p}$ -- because it
is the sum of $n$ mutually independent Bernoulli variables,
$G_1,\dots,G_n$, with the same expectation, $p$.  In determining a desired
sample size in the previous section, we essentially proved that the variance
of $S_n$ is $n\variance{G_1} = np(1-p)$, namely,
\begin{align*}
\variance{S_n} &  \eqdef \variance{\sum_{i=1}^n G_i}\\
   & =  \variance{G_1} + \cdots + \variance{G_n}
              & \text{(Theorem~\ref{th:varsum})}\\
   & =  n \variance{G_1} & \text{($G_i$'s have same distribution)}\\
   & =  n p(1 - p). & \text{(equation~(\ref{bv}))}
\end{align*}
For example, in the special case of an unbiased binomial distribution ($p
= 1/2$), the variance is $n/4$ and the standard deviation is $\sqrt{n}/2$.
Then, using only the variance of this distribution, we applied the
Chebyshev bound.

But knowing that $S_n$ has a binomial distribution allows us to get better
estimates of required sample size by applying the bounds on the cumulative
binomial distribution, $F_{n,p}$, that we derived in
\href{http://theory.lcs.mit.edu/classes/6.042/fall03/handouts/ln12.pdf}
{Notes 12}, \S4.2.  Namely,
\begin{equation}\label{ln12_42}
F_{n,p}(\alpha n)
	 \leq \frac{1 - \alpha}{1 - \alpha / p} \cdot
		\frac{2^{n H(\alpha)}}{\sqrt{2 \pi \alpha (1 - \alpha) n}} 
		\cdot p^{\alpha n} (1-p)^{(1 - \alpha) n} 
\end{equation}
for $0 \le \alpha < p$, where
\[
H(\alpha) \eqdef  \alpha \log_2 \frac{1}{\alpha} +
		(1 - \alpha) \log_2 \frac{1}{1 - \alpha}.
\]

Let $\epsilon$ be the margin of error we can tolerate, and let $\delta$ be
the probability that our result lies outside this margin.  We're
interested in having $\epsilon = 0.04$ and $\delta \le 0.05$, but the
derivation will be clearer if we postpone plugging these values in until
the end.

We want to determine the number, $n$, of times we must poll voters so that
the value, $S_n/n$, of our estimate will, with probability at least
$1-\delta$, be within $\epsilon$ of the actual fraction in the nation
favoring Gore.

We can define $\delta$, the probability that our poll is off by more
than the margin of error $\epsilon$, as follows:
\begin{eqnarray*}
\delta  & = &
        \underbrace{\pr{\frac{S_n}{n} < p - \epsilon}}_{
\begin{array}{c}
\mbox{too many in sample} \\
\mbox{prefer ``Bush''}
\end{array}}
        + \underbrace{\pr{\frac{S_n}{n} > p + \epsilon}}_{
\begin{array}{c}
\mbox{too many in sample} \\
\mbox{prefer ``Gore''}
\end{array}} \\
        & = & \pr{S_n < (p - \epsilon) n} + \pr{S_n > (p + \epsilon) n}.
\end{eqnarray*}
Each term in the definition of $\delta$ can be evaluated using the
bound~(\ref{ln12_42}) on $F_{n,p}$.

In the second term of the equation for $\delta$, we must ensure that
$\alpha < p$.  We observe that
\[
\pr{\frac{S_n}{n} > p + \epsilon} = \pr{\frac{n - S_n}{n} < (1 - p) - \epsilon},
\]
where $(n - S_n)/n$ is the fraction of voters polled who prefer Bush, 
and $1-p$ is the national fraction who prefer Bush.  This gives
\begin{equation}\label{Fnpe}
F_{n,p}((p - \epsilon) n) + F_{n,1-p}((1-p-\epsilon) n)
\end{equation}
as an upper bound for $\delta$.

The problem with the bound~(\ref{Fnpe}) is that the expression contains
$p$, the fraction of Americans that prefer Gore.  This is the
number we are trying to determine by polling!  Fortunately, as in the
example of applying the Chebyshev bound in the previous section, the worst
case is when $p=1/2$.  Namely, a proof using elementary calculus, which
we omit, shows that:
\begin{fact*}
For all $\epsilon$, the maximum value of expression~(\ref{Fnpe}) bounding
$\delta$ occurs when $p = 1/2$.
\end{fact*}
So we get
\begin{align}
\delta & \leq F_{n,1/2}((\frac{1}{2} - \epsilon) n) +
   F_{n,1 - 1/2}((1-\frac{1}{2}-\epsilon) n)\notag\\
 & = 2 F_{n,1/2}((\frac{1}{2} - \epsilon) n)\notag\\
 & = 2 F_{n,1/2}(\alpha n)  &(\alpha \eqdef (\frac{1}{2} -
   \epsilon))\notag\\
 & \le 2 \frac{1 - \alpha}{1 - \alpha / (1/2)} \cdot
		\frac{2^{n H(\alpha)}}{\sqrt{2 \pi \alpha (1 - \alpha) n}} 
		\cdot (1/2)^{\alpha n} (1/2)^{(1 - \alpha) n}  &\text{(by~(\ref{ln12_42}))}\notag\\
 & =  2 \frac{1 - \alpha}{1 - 2\alpha} \cdot
		\frac{2^{n H(\alpha)}}{\sqrt{2 \pi \alpha (1 - \alpha) n}}
		\cdot (1/2)^n\notag\\
 & = 2 \frac{1 - \alpha}{1 - 2\alpha} \cdot
		\frac{2^{n (H(\alpha) - 1)}}{\sqrt{2 \pi \alpha (1 - \alpha) n}} \label{delta bound}
\end{align}

Since $\epsilon = 0.04$, we have
\begin{align*}
\alpha & = 0.46,\\
2 \frac{1 - \alpha}{1 - 2\alpha} & = 6.75\\
H(\alpha) & < .99538,\\
\sqrt{2 \pi \alpha (1 - \alpha)} & > 1.2492,
\end{align*}
so~(\ref{delta bound}) gives the following upper bound for $\delta$:
\begin{equation}\label{db2}
6.75 \cdot \frac{2^{n(-0.00462)}}{1.2492 \sqrt{n}}.
\end{equation}
We want to poll enough people so that~(\ref{db2}) and, therefore $\delta$,
is less than $0.05$.  The easiest way is to plug in values for $n$, the
number of people polled:
\[
\begin{array}{c|l}
\mbox{$n$ = people polled} & \begin{array}{cc}
\mbox{upper bound on} \\
\mbox{probability poll is wrong}
\end{array} \\
\hline
500 &  9.7\% \\
600 &  6.4\% \\
623 &  5.9\% \\
650 &  5.3\% \\
662 &  5.0\% \quad \leftarrow \quad \mbox{our poll size} \\
700 &  4.3\% \\
\end{array}
\]
So 95\% of the time, polling 662 people will yield a fraction that is
within 0.04 of the actual fraction of voters preferring Gore.  By
comparison, the sample size we got using Chebyshev's theorem was nearly
five times larger.

\subsection{Birthdays again}

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.

We've already seen that in a class of one hundred or more, there is a very
high probability that some pair of students have birthdays on the same day
of the month.  We can also easily calculate the expected number of pairs
of students with matching birthdays.  But how close to this expected
value can we expect in a typical class?  We can take the same approach to
answering this question as we did in estimating voter preferences.

But notice that 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, \viz
these two events really are 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.  So even though the events that different pairs of
students have matching birthdays are not mutually independent, indeed not
even three-way independent, they are \emph{pairwise} independent.

This allows 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
people in $n$ consecutive random choices, and let $E_{i,j}$ be the
indicator variable for the event that the birthdays on $i$th and $j$th
choices match, that is, the event $[B_i = B_j]$.  We'll assume that for
$i\neq j$, the probability that $B_i = B_j$ is 1/365, so $\expect{E_{i,j}}
= 1/365$.  We'll also assume the people are chosen independently, so the
$B_i$'s are in fact \emph{mutually} independent variables.  As noted
above, the variables $E_{i,j}$ are \emph{not} mutually independent, but
they are \emph{pairwise} independent, which is all we will need.

Let $M_n$ be the number of matching pairs of birthdays among the $n$
choices, \ie
\begin{equation}\label{Vn}
M_n \eqdef \sum_{1\le i < j \le n} E_{i,j}.
\end{equation}
So by linearity of expectation
\[
\expect{M_n} = \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}\frac{1}{365}.
\]
Also, by Theorem~\ref{th:varsum}, the variances of pairwise independent
variables are additive, so
\[
\variance{M_n} = \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}\frac{1}{365}\left(1-\frac{1}{365}\right).
\]

Now for our 6.042 class of 107 students, we have $\expect{M_{107}} \approx
16$ and $\variance{M_{107}} < 16 (1- 1/365) < 16$.  So by Chebyshev's
Theorem
\[
\pr{\abs{M_{107} - 16} \geq x} < \frac{16}{x^2}.
\]

Letting $x=6$, we conclude that there is a better than 50\% chance that in
a class of 107 students, the number of pairs of students with the same
birthday will be between 10 and 22.  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

\end{document}
