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

\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}
%\renewcommand{\coursecopyrightyear}{2002}

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

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

\section{What the Mean Means}
 
We have focused on the expectation of a random variable because it
indicates the ``average value'' the random variable will take.  But what
precisely does this mean?

We know a random variable may never actually equal its expectation.  We
also know, for example, that if we flip a fair coin 100 times, the chance
that we actually flip \emph{exactly} 50 heads is only about 8\%.  In fact,
it gets less and less likely as we continue flipping that the number of
heads will exactly equal the expected number, \eg the chance of exactly
500 heads in 1000 flips is less than 3\%, in 1,000,000 flips less than
0.1\%, \dots.

But what is true is that the fraction of heads flipped is likely to be
\emph{close} to half of the flips, and the more flips, the closer the
fraction is likely to be to 1/2.  For example, the chance that the
fraction of heads is within 5\% of 1/2 is
\begin{itemize}
\item more than 24\% in 10 flips,
\item more than 38\% in 100 flips,
\item more than 56\% in 200 flips, and
\item more than 89\% in 1000 flips.
\end{itemize}

%%99.9999999\% in 1,000,000 flips????

These numbers illustrate the single most important phenomenon of
probability: the average value from repeated experiments is likely to be
close to the expected value of one experiment.  And it gets more likely to
be closer as the number of experiments increases.  This result was first
formulated and proved by Jacob D. Bernoulli in his book \emph{Ars
Conjectandi} (The Art of Guessing) published posthumously in 1713.  In his
Introduction, Bernoulli comments that\footnote{These quotes are taken from
Grinstead \& Snell,
\href{http://www.dartmouth.edu/~chance/teaching_aids/books_articles/probability_book/book.html}
{\emph{Introduction to Probability}}, American Mathematical Society,
p. 310.}
\begin{quote}
even the stupidest man---by some instinct of nature \emph{per se} and by
no previous instruction (this is truly amazing)---knows for sure that the
more observations \dots that are taken, the less the danger will be of
straying from the mark.
\end{quote}

But he goes on to argue that this instinct should not be taken for
granted:
\begin{quote}
Something further must be contemplated here which perhaps no one has
thought about until now.  It certainly remains to be inquired whether
after the number of observations has been increased, the probability\dots
of obtaining the true ratio\dots finally exceeds any given degree of
certainty; or whether the problem has, so to speak, its own
asymptote---that is, whether some degree of certainty is given which one
can never exceed.
\end{quote}

Here's how to give a technical formulation of the question Bernoulli wants
us to contemplate.  Repeatedly performing some random experiment
corresponds to defining $n$ random variables equal to the results of $n$
trials of the experiment.  That is, we let $G_1,\dots,G_n$ be independent
random variables with the same distribution and the same expectation,
$\mu$.  Now let $A_n$ be the average of the results, that is,
\[
A_n \eqdef \frac{\sum_{i=1}^n G_i}{n}.
\]
How sure we can be that the average value, $A_n$, will be close to $\mu$?
By letting $n$ grow large enough, can we be as certain as we want that the
average will be close, or is there is some irreducible degree of
uncertainty that remains no matter how many trials we perform?  More
precisely, given any positive tolerance, $\epsilon$, how sure can we be
that the average, $A_n$, will be within the tolerance of $\mu$ as $n$
grows?  In other words, we are asking about the limit
\[
\lim_{n \rightarrow \infty} \pr{\abs{A_n-\mu} < \epsilon}.
\]
Bernuolli asks if we can be sure this limit approaches certainty, that is,
equals one, or whether it approaches some number slightly less than one
that cannot be increased to one no matter how many times we repeat the
experiment.  His answer is that the limit is indeed one.  This result is
now known as the Weak Law of Large Numbers.  Bernoulli says of it:
\begin{quote}
Therefore, this is the problem which I now set forth and make known after
I have pondered over it for twenty years.  Both its novelty and its very
great usefulness, coupled with its just as great difficulty, can exceed in
weight and value all the remaining chapters of this thesis.
\end{quote}

With the benefit of three centuries of mathematical development since
Bernoulli, it will be a lot easier for us to resolve Bernoulli's questions
than it originally was for him.

\section{The Weak Law of Large Numbers}

The Weak Law of Large Numbers crystallizes, and confirms, the intuition of
Bernoulli's ``stupidest man'' that the average of a large number of
independent trials is more and more likely to be within a smaller and
smaller tolerance around the expectation as the number of trials grows.

\begin{theorem}\label{weaklaw-lim1}[Weak Law of Large Numbers]
Let $G_1, \dots, G_n, \dots$ be independent variables with the same
distribution and the same expectation, $\mu$.  For any $\epsilon > 0$,
\[
\lim_{n \rightarrow \infty} \prob{\abs{\frac{\sum_{i=1}^n G_i}{n} - \mu}
\leq \epsilon} = 1.
\]
\end{theorem}

This Law gives a high-level description of a fundamental probabilistic
phenomenon, but as it stands it does not give enough information to be of
practical use.  The main problem is that it does not say anything about
the \emph{rate} at which the limit is approached.  That is, how big must
$n$ be to be within a given tolerance of the expected value with a
specific desired probability?  This information is essential in
applications.  For example:
\begin{itemize}

\item Suppose we want to estimate the number of voters who are registered
Republicans.  Exactly \emph{how many} randomly selected voters should we
poll in order to be sure that 99\% of the time, the average number of
Republicans in our poll is within 1/2\% of the actual percentage in the
whole country?

\item Suppose we want to estimate the number of fish in a lake.  Our
procedure will be to catch, tag and release 500 fish caught in randomly
selected locations in the lake at random times of day.  Then we wait a few
days, and catch another 100 random fish.  Suppose we discover that 10 of
the 100 were previously tagged.  Assuming that our 500 tagged fish
represent the same proportion of the whole fish population as the ones in
our sample of 100, we would estimate that the total fish population was
5000.  But how confident can we be of this?  Specifically, \emph{how
confident} should we be that our estimate of 5000 is within 20\% of the
actual fish population?

\item Suppose we want to estimate the average size of fish in the
lake by taking the average of the sizes of the 500 in our initial catch.
How confident can we be that this average is within 2\% of the average
size of all the fish in the lake?

\iffalse
\item ADD network redundancy/reliability example to illustrate need to
estimate distribution  tails.
\fi

\end{itemize}

In these Notes we will develop three basic results about this topic of
\emph{deviation from the mean}.  The first result is Markov's Theorem,
which gives a simple but coarse upper bound on the probability that the
value of the random variable is more than a certain multiple of its mean.
Markov's result holds if we know nothing more than the value of the mean
of a random variable.  As such, it is very general, but also is much
weaker than results which take more information about the random variable
into account.

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.

The third basic result we call the Pairwise Independent Sampling Theorem.
It provides the additional information about rate of convergence we need
to calculate numerical answers to questions such as those above.  The
Sampling Theorem follows from Chebyshev's Theorem and properties of the
variance of a sum of independent variables.

Finally, the Weak Law of Large Numbers will be an easy corollary of
the Pairwise Independent Sampling Theorem.

\subsection{Markov's Theorem}

We want to consider the problem of bounding the probability that the
value of a random variable is far away from the mean. Our first
theorem, Markov's theorem, gives a very rough estimate, based only on
the value of the mean.

The idea behind Markov's Theorem can be explained with a simple example of
\IQ measurment.  \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
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$ 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} & (R \geq xI_x)\\
   & = x \expect{I_x} & \text{(linearity of expectation)}\\
   & = x \pr{R \geq x}.  &  (\expect{I_x} = \pr{I_x =1})
\end{align*}
\end{proof}

Markov's Theorem is often expressed in an alternative form, stated
below as a corollary.
\begin{corollary}
If R is a nonnegative random variable, then for all $c > 0$
\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}$.  This gives:
\[
\pr{R \geq c \cdot \expect{R}} \leq \frac{\expect{R}}{c \cdot \expect{R}} =
\frac{1}{c}.
\]
\end{proof}


