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

\newcommand{\pdf}{\textsc{PDF}}
\newcommand{\cdf}{\textsc{CDF}}

\newcommand{\IQ}{\text{IQ}}
%\newcommand{\ok}{\marginpar{OK?}}

\begin{document}
\lecturenotes{14}{Missed Expectations?}

In the previous notes, we saw that the average value of a random quantity
is captured by the mathematical concept of the expectation of a random
variable, and we calculated expectations for several kinds of random
variables.  Now we will see two things that make expectations so useful.
First, they are often very easy to calculate due to the fact that they
obey linearity.  Second, once you know what the expectation is, you can
also get some type of bound on the probability that you are far from the
expectation ---that is, you can show that really weird things are not that
likely to happen.  How good a bound you can get depends on what you know
about your distribution, but don't worry, even if you know next to
nothing, you can still say something relatively interesting.

\section{Linearity of Expectation}\label{finlin}

\subsection{Expectation of a Sum}

Expected values obey a simple, very helpful rule called
\hyperdef{ln11}{linearity}{\emph{Linearity of Expectation}}.  Its simplest
form says that the expected value of a sum of random variables is the sum
of the expected values of the variables.

\begin{theorem}\label{expsum-2}
For any random variables $R_1$ and $R_2$,
\[
\expect{R_1 + R_2} = \expect{R_1} + \expect{R_2}.
\]
\end{theorem}

\begin{proof}
Let $T \eqdef R_1+R_2$.  The proof follows straightforwardly by
rearranging terms from the definition of $\expect{T}$.
\begin{align*}
\expect{R_1 + R_2} & \eqdef \expect{T}\\
        & \eqdef \sum_{s \in \sspace} T(s) \cdot \pr{s}
                       & \\
        & = \sum_{s \in \sspace} (R_1(s) + R_2(s)) \cdot \pr{s}
                         & \text{(Def. of $T$)}\\
        & = \sum_{s \in \sspace} R_1(s) \pr{s} + 
              \sum_{s \in \sspace} R_2(s) \pr{s} & \text{(rearranging terms)}\\
        & = \expect{R_1} + \expect{R_2}.  & 
\end{align*}
\end{proof}

Similarly, we have
\begin{lemma}\label{constexp}
For any random variable $R$ and constant $a \in \reals$,
\begin{equation*}
\expect{aR} = a\expect{R}.
\end{equation*}
\end{lemma}
The proof follows easily from the definition of expectation, and we omit
it.

Combining Theorem~\ref{expsum-2} and Lemma~\ref{constexp}, we conclude
\begin{theorem}[Linearity of Expectation] \label{linexp-2-thm}
For all random variables $R_1$, $R_2$ and constants $a_1,a_2 \in \reals$,
\[
\expect{a_1R_1 + a_2R_2} = a_1\expect{R_1} + a_2\expect{R_2}.
\]
\end{theorem}
In other words, expectation is a linear function.  The rule and its proof
extends directly to cover more than two random variables:

\begin{corollary}\label{linexp-k-thm}
For any random variables $R_1, \dots, R_k$ and constants $a_1, \dots, a_k
\in \reals$,
\[
\expect{\sum_{i=1}^k a_iR_i} = \sum_{i=1}^k a_i\expect{R_i}.
\]
\end{corollary}

The great thing about linearity of expectation is that \emph{no
independence is required}.  This is really useful, because dealing with
independence is a pain, and we often need to work with random variables
that are not independent.

\iffalse Even when the random variables \emph{are} independent, we know
from previous experience that proving independence requires a lot of
work.\fi


\subsection{Expected Value of Two Dice}

What is the expected value of the sum of two fair dice?

Let the random variable $R_1$ be the number on the first die, and let
$R_2$ be the number on the second die.  We observed earlier that the
expected value of one die is 3.5.  We can find the expected value of the
sum using linearity of expectation:
\begin{equation*}
\expect{R_1 + R_2} 
 =   \expect{R_1} + \expect{R_2}
 =    3.5 + 3.5
 =    7.
\end{equation*}

Notice that we did {\em not} have to assume that the two dice were
independent.  The expected sum of two dice is 7, even if they are
connected together!\footnote{But each die must remain fair after the
connection.}

Proving that the expected sum is 7 with a tree diagram would be hard;
there are 36 cases.  And if we did not assume that the dice were
independent, the job would be a nightmare!

\subsection{The Hat-Check Problem}

There is a dinner party where $n$ men check their hats.  The hats are
mixed up during dinner, so that afterward each man receives a random hat.
In particular, each man gets his own hat with probability $1/n$.  What is
the expected number of men who get their own hat?