\subsubsection{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}
In this case, Markov's Theorem is tight!

On the other hand, Markov's Theorem gives the same $1/N$ bound for the
probability everyone gets their hat in the hat check problem.  But in
reality, the probability of this event is $1/N!$.  So Markov's Theorem in
this case gives probability bounds that are way off.

\subsubsection{Why \emph{R} Must be Nonnegative}

The proof of Markov's Theorem requires that the random variable, $R$, be
nonnegative.  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$.  Remember that Markov's Theorem applies
only to nonnegative random variables!

On the other hand, we can still apply Markov's Theorem to bound the
probability that an arbitrary variable like $R$ is 5 more.  Namely, given
any random variable, $R'$, that, like $R$, has 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}

\subsubsection{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\%.  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\%.


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

In the previous examples, we used a theorem about a random variable to
conclude facts about non-random data.  For example, we concluded that
if the average score on a test is 75\%, then at most $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$.

\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
probabilty that $\abs{R - \expect{R}} \geq x$, since we then would have 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{corollary}\label{cor: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{corollary}

The special case of this corollary when $k=2$ can be applied to bound the
random variable, $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
Corollary~\ref{cor:Markov2} applied to the random variable, $R -
\expect{R}$.  So we can bound the probability that the random
variable~$R$ deviates from its mean by more than~$x$ by an expression
decreasing as $1/x^2$ multiplied by the constant $\expect{(R -
\expect{R})^2}$.  This constant is called the \emph{variance of~$R$}.

\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$
from the 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.  The
variance is just the average of this random variable, $\expect{(R -
\expect{R})^2}$.  Therefore, intuitively, if $R$ is always close to the
mean, then the variance will be small.  If $R$ is often far from the mean,
then the variance will be large.  For this reason, variance is useful in
studying the probability that a random variable deviates far from the
mean.

\subsection{Example: Gambling Games}

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

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

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 hidden by expected value, but
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!

\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
cancelling by taking an absolute value.  That is, we could define variance
to be $\expect{\abs{R - \expect{R}}}$.  There is no great reason not to
use this definition.  However, the conventional version of variance has
some pleasant mathematical properties that the absolute value variant does
not.  For example, for independent random variables, the variance of a sum
is the sum of the variances; that is, $\variance{R_1 + R_2} =
\variance{R_1} + \variance{R_2}$.  We will prove this fact below.

\subsection{Standard Deviation}

Due to squaring, the variance of a random variable may be very far from a
typical deviation from the mean.  For example, in Game B 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} of a random variable R is denoted
$\sigma_R$ and defined as 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
cancelling 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 the situations reasonably well.
\end{example}

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

\subsection{An Alternative Definition of Variance}

There is an equivalent way to define the variance of a random variable
that is less intuitive, but 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{(definition of $\mu$)}\\
        & = \expect{R^2} - \mu^2\\
        & = \expect{R^2} - \expectsq{R}.
                  &  \text{(definition of $\mu$)}
\end{align*}
\end{proof}

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.

\iffalse

\subsection{A Cute Corollary}

The alternate definition of variance given in Theorem~\ref{th:alt} has
a cute implication:
\begin{corollary}
If $R$ is a random variable, then $\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}
\fi


\subsection{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 outcomes with positive probability.
\end{lemma}

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

\begin{proof}
By the definition of variance, $\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}

\subsection{Dealing with Constants}

The following theorem describes how the variance of a random variable
changes when it is scaled or shifted by a constant.
\begin{theorem}\label{th:const}
Let $R$ be a random variable, and let $a$ and $b$ be constants. Then
\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 substract 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 (\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}

\subsection{Variance of a Binomial Distribution}

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

We can think of $R$ as the sum of $n$ independent Bernoulli variables.
For example, we can regard $R$ as the number of heads that come up
when we toss $n$ independent coins, where each coin comes up heads
with probability $p$.  Formally, we can write $R = R_1 + R_2 + \cdots
+ R_n$ where
\begin{displaymath}
  R_i = \begin{cases}
    1 & \text{with probability $p$,} \\
    0 & \text{with probability $1-p$.}
  \end{cases}
\end{displaymath}
Now we can compute the variance of the binomially distributed
variable~$R$.
\begin{align*}
\variance{R}
   & =  \variance{R_1} + \variance{R_2} + \ldots + \variance{R_n}
              & \text{(Theorem~\ref{th:varsum})}\\
   & =  n \variance{R_1} & (\variance{R_i} = \variance{R_j})\\
   & =  n (\expect{R_1^2} - \expectsq{R_1}) 
             & \text{(Theorem~\ref{th:alt})}\\
   & =  n (\expect{R_1} - \expectsq{R_1}) & (R_1^2 = R_1)\\
   & =  n (p - p^2). & (\expect{R_1} = \pr{R_1 = 1} = p)