Without linearity of expectation, this would be a very difficult
question to answer.  We might try the following.  Let the random
variable $R$ be the number of men that get their own hat.  We want to
compute $\expect{R}$.  By the definition of expectation, we have:
%
\[
\expect{R} = \sum_{k=0}^{\infty} k \cdot \pr{R = k}
\]
%
Now we're in trouble, because evaluating $\pr{R = k}$ is a mess and we
then need to substitute this mess into a summation.  Furthermore, to
have any hope, we would need to fix the probability of each
permutation of the hats.  For example, we might assume that all
permutations of hats are equally likely.

Now let's try to use linearity of expectation.  As before, let the
random variable $R$ be the number of men that get their own hat.  The
trick is to express $R$ as a sum of indicator variables.  In
particular, let $R_i$ be an indicator for the event that the $i$th
man gets his own hat.  That is, $R_i = 1$ is the event that he gets
his own hat, and $R_i = 0$ is the event that he gets the wrong hat.
The number of men that get their own hat is the sum of these
indicators:
%
\[
R = R_1 + R_2 + \cdots + R_n
\]
%
These indicator variables are \textit{not} mutually independent.  For
example, if $n-1$ men all get their own hats, then the last man is
certain to receive his own hat.  But, since we plan to use linearity
of expectation, we don't have worry about independence!

Let's take the expected value of both sides of the equation above and
apply linearity of expectation:
%
\begin{align*}
\expect{R} & = \expect{R_1 + R_2 + \cdots + R_n} \\
       & = \expect{R_1} + \expect{R_2} + \cdots + \expect{R_n}\\
       %& = \frac1n+\frac1n+\cdots+\frac1n\\
	%& = 1.
\end{align*}
%

Since the $R_i$'s are indicator variables, $\expect{R_i} = \pr{R_i}$ and
since every man is as likely to get one hat as another, this is just $1 /
n$.  Putting all this together, we have:
%
\begin{align*}
\expect{R}	& = \expect{R_1} + \expect{R_2} + \cdots + \expect{R_n} \\
        & = \pr{R_1 = 1} + \pr{R_2 = 1} + \cdots + \pr{R_n = 1}\\
	& = n \cdot \frac{1}{n}  = 1.
\end{align*}
%
So we should expect 1 man to get his own hat back on average!

Notice that we did not assume that all permutations of hats are equally
likely or even that all permutations are possible.  We only needed to know
that each man received his own hat with probability $1/n$.  

\subsection{Expectation of a Binomial Distribution}

Suppose that we independently flip $n$ biased coins, each with probability
$p$ of coming up heads.  What is the expected number that come up heads?

Let $H_{n,p}$ be the number of heads after the flips.  Then $H_{n,p}$ has
the binomial distribution with parameters $n$ and $p$.  Now let $I_k$ be
the indicator for the $k$th coin coming up heads.  
Since $I_k$ is an indicator variable with probability $p$ of being
1, we know that 
\[
\expect{I_k} = p.
\]
But
\[
H_{n,p} = \sum_{k=1}^n I_k,
\]
so by linearity
\[
\expect{H_{n,p}} = \expect{\sum_{k=1}^n I_k} = \sum_{k=1}^n \expect{I_k} =
\sum_{k=1}^n p = pn.
\]
numbThat is, the expectation of an $(n,p)$-binomially distributed variable is
$pn$.

\iffalse
=================================================
I'm bothered by a bunch of things in the writeup below of the
Number-picking game, so have cut it:

(1) It's not obvious that pr{T is finite} = 1.  In fact, pr{finite} will be
    ZERO in the case that the "pick" is a constant RV.  I don't know if
    there are other cases with pr{finite} < 1.

    But we assumed RV's were real-valued (not infinity) at all sample
    points, and we don't want to get into infty-valued RV's, since they
    raise a bunch of technical problems, eg, how to define E[R] for R's
    which can be infinite but with probability zero.

(2) MORE IMPORTANT: the argument of taking z and y_1,..,y_k and then arguing
          pr{z >= y_1,...y_k} >= 1/(k+1)    (*)
    needs careful clarification, since the game stops before choosing k y's unless
    all the y's are <= z, but we are NOT calculating
                 pr{z >= y_k  | z >= y_1,...,y-{k-1}}
    which is a lot larger than (*).  What's intended here is that you pick k y's
    without stopping even if you beat z.

(3) There is no need to separate the unique max case from non-unique max.
    Could be argued w/o cases as follows
       "since the value of z is as likely to be the max of the values of
        z,y_1,...,y_k as the value of any of the variables, and there are at
        most k+1 values, the prob that the value of z is the max is at
        least 1/(k+1)"

(4) I don't think having this example with infinite expectation is
    important to us for any reason other than to point out that this can
    happen.  So skipping this will do no harm.  The final lecture
    on 1-D random walks yields another example where infinite expectation
    comes up if we decide it's important to emphasize that expectation may
    be infinite.

(5) FYI, an example distribution where pr(T>k) = Theta(1/k) is to have
    pr{pick = i} = Theta(1/i^2).  In this case E[\sqrt{T}] is finite, even
    though E[T] = infinity.  So we can still say a lot about average
    behavior of independent samples of T.

--- ARM, 12/3/05
===========================

\section{The Number-Picking Game}

Here is a game that you and I could play that reveals a strange
property of expectation.

First, you think of a probability density function on the natural
numbers.  Your distribution can be absolutely anything you like.  For
example, you might choose a uniform distribution on $1, 2, \dots, 6$,
like the outcome of a fair die roll.  Or you might choose a binomial
distribution on $0, 1, \dots, n$.  You can even give every natural
number a non-zero probability, provided that the sum of all
probabilities is 1.

Next, I pick a random number $z$ according to your distribution.
Then, you pick a random number $y_1$ according to the same
distribution.  If your number is bigger than mine ($y_1 > z$), then
the game ends.  Otherwise, if our numbers are equal or mine is bigger
($z \geq y_1$), then you pick a new number $y_2$ with the same
distribution, and keep picking values $y_3$, $y_4$, etc. until you get
a value that is strictly bigger than my number, $z$.  What is the
expected number of picks that you must make?

Certainly, you always need at least one pick, so the expected number
is greater than one.  An answer like 2 or 3 sounds reasonable, though
one might suspect that the answer depends on the distribution.  Let's
find out whether or not this intuition is correct.

\subsection{Analyzing the Game}