\end{align*}

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


\section{Applications of Chebyshev's Theorem}

There is a nice reformulation of Chebyshev's Theorem in terms of
standard deviation.
\begin{corollary}
\label{cor:cheby}
Let $R$ be a random variable, and let $c$ be a positive real number.
\[
\pr{\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}

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

\subsection{A One-Sided Bound}

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

This question is often answered incorrectly.  The erroneous argument runs
as follows.  By Chebyshev's Theorem, $R$ deviates above or below the mean
by some amount with probability $p$.  Therefore, $R$ deviates above the
mean by this amount with probability $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.

\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

\section{Deviation of Repeated Trials}

Using Chebyshev's Theorem and the facts about variance and expectation, we
are finally in a position to be show how the average of many trials
approaches the mean.

\subsection{Estimation from Repeated Trials}

For example, 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.  Now we can
define a Bernoulli variable, $G$, by the rule that $G=1$ if a random voter
most prefers Gore, and $G=0$ otherwise.  In this case, $G=G^2$, so
\[
\expect{G^2} = \expect{G} = \prob{G=1} = p,
\]
and
\[
\variance{G} = \expect{G^2} - \expectsq{G} = p - p^2 = p(1-p).
\]

To estimate $p$, we take a large number, $n$, of sample voters and count
the fraction who favor Gore.  We can describe this estimation as taking
independent Bernoulli variables $G_1, G_2, \dots, G_n$, each with the same
expectation as $G$, computing their sum
\begin{equation}\label{Sn}
S_n \eqdef \sum_{i=1}^n G_i,
\end{equation}
and then using the average, $S_n/n$, as our estimate of $p$.

More generally, we can consider \emph{any} set of random variables $G_1,
G_2, \dots, G_n$, with the same mean, $\mu$, and likewise use the average,
$S_n/n$, to estimate $\mu$.  One of the properties of $S_n/n$ that is
critical for this purpose is that $S_n/n$ has the same expectation as the
$G_i$'s, namely,
\begin{equation}\label{Smu}
\expect{\frac{S_n}{n}} = \mu,
\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 \mu}{n}\\
 & = \frac{n\mu}{n} = \mu.
\end{align*}
\end{proof}
Note that the random variables $G_i$ need not be Bernoulli or even
independent for~(\ref{Smu}) to hold, because linearity of expectation
always holds.

Now suppose the $G_i$'s also have the same deviation, $\sigma$.  The second
critical property of $S_n/n$ is that
\begin{equation}\label{Snu}
\variance{\frac{S_n}{n}} = \frac{\sigma^2}{n}.
\end{equation}
This follows as long as the variance of $S_n$ is the sum of the variances
of the $G_i$'s.  For example, by Theorem~\ref{th:varsum}, the variances
can be summed if the $G_i$'s are pairwise independent.  Then we calculate:
\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{(variances assumed to add)}\\
 & =  \frac{1}{n^2}\cdot n\sigma^2 =  \frac{\sigma^2}{n}.
\end{align*}

This is enough to apply Chebyshev's Bound and conclude:
\begin{theorem}\label{devmean}[Pairwise Independent Sampling]
Let
\[
S_n \eqdef \sum_{i=1}^n G_i
\]
where $G_1, \dots, G_n$ are pairwise independent variables with the same
mean, $\mu$, and deviation, $\sigma$.  Then
\begin{equation}\label{Snx}
\pr{\abs{\frac{S_n}{n} - \mu} \geq x}
    \leq \frac{1}{n} \left(\frac{\sigma}{x}\right)^2.
\end{equation}
\end{theorem}

\begin{proof}
\begin{align*}
\pr{\abs{\frac{S_n}{n} - \mu} \geq x} & \leq \frac{\variance{S_n/n}}{x^2}.
       & \text{(Chebyshev's bound, Theorem~\ref{chebthm})}\\
    & = \frac{\sigma^2/n}{x^2} & \text{(by~(\ref{Snu}))}\\
    & = \frac{1}{n} \left(\frac{\sigma}{x}\right)^2.
\end{align*}
\end{proof}

Theorem~\ref{devmean} finally provides a precise statement about how the
average of independent samples of a random variable approaches the mean.
It generalizes to many cases when $S_n$ is the sum of independent
variables whose mean and deviation are not necessarily all the same,
though we shall not develop such generalizations here.

\subsection{Size of a Poll}

Theorem~\ref{devmean} allows us to calculate poll size.  How many people
should we poll to get a reliable estimate of voters' preference?

\iffalse The results will be weaker than we previously derived using
approximations to the binomial distribution, but they are still
illustrative.\fi


\iffalse
Notice that if $p=0$ or $p = 1$ our estimate is guaranteed to be
correct, so we henceforth assume $0<p<1$.
\fi

Suppose, in particular, we want to know within tolerance $x \eqdef 0.02$
what fraction of the voters favor Gore.  By choosing $n$ large enough in
Theorem~\ref{devmean} that we can reduce the probability that our estimate
is off by more than $x$ to as close to zero as we please.

For example, ninety-five per cent ``confidence level'' is a standard used
in many statistical applications.  So let's suppose we want our estimate
of $p$ to be within the tolerance 95\% of the time, that is, with
probability 0.95.  Then we choose $n$ so that $(1/n)(\sigma/x)^2 \leq 1 -
0.95$.  That is, we want
\[
n \geq \frac{\sigma^2}{(0.02)^2(1-0.95))} = \frac{p(1-p)}{0.00002} = 50,000p(1-p).
\]
Solving for the sample size $n$ in terms of the unknown $p$ that we are
trying to estimate in the first place may not seem to be making progress,
but it's easy to see that the maximum value of $p(1-p)$ in the interval
$0\leq p \leq 1$ occurs at $p=1/2$.  So we conclude that if we sample
\[
n \geq 50,000(1-1/2)1/2 = 12,500
\]
voters, we can say that 95\% of the time, our estimate $S_{12,500}/12,500$
will be within 0.02 of the fraction of voters who favor Gore.

Note that this bound on poll size holds regardless of how large the total
voting population may be---whether we are trying to determine the
preferences of a few tens of thousands of voters in a small city like
Cambridge, or of the tens of millions of voters in a large nation like the
U.S., the same poll size is adequate.

\subsection{Confidence Levels}

Now suppose a pollster dutifully checks with 12,500 randomly chosen voters
and finds that 6,300 prefer Gore.  It's tempting, but sloppy, to say that
this means ``With probability 0.95, the fraction, $p$, of voters who
prefer Gore is $6300/12,500 = 0.504 \pm 0.02$.''

What's objectionable about this statement is that it talks about the
probability of a real world fact, namely the actual value of the fraction
$p$.  But $p$ is what it is, and it simply makes no sense to talk about
the probability that it is something else.  For example, suppose $p$ is
actually 0.53; then it's nonsense to ask about the probability that it is
within 0.02 of 0.504---it simply isn't.

A more careful summary of what we have accomplished goes this way: we have
described a probabilistic procedure for estimating the actual value of the
fraction $p$.  The probability that \emph{our estimation procedure} will
yield a value within 0.02 of $p$ is 0.95.  This is a bit of a mouthful, so
special phrasing closer to the sloppy language is commonly used.  The
pollster would describe his conclusion by saying that ``At the 95\%
\emph{confidence level}, the fraction of voters who prefer Gore is $0.504
\pm 0.02$.''

Actually, polling 12,500 voters is excessive.  We derived this bound on
poll size solely by applying Chebyshev's Theorem to the value of the
variance of $S_n/n$.  But in fact we know the exact distribution of $S_n$,
namely, it has a binomial distribution with parameters $n,p$.  In the next
section we do a more detailed calculation of probabilities of deviation
from the mean specifically for the binomial distribution; we can show that
the poll size need only be about 1/5 of the size derived from the
Chebyshev bound.

\subsection{Better Polling}

Let $\epsilon$ be the acceptable error tolerance of our poll.  In the
previous section we chose $\epsilon = 0.02$.  We can define $\delta$, the
probability that our poll is off by more than $\epsilon$ as follows:
\begin{eqnarray*}
\delta  & \eqdef &
        \underbrace{\pr{\frac{S_n}{n} < p - \epsilon}}_{
\begin{array}{c}
\mbox{too many in sample} \\
\mbox{say ``Bush''}
\end{array}}
        + \underbrace{\pr{\frac{S_n}{n} > p + \epsilon}}_{
\begin{array}{c}
\mbox{too many in sample} \\
\mbox{say ``Gore''}
\end{array}} \\
        & = & \pr{S_n < (p - \epsilon) n} + \pr{S_n > (p + \epsilon) n}.
\end{eqnarray*}

Since $S_n$ has the binomial distribution with parameters $n$ and $p$,
the two terms in the definition of $\delta$ can be bounded using the
bound~(\ref{Fbyf}) on $F_{n,p}$ from Notes 10:
\begin{lemma*}
\begin{equation}\label{Fbyf}
F_{n, p}(\alpha n) \leq
\left(\frac{1 - \alpha}{1 - \alpha/p}\right) f_{n, p}(\alpha n)
\end{equation}
for $\alpha < p$.
\end{lemma*}

To 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 people polled who say that they
prefer Bush, and $1-p$ is the fraction of all Americans who prefer Bush.
This gives
\begin{equation}\label{Fnpe}
\delta \leq F_{n,p}((p - \epsilon) n) + F_{n,1-p}((1-p-\epsilon) n).
\end{equation}

As in the previous section, the bound~(\ref{Fnpe}) contains $p$, the
fraction of Americans that favor Gore, which is the number we are trying
to determine by polling.  But as before, the worst case for the bound is
when $p = 1/2$, though we shall not prove this.  So we get
\begin{equation}\label{delta bound}
\delta \leq F_{n,\frac{1}{2}}((\frac{1}{2} - \epsilon) n) +
   F_{n,1-\frac{1}{2}}((1-\frac{1}{2}-\epsilon) n)
 = 2 F_{n,\frac{1}{2}}((\frac{1}{2} - \epsilon) n).
\end{equation}

Now plugging in $\epsilon = 0.02$ into~(\ref{delta bound}) gives:
\begin{align*}
\delta \leq  2 F_{n,\frac{1}{2}}(0.48 n)
    & \leq 2 \cdot  \frac{1 - \alpha}{1 - 2\alpha} f_{n,1/2}(0.48 n)\\
    &  \approx 2 \cdot 13 \cdot 2^{-n(1 - H(0.48))}/\sqrt{2\pi \cdot 0.48(1-0.48)n}\\
    & = 26 \cdot \frac{2^{-0.00115 n}}{1.2523 \sqrt{n}}.
\end{align*}

We want to poll enough people so that $\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
1000 &  29.4\% \\
2000 &  9.3\% \\
3000 &  3.4\% \\
2500 &  5.6\% \\
2750 &  4.4\%\\
2616 &  5.004\%\\
2617 &  4.999\%
\end{array}
\]

So polling 2617 people is sufficient to determine public opinion to within
2\% with confidence of 95\%.  Again, the remarkable point is that the
population of the country has no effect on the poll size.  Whether there
are ten thousand people or a billion in a country, polling 2617 people
is sufficient!

\subsection{Birthdays again}

In the polling example, we got a much better estimate of probable
deviation from the mean using the fact that the samples were
independent---and hence that the sampling distribution was binomial---than
from the Pairwise Independent Sampling Theorem~\ref{devmean}.  This should
not be surprising, since the Sampling Theorem is based on Chebyshev's
bound, and we've already seen that the Chebyshev bound can be much weaker
than bounds derived using more information about a density function than
simply its variance.

However, there are places where mutual independence of the samples doesn't
hold, but pairwise independence does, and that's where the Pairwise
Independent Sampling Theorem becomes our main handle on predicting sample
deviations.  We've already examined one scenario which illlustrates this
point: birthday matching.

We observed in lecture that the expected number of matching birthday pairs
among $n$ people was $\binom{n}{2}/365$.  But how close to this expected
value can we expect a typical sample to be?  We can apply the Pairwise
Independent Sampling Theorem to answer this question, because whether or
not the birthdays of one pair of students match is independent of whether
the birthdays of any other pair match.  This is obvious if the pairs don't
overlap, but it holds even if they do, as we already observed in
\href{http://theory.lcs.mit.edu/classes/6.042/spring02/handouts/lectures/ln9.pdf}
{Notes 9}, \S12.5, for the case of matching pairs among three coins.  For
example, knowing that Alice and Bob have the same birthday is not relevant
to the probability that Alice and some other randomly chosen student have
the same birthday.

To apply the Sampling Theorem, let $B_1,B_2,\dots,B_n$ be the birthdays of
the $n$ people, let $E_{i,j}$ be the indicator variable for the event
$[B_i = B_j]$.  For $i\neq j$, the probability that $B_i = B_j$ is 1/365,
so $\expect{E_{i,j}} = 1/365$.

Now let $V_n$ be the number of matching pairs, \ie
\begin{equation}\label{Vn}
V_n \eqdef \sum_{1\le i < j \le n} E_{i,j}.
\end{equation}

So by linearity of expectation
\[
\expect{V_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},
\]
as we noted above.  Also, by linearity of variance for pairwise
independent variables
\[
\variance{V_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 111 students, we have $\expect{V_{111}} \approx
16.7$ and $\variance{V_{111}} = 16.7(1- 1/365) < 16.7$.  So by
Theorem~\ref{devmean},
\[
\pr{\abs{V_{111} - 16.7} \geq x} < \frac{16.7}{x^2}.
\]
Letting $x=6$, we conclude that there is a better than 50\% chance that in
a class of 111 students, the number of pairs of students with the same
birthday will be between 11 and 22.  In our class, we actually found that
there were 11 matching pairs and 1 triple, for a total of 14 matching
pairs.

\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

\section{Proof of the Weak Law}
An equivalent way to state the conclusion of the Weak Law of Large
Numbers, Theorem~\ref{weaklaw-lim1}, is that the probability that the
average \emph{differs} from the expectation by more than any given
tolerance approaches zero.

\begin{theorem}\label{weaklaw-lim0}[Weak Law of Large Numbers]
Let
\[
S_n \eqdef \sum_{i=1}^n G_i,
\]
where $G_1, \dots, G_n, \dots$ are pairwise independent variables with the
same expectation, $\mu$ and standard deviation, $\sigma$.  For any
$\epsilon > 0$,
\[
\lim_{n \rightarrow \infty} \pr{\abs{\frac{S_n}{n} - \mu} \geq \epsilon} = 0.
\]
\end{theorem}

\begin{proof}
Choose $x$ in Theorem~\ref{devmean} to be $\epsilon$.  Then, given any
$\delta>0$, choose $n$ large enough to make $(\sigma/x)^2/n < \delta$.
By Theorem~\ref{devmean},
\[
\pr{\abs{\frac{S_n}{n} - \mu} \geq \epsilon} < \delta.
\]
So the limiting probability must equal zero.
\end{proof}

Notice that this version of the Weak Law is slightly different from the
version we first stated in Theorem~\ref{weaklaw-lim1}.
Theorem~\ref{weaklaw-lim0} requires that the $G_i$'s have finite variance
but Theorem~\ref{weaklaw-lim1} only requires finite expectation.  On the
other hand, the original version~\ref{weaklaw-lim1} requires mutual
independence, while Theorem~\ref{weaklaw-lim0} requires only pairwise
independence.  The case when the variance may be infinite is not important
to us, and we will not try to prove it.

A weakness of both the Weak Law as well as our Pairwise Independence
Sampling Theorem~\ref{devmean} is that neither provides any information
about the way the average value of the observations may be expected to
\emph{oscillate} in the course of repeated experiments.  In later Notes we
will briefly consider a \emph{Strong} Law of Large Numbers which deals
with the oscillations.  Such oscillations may not be important in our
example of polling about Gore's popularity or of birthday matches, but
they are critical in gambling situations, where large oscillations can
bankrupt a player, even though the player's average winnings are assured
in the long run.  As the famous economist Keynes is alleged to have
remarked, the problem is that ``In the long run, we are all dead.''

\end{document}