The number of picks you must make is a natural-valued random variable.
And, as we've seen, there is a nice formula for the expectation of a
natural-valued random variable:
%
\begin{align}
\expect{\text{\# times you pick}}
    & = \sum_{k=0}^{\infty} \pr{\text{\# times you pick} > k} \label{eqn:1}
\end{align}

Suppose that I've picked my number $z$, and you have picked $k$
numbers $y_1, y_2, \dots, y_k$.  There are two possibilities:
%
\begin{itemize}

\item If there is a unique largest number among our picks, then my
number is as likely to be it as any one of yours.  So with probability
$1/(k+1)$ my number is larger than all of yours, and you must pick
again.

\item Otherwise, there are several numbers tied for largest.  My
number is as likely to be one of these as any of your numbers, so with
probability greater than $1/(k+1)$ you must pick again.

\end{itemize}
%
In both cases, with probability at least $1/(k+1)$, you need more than
$k$ picks to beat me.  In other words:
%
\begin{align}
\pr{\text{\# times you pick} > k} \geq \frac{1}{k+1} \label{eqn:2}
\end{align}

This suggests that in order to minimize your rolls, you should chose a
distribution such that ties are very rare.  For example, you might
choose the uniform distribution on $\set{1, 2, \dots, 10^{100}}$.  In
this case, the probability that you need more than $k$ picks to beat
me is very close to $1/(k+1)$ for moderate values of $k$.  For
example, the probability that you need more than 99 picks is almost
exactly 1\%.  This sounds very promising for you; intuitively, you
might expect to win within a reasonable number of picks on average!

Unfortunately for intuition, there is a simple proof that the expected
number of picks that you need in order to beat me is
\textit{infinite}, regardless of the distribution!  Let's
plug~\eqref{eqn:2} into~\eqref{eqn:1}:
%
\begin{align*}
\expect{\text{\# times you pick}}
    & = \sum_{k=0}^{\infty} \frac{1}{k+1} \\
    & = \infty
\end{align*}

This phenomenon can cause all sorts of confusion!  For example,
suppose you have a communication network where each packet of data has
a $1/k$ chance of being delayed by $k$ or more steps.  This sounds
good; there is only a 1\% chance of being delayed by 100 or more
steps.  But the \textit{expected} delay for the packet is actually
infinite!

There is a larger point here as well: not every random variable has a
well-defined expectation.  This idea may be disturbing at first, but
remember that an expected value is just a weighted average.  And there
are many sets of numbers that have no conventional average either, such as:
%
\[
\set{1, -2, 3, -4, 5, -6, \dots}
\]
%
Strictly speaking, we should qualify virtually all theorems involving
expectation with phrases such as ``...provided all expectations
exist.''  But we're going to leave that assumption implicit.
Fortunately, random variables without expectations don't arise too
often in practice.
\fi

\section{The Coupon Collector Problem}

Every time I purchase a kid's meal at Taco Bell, I am graciously
presented with a miniature ``Racin' Rocket'' car together with a
launching device which enables me to project my new vehicle across any
tabletop or smooth floor at high velocity.  Truly, my delight knows no
bounds.

There are $n$ different types of Racin' Rocket car (blue, green, red,
gray, etc.).  The type of car awarded to me each day by the kind woman
at the Taco Bell register appears to be selected uniformly and
independently at random.  What is the expected number of kids meals
that I must purchase in order to acquire at least one of each type of
Racin' Rocket car?

The same mathematical question shows up in many guises: for example,
what is the expected number of people you must poll in order to find
at least one person with each possible birthday?  Here, instead of
collecting Racin' Rocket cars, you're collecting birthdays.  The
general question is commonly called the \term{coupon collector
problem} after yet another interpretation.

\subsection{A Solution Using Linearity of Expectation}

Linearity of expectation is somewhat like induction and the pigeonhole
principle; it's a simple idea that can be used in all sorts of
ingenious ways.  For example, we can use linearity of expecatation in
a clever way to solve the coupon collector problem.  Suppose there are
five different types of Racin' Rocket, and I receive this sequence:
%
\begin{center}
blue \quad green \quad green \quad red \quad blue \quad orange \quad blue \quad orange \quad gray
\end{center}
%
Let's partition the sequence into 5 segments:
%
\[
\underbrace{\text{blue}}_{X_0} \quad
\underbrace{\text{green}}_{X_1} \quad
\underbrace{\text{green} \quad \text{red}}_{X_2} \quad
\underbrace{\text{blue} \quad \text{orange}}_{X_3} \quad
\underbrace{\text{blue} \quad \text{orange} \quad \text{gray}}_{X_4}
\]
%
The rule is that a segment ends whenever I get a new kind of car.  For
example, the middle segment ends when I get a red car for the first
time.  In this way, we can break the problem of collecting every type
of car into stages.  Then we can analyze each stage individually and
assemble the results using linearity of expectation.

Let's return to the general case where I'm collecting $n$ Racin'
Rockets.  Let $X_k$ be the length of the $k$-th segment.  The total
number of kid's meals I must purchase to get all $n$ Racin' Rockets is
the sum of the lengths of all these segments:
%
\[
T = X_0 + X_1 + \cdots + X_{n-1}
\]

Now let's focus our attention of the $X_k$, the length of the $k$-th
segment.  At the beginning of segment $k$, I have $k$ different types
of car, and the segment ends when I acquire a new type.  When I own
$k$ types, each kid's meal contains a type that I already have with
probability $k / n$.  Therefore, each meal contains a new type of car
with probability $1 - k / n = (n - k) / n$.  Thus, the expected number
of meals until I get a new kind of car is $n / (n - k)$ by the ``mean
time to failure'' formula that we worked out last time.  So we have:
%
\[
\expect{X_k} = \frac{n}{n - k}
\]

Linearity of expecatation, together with this observation, solves the
coupon collector problem:
%
\begin{align*}
\expect{T}
  & = \expect{X_0 + X_1 + \cdots + X_{n-1}} \\
  & = \expect{X_0} + \expect{X_1} + \cdots + \expect{X_{n-1}} \\
  & = \frac{n}{n - 0} + \frac{n}{n - 1} + \cdots + \frac{n}{3} + \frac{n}{2} + \frac{n}{1} \\
  & = n \paren{\frac{1}{n} + \frac{1}{n-1} + \cdots + \frac{1}{3} + \frac{1}{2} + \frac{1}{1}} \\
  & = n H_n
\end{align*}
%
The summation on the next-to-last line is the $n$-th harmonic sum with
the terms in reverse order.  As you may recall, this sum is denoted
$H_n$ and is approximately $\ln n$.

Let's use this general solution to answer some concrete questions.
For example, the expected number of die rolls required to see every
number from 1 to 6 is:
%
\[
6 H_6 = 14.7 \dots
\]
%
And the expected number of people you must poll to find at least one
person with each possible birthday is:
%
\[
365 H_{365} = 2364.6\dots
\]

\iffalse

Let $A_i$ be the event that coin $i$ comes up heads.
Since the coin is fair, $\pr{A_i} = 1/2$.  Since
there are $N$ coins in all, there are $N$ such events.  By the theorem
in the last section, the expected number of events that occur (the
number of coins that come up heads) is $N(1/2) =
N/2$.

Let's try to solve the same problem the hard way.  In this case,
assume that the coins are fair.  Let the random variable $R$ be the
number of heads.  We want to compute the expected value of $R$.

\begin{eqnarray*}
\expect{R}  & = & \sum_{i=0}^N i \cdot \pr{R = i} \\
        & = & \sum_{i=0}^N i \binom{N}{i} 2^{-N}
\end{eqnarray*}

The first equation follows from the definition of expectation.  In the
second step, we evaluate $\pr{R = i}$.  An outcome of tossing the $N$
coins can be represented by a length $N$ sequence of $H$'s and $T$'s.
An $H$ in position $i$ indicates that the $i$th coin is heads, and a
$T$ indicates that the $i$th coin is tails.  The sample space
consists of all $2^N$ such sequences.  The outcomes are equiprobable,
and so each has probability $2^{-N}$.  The number of outcomes with
exactly $i$ heads is the number of length $N$ sequences with $i$
$H$'s, which is $\binom{N}{i}$.  Therefore, $\pr{R = i} = \binom{N}{i}
2^{-N}$.

The answer from linearity of expectation and from the hard way must be
the same, so we can equate the two results to obtain a neat identity.

\begin{eqnarray*}
\sum_{i=0}^N i \binom{N}{i} 2^{-N} & = & \frac{N}{2} \\
\sum_{i=0}^N i \binom{N}{i} & = & N2^{N-1}
\end{eqnarray*}

In fact, we proved this identity by another method earlier in the
term.  Note that linearity of expectation solves the problem more
easily and that the result is more general, since we do not need to
assume that the coins are independent.  The expected number of
heads is $N/2$, even if some coins are glued together.


We can extend this reasoning to $n$ tosses of a coin with probability $p$
of a head, rather than 1/2.  If we do this, we get the generalized
combinatorial identity:
\begin{eqnarray*}
\sum_{i=0}^N i \binom{N}{i} p^i (1-p)^{N-i} & = & N p
\end{eqnarray*}
Here, the $p^i$ factor gives the probabilities for the heads and the
$(1-p)^{N-i}$ factor gives the probabilities for the tails.  The
right-hand side is the sum of $N$ terms, each giving the probability
of a particular $A_i$, which is $p$.  The total is $N p$.  For
example, consider an ordinary die.  Let $A_1$ be the event that the
value is odd, $A_2$ the event that the value is $1$, $2$, or $3$, and
$A_3$ the event that the value is $4$, $5$, or $6$.  These events are
not mutually independent.  However, the expected number of these
events that occur is still obtainable by adding $\pr{A_1} + \pr{A_2} +
\pr{A_3}$, which yields 3/2.

{\bf Question:} What can we say about the product of expectations?
For example, can we say $\expect{R_1 R_2} = \expect{R_1}
\expect{R_2}$?  Not in general. We will see more of this in just a
little bit.

\fi

\section{Conditional Expectation}

Just like event probabilities, expectations can be conditioned on some
event.

\begin{definition}\label{defcondexp}
We define the \emph{conditional expectation  $\expcond{R}{A}$ of a
random variable $R$ given event $A$}:
\[
\expcond{R}{A} \eqdef \sum_r r \cdot\prcond{R=r}{A}.
\]
\end{definition}
In other words, it is the expected value of the variable $R$ once we skew
the distribution of $R$ to be conditioned on event $A$.
\begin{example}
Let $D$ be the outcome of a roll of a fair die.  What is
$\expcond{D}{D\ge 4}$? 
\[
\sum_{i=1}^6 i \cdot \prcond{D=i}{D \ge 4} 
%= \sum_{i=4}^6 i \cdot 1/3 
= 1\cdot 0 + 2\cdot 0 + 3\cdot 0 + 
  4\cdot\tfrac{1}{3} + 5\cdot\tfrac{1}{3} + 6\cdot\tfrac{1}{3} 
= 5.
\]
\end{example}

%Since $\expcond{R}{A}$ is just an expectation over a different probability
%space, we know 

It is easy to see that the rules for expectation will extend to
conditional expectation.  For example, conditional expectation will also
be linear.

\begin{theorem}\label{condexplin}
For any two random variables $R_1$, $R_2$, constants
$a_1,a_2\in\reals$, and event $A$, 
\[
\expcond{a_1R_1+a_2R_2}{A} = a_1\expcond{R_1}{A} + a_2\expcond{R_2}{A}.
\]
\end{theorem}

A real benefit of conditional expectation is the way it lets us divide
complicated expectation calculations into simpler cases.
\begin{theorem}[Law of Total Expectation] \label{totexp}
If the sample space is the union of the pairwise disjoint events
$A_1,A_2,\dots$, then 
\[
\expect{R} = \sum_i \expcond{R}{A_i} \pr{A_i}.
\]
\end{theorem}

\begin{proof}
  \begin{align*}
    \expect{R} &= \sum_r r \cdot \pr{R=r} & \\
    &= \sum_r r \cdot \sum_i \prcond{R=r}{A_i} \pr{A_i}
            & \text{(Law of Total Probability)}\\
    &= \sum_r \sum_i r \cdot \prcond{R=r}{A_i} \pr{A_i}
              & \text{(distribute constant $r$)}\\
    &= \sum_i \sum_r r \cdot \prcond{R=r}{A_i} \pr{A_i}
              & \text{(exchange order of summation)}\\
    &= \sum_i \pr{A_i} \sum_r r \cdot \prcond{R=r}{A_i}
             & \text{(factor constant $\pr{A_i}$)}\\
    &= \sum_i \pr{A_i} \expcond{R}{A_i}.
             & \text{(Def.~\ref{defcondexp})}
  \end{align*}
\end{proof}

\begin{example}
Half the people in the world are male, half female.  The expected
height of a randomly chosen male is $5'11''$, while the expected
height of a randomly chosen female is $5'5''$.  What is the expected
height of a randomly chosen individual?

Let $H(P)$ be the height of the random person $P$.  The events
$M\eqdef$``$P$ is male'' and $F\eqdef$``$P$ is female'' are a partition of
the sample space.
%(at least for the moment ---though with modern science you never
%know).  
Then
\begin{align*}
\expect{H} &= \expcond{H}{M} \pr{M} + \expcond{H}{F} \pr{F}\\
&= 5'11'' \cdot \frac12 + 5'5'' \cdot \frac12\\
&= 5'8''.
\end{align*}
\end{example}
We will see in the following sections that the Law of Total Expectation
has much more power than one might think.

\section{The Expected Value of a Product}

\subsection{The Product of Independent Expectations}

We have determined that the expectation of a sum is the sum of the
expectations.  The same is not always true for products: in general, the
expectation of a product need \emph{not} equal the product of the
expectations.  But it is true in an important special case, namely, when
the random variables are \emph{independent}.

\begin{lemma}\label{E=Econd}
If $R_1$ and $R_2$ are independent random variables, then
\[
\expcond{R_1}{R_2=a} = \expect{R_1}.
\]
\end{lemma}
The Lemma follows immediately from Definition~\ref{defcondexp} of
conditional expectation and the fact that $\pr{R_1=r} =
\prcond{R_1=r}{R_2=a}$.

\begin{theorem}\label{th:prod}
For any two \emph{independent} random variables $R_1$, $R_2$,
\[
\expect{R_1 \cdot R_2} = \expect{R_1} \cdot \expect{R_2}.
\]
\end{theorem}

\begin{proof}
We apply the Law of Total Expectation by conditioning on the value
of~$R_1$.
\begin{align*}
\expect{R_1 \cdot R_2} & = \sum_{r \in \range{R_1}} \expcond{R_1 \cdot
           R_2}{R_1 = r} \cdot \pr{R_1 = r} & \text{(Thm~\ref{totexp})}\\
   & = \sum_{r} \expcond{r \cdot R_2}{R_1 = r} \cdot \pr{R_1 = r}\\
   & = \sum_{r} r \cdot \expcond{R_2}{R_1 = r} \cdot \pr{R_1 = r}
                 & \text{(Lemma~\ref{constexp})}\\
   & = \sum_{r} r \cdot \expect{R_2} \cdot \pr{R_1 = r}
                     & \text{Lemma~\ref{E=Econd}}\\
   & = \expect{R_2} \sum_{r} r \cdot \pr{R_1 = r}
              & \text{(factor out constant $\expect{R_2}$)}\\
  & = \expect{R_2} \cdot \expect{R_1}. & 
\end{align*}
\end{proof}

Theorem~\ref{th:prod} extends routinely to a collection of mutually
independent variables.
\begin{corollary}
If random variables $R_1, R_2, \dots, R_k$ are mutually
independent, then
\[
\expect{\prod_{i=1}^k R_i} = \prod_{i=1}^k \expect{R_i}.
\]
\end{corollary}

%We omit the simple proof by induction on $k$.

\subsection{The Product of Two Dice}

Suppose we throw two \emph{independent}, fair dice and multiply the
numbers that come up.  What is the expected value of this product?

Let random variables $R_1$ and $R_2$ be the numbers shown on the two
dice.  We can compute the expected value of the product as follows:
\begin{equation}\label{R1R2}
  \expect{R_1 \cdot R_2}
  = \expect{R_1} \cdot \expect{R_2}
  = 3.5 \cdot 3.5
  = 12.25.
\end{equation}
Here the first equality holds by Theorem~\ref{th:prod} because the dice
are independent.

Now suppose that the two dice are \emph{not} independent; in fact, assume
that the second die is always the same as the first.  In this case, the
product of expectations will not equal the expectation of the product.

To verify this, let random variables $R_1$ and $R_2$ be the numbers shown
on the two dice.  We can compute the expected value of the product without
Theorem~\ref{th:prod} as follows:
\begin{align*}
\expect{R_1 \cdot R_2} & = \expect{R_1^2} & (R_2 = R_1)\\
        & =    \sum_{i=1}^6 i^2 \cdot \pr{R_{1}^2 = i^2}
                    &  \\
        & =    \sum_{i=1}^6 i^2 \cdot \pr{R_{1} = i}\\
        & =    \frac{1^2}{6} + \frac{2^2}{6} + \frac{3^2}{6} + 
                \frac{4^2}{6} + \frac{5^2}{6} + \frac{6^2}{6} \\
        & =    \frac{91}{6} \\ %15\; \frac{1}{6}\\
        & \neq  12.25 \\ %12 \; \frac{1}{4}\\
        & = \expect{R_1} \cdot \expect{R_2}. & \text{from (\ref{R1R2})}
\end{align*}


\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.  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
\emph{intelligence quotient}, \IQ.  \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, \dots 6$.  The mean, or expected
  value, is 3.5.  Of course, this random variable never takes on
  exactly the expected value; in fact, the outcome deviates from the
  mean by at least 0.5 with probability 1.  Furthermore, there is a
  $\frac{2}{3}$ probability that the outcome deviates from the mean by
  at least 1.5 (roll 1, 2, 5, or 6), a $\frac{1}{3}$ probability that
  the outcome deviates by at least 2.5 (roll 1 or 6), and zero
  probability that the outcome deviates by more than 2.5.
\end{example}

\begin{example}
  A random variable with the binomial distribution is much less likely
  to deviate far from the mean.  For example, suppose we flip 100
  fair, mutually independent coins and count the number of heads.  The
  expected number of heads is 50.  There is an 8\% chance that the
  outcome is exactly the mean, and the probability of flipping more
  than 75 heads or fewer than 25 is less than 1 in a billion.
\end{example}

The probability distribution functions for the two preceding examples
are graphed in Figure~\ref{fig:uniform} and Figure~\ref{fig:binom2}.
There is a big difference!  For the uniform distribution, the graph is
flat; that is, outcomes far from the mean are as likely as outcomes
close to the mean.  However, the binomial distribution has a peak
centered on the expected value and the tails fall off rapidly.  This
shape implies that outcomes close to the expected value are vastly
more likely than outcomes far from the expected value.  In other
words, a random variable with the binomial distribution rarely
deviates far from the mean.
\begin{figure}
  \centerline{\includegraphics[height=2in]{figures/uniform}}
  \caption{This is a graph of the uniform distribution arising from
    rolling a fair die.  Outcomes within the range of the distribution
    are equally likely, regardless of distance from the mean.}
  \label{fig:uniform}
\end{figure}
\begin{figure}
  \centerline{\includegraphics[height=2in]{figures/binom2}}
  \caption{This is a rough graph of the binomial distribution given by
    the number of heads that come up when we flip 100 fair, mutually
    independent coins.  Outcomes close to the mean are much more
    likely than outcomes far from the mean.}
  \label{fig:binom2}
\end{figure}

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

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


\subsection{Theorem Statement and Some Applications}
\fi

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

\iffalse

Before we prove Markov's Theorem, let's apply it to the three examples in
the preceding subsection.  First, let the random variable~$R$ be the
number that comes up when we roll a fair die.  By Markov's Theorem, the
probability of rolling a 6 is at most:
\[
\pr{R \geq 6} \leq \frac{\expect{R}}{6} = \frac{3.5}{6} = 0.583\dots
\]
This conclusion is true, but weak.  The actual probability of rolling
a 6 is $1/6 = 0.166\dots$.

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

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

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

\subsection{Proof of Markov's Theorem}

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

There is insufficient information for an exact answer.  However, we
can safely say that the probability that $R \geq 200$ is most
$1/2$.  If more than half of the people weigh 200 pounds or
more, then the average weight would exceed 100 pounds, even if
everyone else weighed zero!  Markov's Theorem gives the same result:
\begin{displaymath}
  \pr{R \geq 200} \leq \frac{\expect{R}}{200} = \frac{100}{200} = \frac{1}{2}.
\end{displaymath}

Reasoning similar to that above underlies the proof of Markov's
Theorem.  Since expectation is a weighted average of all the outcomes
of the random variable, that is, a sum over all the variables the random
variable can assume, we can give a lower bound on the expectation by
removing some of the terms from the sum defining the expectation; this
new sum can then be modified into an expression involving the
probability of an event in the tail $[R \geq x]$.
\fi

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

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

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


\subsection{Examples of Markov's Theorem}

Suppose that $n$ men go to a dinner party and check their hats.  At the
end of the night, the hats are randomly permuted and returned, so each man
gets 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$.  
You can show that $\expect{R} = 1$ (right?).
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{Markov's Theorem for Bounded Variables}

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

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

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

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

\iffalse

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

\fi


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

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

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

\subsection{Deviation Below the Mean}

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

\begin{theorem}
\label{th:below}
Let $l$ be a real number and let $R$ be a random variable such that $R
\leq l$.  For all $x < l$, we have:
\[
\pr{R \leq x} \leq \frac{l - \expect{R}}{l - x}.
\]
\end{theorem}

\begin{proof}
The event that $R \leq x$ is the same as the event that $l - R \geq l -
x$.  Therefore:
\begin{align}
\pr{R \leq x} &  = \pr{l - R \geq l - x}\notag\\
 & \leq \frac{\expect{l - R}}{l - x}. & \text{(by Markov' Theorem)}\label{LR}
\end{align}
Applying Markov's Theorem in line~(\ref{LR}) is permissible
since $l - R$ is a nonnegative random variable and $l - x > 0$.
\end{proof}

For example, suppose that the class average on the 6.042 midterm was
75/100.  What fraction of the class scored below 50?

There is not enough information here to answer the question exactly,
but Theorem~\ref{th:below} gives an upper bound.  Let $R$ be the score
of a random student.  Since 100 is the highest possible score, we
can set $L = 100$ to meet the condition in the theorem that $R \leq
L$.  Applying Theorem~\ref{th:below}, we find:
\begin{displaymath}
  \pr{R \leq 50} \leq \frac{100 - 75}{100 - 50} = \frac{1}{2}\,.
\end{displaymath}

That is, at most half of the class scored 50 or worse.  This makes
sense; if more than half of the class scored 50 or worse, then the
class average could not be 75, even if everyone else scored 100.
As with Markov's Theorem, Theorem~\ref{th:below} often gives weak
results.  In fact, based on the data given, the entire class could
have scored above 50.
\fi

\iffalse

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

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

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

\end{optional}
\fi

\section{Chebyshev's Theorem}

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

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

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

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

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

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

The expression $\expect{(R - \expect{R})^2}$ for variance is a bit
cryptic; the best approach is to work through it from the inside out.  The
innermost expression, $R - \expect{R}$, is precisely the deviation of $R$
above its mean.  Squaring this, we obtain, $(R - \expect{R})^2$.  This is
a random variable that is near 0 when $R$ is close to the mean and is a
large positive number when $R$ deviates far above or below the mean.  So
if $R$ is always close to the mean, then the variance will be small.  If
$R$ is often far from the mean, then the variance will be large.

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

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

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


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

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

\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 $\pr{R =
\expect{R}} = 1$.
\end{lemma}

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

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

\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~\eqref{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}, essentially only holds
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, \dots, R_n$ are \emph{pairwise} independent random
variables, then
\[
\variance{R_1 + R_2 + \cdots + 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 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}

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

%\subsection{Applying Chebyshev's Theorem}

\section{Estimation by Random Sampling}

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

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

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

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

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

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

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

\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 is it likely the number of
matching pairs in a typical class will actually be close to the expected
number?  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, namely,
these two events really are independent.  So even though the events that
various pairs of students have matching birthdays are not mutually
independent, indeed not even three-way independent, they are
\emph{pairwise} independent.

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

This 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
$n$ independently chosen people, and let $E_{i,j}$ be the indicator
variable for the event that the $i$th and $j$th people chosen have the
same birthdays, that is, the event $[B_i = B_j]$.  For simplicity, we'll
assume that for $i\neq j$, the probability\footnote{In the U.S., Fall
birthdays are more common than Winter birthdays, so $\pr{B_i=B_j}$ is
actually a bit larger than $1/365$.} that $B_i = B_j$ is 1/365.  So the
$B_i$'s are mutually independent variables, and hence the $E_{i,j}$'s are
\emph{pairwise} independent variables, which is all we will need.

Let $M_n$ be the number of matching pairs of birthdays among the $n$
choices, that is,
\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}\cdot \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} \cdot \frac{1}{365}\paren{1-\frac{1}{365}}.
\]

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

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

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

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

\section{Pairwise Independent Sampling}

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

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

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

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

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

\end{proof}

The Pairwise Independent Sampling Theorem provides a precise general
statement about how the average of independent samples of a random
variable approaches the mean.  In particular, it shows that by choosing a
large enough sample size, $n$, we can get arbitrarily accurate estimates
of the mean with confidence arbitrarily close to 100\%.

\end{document}
