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

\newcommand{\beqn}{\begin{eqnarray*}}
\newcommand{\eeqn}{\end{eqnarray*}}

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

\begin{document}
\lecturenotes{13}{Random Variables, Distributions and Expectation}

\section{Random Variables}

We've used probablity to model a variety of experiments, games, and tests.
Throughout, we have tried to compute probabilities of \term{events}.  We
asked, for example, what is the probability of the event that you win the
Monty Hall game?  What is the probability of the event that it rains,
given that the weatherman carried his umbrella today?  What is the
probability of the event that you have a rare disease, given that you
tested positive?

But one can ask more general questions about an experiment.  {\em How
hard} will it rain?  {\em How long} will this illness last?  {\em How
much} will I lose playing 6.042 games all day?  These questions are
fundamentally different and not easily phrased in terms of events.
The problem is that an event either does or does not happen: you win
or lose, it rains or doesn't, you're sick or not.  But these questions
are about matters of degree: how much, how hard, how long?  To
approach these questions, we need a new mathematical tool.

\subsection{Definition}

Let's begin with an example.  Consider the experiment of tossing three
independent, unbiased coins.  Let $C$ be the number of heads that
appear.  Let $M = 1$ if the three coins come up all heads or all
tails, and let $M = 0$ otherwise.  Now every outcome of the three coin
flips uniquely determines the values of $C$ and $M$.  For example, if
we flip heads, tails, heads, then $C = 2$ and $M = 0$.  If we flip
tails, tails, tails, then $C = 0$ and $M = 1$.  In effect, $C$ counts
the number of heads, and $M$ indicates whether all the coins match.

Since each outcome uniquely determines $C$ and $M$, we can regard them
as functions mapping outcomes to numbers.  For this experiment, the
sample space is:
\beqn
\sspace & = & \set{ HHH, HHT, HTH, HTT, THH, THT, TTH, TTT }.
\eeqn
Now $C$ is a function that maps each outcome in the sample space to a 
number as follows:
\[
\begin{array}{rclcrcl}
C(HHH) & = & 3 & \quad & C(THH) & = & 2 \\
C(HHT) & = & 2 & \quad & C(THT) & = & 1 \\
C(HTH) & = & 2 & \quad & C(TTH) & = & 1 \\
C(HTT) & = & 1 & \quad & C(TTT) & = & 0.
\end{array}
\]
Similarly, $M$ is a function mapping each outcome another way:
\[
\begin{array}{rclcrcl}
M(HHH) & = & 1 & \quad & M(THH) & = & 0 \\
M(HHT) & = & 0 & \quad & M(THT) & = & 0 \\
M(HTH) & = & 0 & \quad & M(TTH) & = & 0 \\
M(HTT) & = & 0 & \quad & M(TTT) & = & 1.
\end{array}
\]
The functions $C$ and $M$ are examples of \term{random variables}.  In
general, a random variable is a function whose domain is the sample
space.  (The codomain can be anything, but we'll usually use a subset
of the real numbers.)  Notice that the name ``random variable'' is a
misnomer; random variables are actually functions!


\subsection{Indicator Random Variables}

An \term{indicator random variable} (or simply an \term{indicator}, or
a \term{Bernoulli random variable}) is a random variable that maps
every outcome to either 0 or 1.  The random variable $M$ is an
example.  If all three coins match, then $M=1$; otherwise, $M = 0$.

Indicator random variables are closely related to events.  In
particular, an indicator partitions the sample space into those
outcomes mapped to 1 and those outcomes mapped to 0.  For example, the
indicator $M$ partitions the sample space into two blocks as follows:
\[
\underbrace{HHH \quad TTT}_{\text{$M = 1$}} \quad
\underbrace{HHT \quad HTH \quad HTT \quad
        THH \quad THT \quad TTH}_{\text{$M = 0$}}.
\]
In the same way, an event partitions the sample space into
those outcomes in the event and those outcomes not in the event.
Therefore, each event is naturally associated with a certain indicator
random variable and vice versa: an \term{indicator for an event $E$}
is an indicator random variable that is 1 for all outcomes in $E$ and
$0$ for all outcomes not in $E$.  Thus, $M$ is an indicator random
variable for the event that all three coins match.

\subsection{Random Variables and Events}

There is a strong relationship between events and more general random
variables as well.  A random variable that takes on several values
partitions the sample space into several blocks.  For example, $C$
partitions the sample space as follows:
\[
\underbrace{TTT}_{\text{$C = 0$}} \quad
\underbrace{TTH \quad THT \quad HTT}_{\text{$C = 1$}} \quad
\underbrace{THH \quad HTH \quad HHT}_{\text{$C = 2$}} \quad
\underbrace{HHH}_{\text{$C = 3$}}.
\]
Each block is a subset of the sample space and is therefore
an event.  Thus, we can regard an equation or inequality involving a
random variable as an event.  For example, the event that $C = 2$
consists of the outcomes $THH$, $HTH$, and $HHT$.  The event $C \leq
1$ consists of the outcomes $TTT$, $TTH$, $THT$, and $HTT$.

Naturally enough, we can talk about the probability of events defined
by equations involving random variables.  For example:
\beqn
\pr{C = 2}
        & = &   \pr{THH} + \pr{HTH} + \pr{HHT} \\
        & = &   \frac{1}{8} + \frac{1}{8} + \frac{1}{8} \\
        & = &   \frac{3}{8}.
\eeqn
As another example:
\beqn
\pr{M = 1}
        & = &   \pr{TTT} + \pr{HHH}\\
        & = &   \frac{1}{8} + \frac{1}{8} \\
        & = &   \frac{1}{4}.
\eeqn

\subsection{Conditional Probability}

Mixing conditional probabilities and events involving random variables
creates no new difficulties.  For example, $\prcond{C \geq 2}{M = 0}$
is the probability that at least two coins are heads ($C \geq 2$),
given that not all three coins are the same ($M = 0$).  We can compute
this probability using the definition of conditional probability:
\begin{eqnarray*}
\prcond{C \geq 2}{M = 0}
        & = &   \frac{\pr{[C \geq 2] \cap [M = 0]}}{\pr{M = 0}} \\
        & = &   \frac{\pr{\set{THH, HTH, HHT}}}
                        {\pr{\set{THH, HTH, HHT, HTT, THT, TTH }}} \\
        & = &   \frac{3/8}{6/8} \\
        & = &   \frac{1}{2}.
\end{eqnarray*}
The expression $[C \geq 2] \cap [M = 0]$ on the first line may look odd;
what is the set operation $\cap$ doing between an inequality and an
equality?  But recall that, in this context, $[C \geq 2]$ and $[M = 0]$
are \emph{events}, namely, \emph{sets} of outcomes.

\subsection{Independence}

The notion of independence carries over from events to random
variables as well.  Random variables $R_1$ and $R_2$ are
\term{independent} if for all $x_1$ in the codomain
of $R_1$, and $x_2$  in the codomain of $R_2$, we have:
\[
\pr{[R_1 = x_1] \cap [R_2 = x_2]}  =  \pr{R_1 = x_1} \cdot \pr{R_2 = x_2}.
\]
As with events, we can formulate independence for random
variables in an equivalent and perhaps more intuitive way: random
variables $R_1$ and $R_2$ are independent if for all $x_1$ and $x_2$
in the codomains of $R_1$ and $R_2$ respectively,
such that $\pr{R_2 = x_2} > 0$, we have:
\[
\prcond{R_1 = x_1}{R_2 = x_2}  =  \pr{R_1 = x_1}.
\]
In words: the probability that $R_1$ takes on a particular
value is unaffected by the value of $R_2$.

As an example, are $C$ and $M$ independent?  Intuitively, the answer
should be ``no''.  The number of heads, $C$, completely determines
whether all three coins match; that is, whether $M = 1$.  But, to
verify this intuition, we must find some $x_1, x_2 \in \reals$
such that:
\beqn
\pr{[C = x_1] \cap [M = x_2}] & \neq & \pr{C = x_1} \cdot \pr{M = x_2}.
\eeqn
One appropriate choice of values is $x_1 = 2$ and $x_2 = 1$.
In this case, we have:
\[
\begin{array}{ccc}
\pr{[C = 2] \cap [M = 1]} = 0
& \text{ but } &
\pr{C = 2} \cdot \pr{M = 1} = \dfrac{3}{8} \cdot \dfrac{1}{4} \neq 0.
\end{array}
\]
The first probability is zero because we never have exactly
two heads ($C = 2$) when all three coins match ($M = 1$).  The other
two probabilities were computed earlier.

The notion of independence generalizes to a set of random variables as
follows.  Random variables $R_1, R_2, \dots, R_n$ are \term{mutually
independent} if for all $x_1, x_2, \dots, x_n$,
in the codomains of $R_1,R_2,\dots,R_n$ respectively,  we
have:
\begin{eqnarray*}
\lefteqn{\pr{[R_1 = x_1] \cap [R_2 = x_2] \cap \cdots \cap [R_n = x_n]}}
        \hspace{1in} \\
        & = & \pr{R_1 = x_1} \cdot \pr{R_2 = x_2} \cdots \pr{R_n = x_n}.
\end{eqnarray*}
A consequence of this definition of mutual independence is that the
probability that any {\em subset} of the variables takes a particular set
of values is equal to the product of the probabilites that the individual
variables take their values.  Thus, for example, if $R_1, R_2, \dots,
R_{100}$ are mutually independent random variables, then it follows that:
\begin{eqnarray*}
\pr{[R_1 = 7] \cap [R_7 = 9.1] \cap [R_{23} = \pi]}
        & = &   \pr{R_1 = 7} \cdot \pr{R_7 = 9.1} \cdot \pr{R_{23} = \pi}.
\end{eqnarray*}


\section{The Birthday Principle}

There are 100 students in a lecture hall.
What is the probability that some two people share a
birthday?  Maybe about $1/3$?  Let's check!  We'll use the following
two variables throughout our analysis:

\begin{itemize}

\item Let $n$ be the number of people in the group.

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

\end{itemize}

Furthermore, we'll make the assumption that birthdays are
uniformly-distributed, independent random variables.  This assumption
is not really valid in the real world, since more babies are born at
certain times of year and the birthdays of twins are clearly not
independent.  However, our analysis of this problem applies to many
situations in computer science that are unaffected by twins, leap
days, and romantic holidays anyway, so we won't dwell on those
complications.

The sample space for this experiment consists of all ways of assigning
birthdays to the people of the group.  There are $d^n$ such
assignments, since the first person can have $d$ different birthdays,
the second person can have $d$ different birthdays, and so forth.
Furthermore, every such assignment is equally probable by our
assumption that birthdays are uniformly-distributed and mutually
independent, so the sample space is uniform.

Let $D$ be the event that everyone has a distinct birthday.  This is
the complement of the event that we're interested in, but the
probability of $D$ is easier to evaluate.  Later we can use the fact
that $\pr{\overline{D}} = 1 - \pr{D}$ to compute the probability we
really want.  Anyway, event $D$ consists of $d (d - 1) (d - 2) \cdots
(d - n + 1)$ outcomes, since we can select the birthday of the first
person in $d$ days, the birthday of the second person in $d - 1$ ways,
and so forth.  Therefore, the probability that everyone has a
different birthday is:
\begin{align*}
\pr{D} & = \frac{d (d - 1) (d - 2) \cdots (d - n + 1)}{d^n}.
\end{align*}
For $n=100$, this probability is actually fantastically small ---less
than one in a million!  If there are 100 people in a room, two are
almost certain to share a birthday.

Let's use an approximation to rewrite the right side of the preceding
equation in a more insightful form:
\begin{align*}
\pr{D} & = \left(1 - \frac{0}{d}\right)
           \left(1 - \frac{1}{d}\right)
           \left(1 - \frac{2}{d}\right) 
           \cdots
           \left(1 - \frac{n - 1}{d}\right) \\
       & \approx e^0 \cdot e^{-1/d} \cdot e^{-2/d} \cdots e^{-(n-1)/d} \\
       & = e^{\frac{-n(n-1)}{2d}}.
\end{align*}
In the first step, we pair each term in the numerator with a $d$ term
in the denominator.  Next, we use the approximation $e^{-x} \approx 1
- x$, which is pretty accurate when $x$ is small.\footnote{This
approximation is obtained by truncating the Taylor series $e^{-x} = 1
- x + x^2/2! - x^3/3! + \cdots$} In the last step, we combine
exponents using the familiar formula $0 + 1 + 2 + \cdots + (n - 1) = n
(n - 1) / 2$.

The exponent in the final expression above is $-1$ when $n \approx
\sqrt{2d}$.  This is roughly the break-even point, where the
probability that two people share a birthday is in the ballpark of
$1/2$.  This leads to a rule called the \term{birthday principle},
which is useful in many contexts in computer science:
\begin{quote}
If there are $d$ days in a year and $\sqrt{2d}$ people in a
room, then the probability that two share a birthday is about 
$1 - 1/e \approx 0.632$.
\end{quote}
For example, this principle says that if you have $\sqrt{2 \cdot 365}
\approx 27$ people in a room, then the probability that two share a
birthday is about $0.632$.  The actual probability is about $0.626$,
so the approximation is quite good.

The Birthday Principle is a great rule of thumb with surprisingly many
applications.  For example, cryptographic systems and digital
signature schemes must be hardened against ``birthday attacks''.  The
principle also tells us how many items can be inserted into a
hash table before one starts to experience collisions.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Probability Distributions}

A random variable is defined to be a function whose domain is the
sample space of an experiment.  Often, however, random variables with
essentially the same properties show up in completely different
experiments.  For example, some random variable that come up in
polling, in primality testing, and in coin flipping all share some
common properties.  If we could study such random variables in the
abstract, divorced from the details any particular experiment, then
our conclusions would apply to \textit{all} the experiments where that
sort of random variable turned up.  Such general conclusions could be
very useful.  There are a couple tools that capture the essential
properties of a random variable, but leave other details of the
associated experiment behind.

The \term{probability density function (pdf)} for a random variable
$R$ with codomain $V$ is a function $\pdf_R : V \to [0,1]$ defined by:
%
\[
\pdf_R(x) = \pr{R = x}
\]
%
A consequence of this definition is that
%
\[
\sum_{x \in V} \pdf_R(x) = 1
\]
%
since the random variable always takes on exactly one value in the set
$V$.

As an example, let's return to the experiment of rolling two fair,
independent dice.  As before, let $T$ be the total of the two rolls.
This random variable takes on values in the set $V = \set{2, 3,
\dots, 12}$.  A plot of the probability density function is shown
below:
%
\begin{center}
\begin{picture}(305,110)(-75,-40)
%\put(-75,-40){\dashbox(305,110)} % bounding box
\put(0,0){\vector(1,0){230}}
\put(0,0){\vector(0,1){70}}
\put(-1,60){\line(1,0){2}}
\put(-15,60){\makebox(0,0){{\small $6/36$}}}
\put(-1,30){\line(1,0){2}}
\put(-15,30){\makebox(0,0){{\small $3/36$}}}
\put(-50,40){\makebox(0,0){$\pdf_R(x)$}}
\put(120,-30){\makebox(0,0){$x \in V$}}
\put(0,0){\framebox(20,10){}}
\put(10,-10){\makebox(0,0){2}}
\put(20,0){\framebox(20,20){}}
\put(30,-10){\makebox(0,0){3}}
\put(40,0){\framebox(20,30){}}
\put(50,-10){\makebox(0,0){4}}
\put(60,0){\framebox(20,40){}}
\put(70,-10){\makebox(0,0){5}}
\put(80,0){\framebox(20,50){}}
\put(90,-10){\makebox(0,0){6}}
\put(100,0){\framebox(20,60){}}
\put(110,-10){\makebox(0,0){7}}
\put(120,0){\framebox(20,50){}}
\put(130,-10){\makebox(0,0){8}}
\put(140,0){\framebox(20,40){}}
\put(150,-10){\makebox(0,0){9}}
\put(160,0){\framebox(20,30){}}
\put(170,-10){\makebox(0,0){10}}
\put(180,0){\framebox(20,20){}}
\put(190,-10){\makebox(0,0){11}}
\put(200,0){\framebox(20,10){}}
\put(210,-10){\makebox(0,0){12}}
\end{picture}
\end{center}
%
The lump in the middle indicates that sums close to 7 are the most
likely.  The total area of all the rectangles is 1 since the dice must
take on exactly one of the sums in $V = \set{2, 3, \dots, 12}$.

A closely-related idea is the \term{cumulative distribution function
(cdf)} for a random variable $R$.  This is a function $\cdf_R : V \to
[0,1]$ defined by:
%
\[
\cdf_R(x) = \pr{R \leq x}
\]
%
As an example, the cumulative distribution function for the random
variable $T$ is shown below:
%
\begin{center}
\begin{picture}(305,155)(-75,-40)
%\put(-75,-40){\dashbox(305,155)} % bounding box
\put(0,0){\vector(1,0){230}}
\put(0,0){\vector(0,1){115}}
\put(-1,108){\line(1,0){2}}
\put(-15,108){\makebox(0,0){{\small $1$}}}
\put(-1,54){\line(1,0){2}}
\put(-15,54){\makebox(0,0){{\small $1/2$}}}
\put(-15,0){\makebox(0,0){{\small $0$}}}
\put(-50,81){\makebox(0,0){$\cdf_R(x)$}}
\put(120,-30){\makebox(0,0){$x \in V$}}
\put(0,0){\framebox(20,3){}}
\put(10,-10){\makebox(0,0){2}}
\put(20,0){\framebox(20,9){}}
\put(30,-10){\makebox(0,0){3}}
\put(40,0){\framebox(20,18){}}
\put(50,-10){\makebox(0,0){4}}
\put(60,0){\framebox(20,30){}}
\put(70,-10){\makebox(0,0){5}}
\put(80,0){\framebox(20,45){}}
\put(90,-10){\makebox(0,0){6}}
\put(100,0){\framebox(20,63){}}
\put(110,-10){\makebox(0,0){7}}
\put(120,0){\framebox(20,78){}}
\put(130,-10){\makebox(0,0){8}}
\put(140,0){\framebox(20,90){}}
\put(150,-10){\makebox(0,0){9}}
\put(160,0){\framebox(20,99){}}
\put(170,-10){\makebox(0,0){10}}
\put(180,0){\framebox(20,105){}}
\put(190,-10){\makebox(0,0){11}}
\put(200,0){\framebox(20,108){}}
\put(210,-10){\makebox(0,0){12}}
\end{picture}
\end{center}
%
The height of the $i$-th bar in the cumulative distribution function
is equal to the \textit{sum} of the heights of the leftmost $i$ bars
in the probability density function.  This follows from the
definitions of pdf and cdf:
%
\begin{align*}
\cdf_R(x) & = \pr{R \leq x} \\
          & = \sum_{y \leq x} \pr{R = y} \\
          & = \sum_{y \leq x} \pdf_R(y)
\end{align*}

In summary, $\pdf_R(x)$ measures the probability that $R = x$ and
$\cdf_R(x)$ measures the probability that $R \leq x$.  Both the
$\pdf_R$ and $\cdf_R$ capture the same information about the random
variable $R$--- you can derive one from the other--- but sometimes one
is more convenient.  The key point here is that neither the
probability density function nor the cumulative distribution function
involves the sample space of an experiment.  Thus, through these
functions, we can study random variables without reference to a
particular experiment.

We'll now look at three important
distributions and some applications.

\subsection{Bernoulli Distribution}

Indicator random variables are perhaps the most common type because of
their close association with events.  The probability density function
of an indicator random variable $B$ is always
%
\begin{align*}
\pdf_B(0) & = p \\
\pdf_B(1) & = 1 - p \\
\end{align*}
%
where $0 \leq p \leq 1$.  The corresponding cumulative distribution
function is:
%
\begin{align*}
\cdf_B(0) & = p \\
\cdf_B(1) & = 1
\end{align*}
%
%This is called the \term{Bernoulli distribution}. 
%The number of heads
%flipped on a (possibly biased) coin has a Bernoulli distribution.

\subsection{Uniform Distribution}

A random variable that takes on each possible value with the same
probability is called \term{uniform}.  For example, the probability
density function of a random variable $U$ that is uniform on the set
$\set{1, 2, \dots, N}$ is:
%
\begin{align*}
\pdf_U(k) = \frac{1}{N}
\end{align*}
%
And the cumulative distribution function is:
%
\begin{align*}
\cdf_U(k) = \frac{k}{N}
\end{align*}
%
Uniform distributions come up all the time.  For example, the number
rolled on a fair die is uniform on the set $\set{1, 2, \dots, 6}$.

\subsection{The Numbers Game}

Let's play a game!  I have two envelopes.  Each contains an integer in
the range $0, 1, \dots, 100$, and the numbers are distinct.  To win
the game, you must determine which envelope contains the larger
number.  To give you a fighting chance, I'll let you peek at the
number in one envelope selected at random.  Can you devise a strategy
that gives you a better than 50\% chance of winning?

For example, you could just pick an evelope at random and guess that
it contains the larger number.  But this strategy wins only 50\% of
the time.  Your challenge is to do better.

So you might try to be more clever.  Suppose you peek in the left
envelope and see the number 12.  Since 12 is a small number, you might
guess that that other number is larger.  But perhaps I'm sort of
tricky and put small numbers in \textit{both} envelopes.  Then your
guess might not be so good!

An important point here is that the numbers in the envelopes may
\textit{not} be random.  I'm picking the numbers and I'm choosing them
in a way that I think will defeat your guessing strategy.  I'll only
use randomization to choose the numbers if that serves \textit{my}
end:  making you lose!

\subsubsection{Intuition Behind the Winning Strategy}

Amazingly, there is a strategy that wins more than 50\% of the time,
regardless of what numbers I put in the envelopes!

Suppose that you somehow knew a number $x$ \textit{between} my lower
number and higher numbers.  Now you peek in an envelope and see one or
the other.  If it is bigger than $x$, then you know you're peeking at
the higher number.  If it is smaller than $x$, then you're peeking at
the lower number.  In other words, if you know an number $x$ between
my lower and higher numbers, then you are certain to win the game.

The only flaw with this brilliant strategy is that you do \textit{not}
know $x$.  Oh well.

But what if you try to \textit{guess} $x$?  There is some probability
that you guess correctly.  In this case, you win 100\% of the time.
On the other hand, if you guess incorrectly, then you're no worse off
than before; your chance of winning is still 50\%.  Combining these
two cases, your overall chance of winning is better than 50\%!

Informal arguments about probability, like this one, often sound
plausible, but do not hold up under close scrutiny.  In contrast, this
argument sounds completely implausible--- but is actually correct!

\subsubsection{Analysis of the Winning Strategy}

For generality, suppose that I can choose numbers from the set
$\set{0, 1, \dots, n}$.  Call the lower number $L$ and the higher
number $H$.

Your goal is to guess a number $x$ between $L$ and $H$.  To avoid
confusing equality cases, you select $x$ at random from among the
half-integers:
%
\[
\set{\frac{1}{2},\ 1\frac{1}{2},\ 2\frac{1}{2},\ \dots,\ n - \frac{1}{2}}
\]
%
But what probability distribution should you use?

The uniform distribution turns out to be your best bet.  An informal
justification is that if I figured out that you were unlikely to pick
some number--- say $50\frac{1}{2}$--- then I'd always put 50 and 51 in
the evelopes.  Then you'd be unlikely to pick an $x$ between $L$ and
$H$ and would have less chance of winning.

After you've selected the number $x$, you peek into an envelope and
see some number $p$.  If $p > x$, then you guess that you're looking
at the larger number.  If $p < x$, then you guess that the other
number is larger.

All that remains is to determine the probability that this strategy
succeeds.  We can do this with the usual four-step method and a tree
diagram.

\noindent \textbf{Step 1: Find the sample space. }  You either choose
$x$ too low ($< L$), too high ($> H$), or just right ($L < x < H$).
Then you either peek at the lower number ($p = L$) or the higher
number ($p = H$).  This gives a total of six possible outcomes.
%
\begin{center}
\includegraphics[height=2.5in]{figures/numbers-game}
\end{center}

\noindent \textbf{Step 2: Define events of interest. } The four
outcomes in the event that you win are marked in the tree diagram.

\noindent \textbf{Step 3: Assign outcome probabilities. } First, we
assign edge probabilities.  Your guess $x$ is too low with probability
$L/n$, too high with probability $(n-H)/n$, and just right with
probability $(H-L)/n$.  Next, you peek at either the lower or higher
number with equal probability.  Multiplying along root-to-leaf paths
gives the outcome probabilities.

\noindent \textbf{Step 4: Compute event probabilities. }  The
probability of the event that you win is the sum of the probabilities
of the four outcomes in that event:
%
\begin{align*}
\pr{\text{win}}
    & = \frac{L}{2n} + \frac{H-L}{2n} + \frac{H-L}{2n}  + \frac{n-H}{2n} \\
    & = \frac{1}{2} + \frac{H-L}{2n} \\
    & \geq \frac{1}{2} + \frac{1}{2n}
\end{align*}
%
The final inequality relies on the fact that the higher number $H$ is
at least 1 greater than the lower number $L$ since they are required
to be distinct.

Sure enough, you win with this strategy more than half the time,
regardless of the numbers in the envelopes!  For example, if I choose
numbers in the range $0, 1, \dots, 100$, then you win with probability at
least $\frac{1}{2} + \frac{1}{200} = 50.5\%$.  Even better, if I'm allowed
only numbers in the range $0, \dots, 10$, then your probability of
winning rises to 55\%!  By Las Vegas standards, those are great odds!

\subsection{Binomial Distribution}

Of the more complex distributions, the \term{binomial distribution} is
surely the most important in computer science.  The standard example
of a random variable with a binomial distribution is the number of
heads that come up in $n$ independent flips of a coin; call this
random variable $H$.  If the coin is fair, then $H$ has an
\textit{unbiased binomial density function}:
%
\[
\pdf_H(k) = \binom{n}{k} 2^{-n}
\]
%
This follows because there are $\binom{n}{k}$ sequences of $n$ coin
tosses with exactly $k$ heads, and each such sequence has probability
$2^{-n}$.

Here is a plot of the unbiased probability density function
$\pdf_H(k)$ corresponding to $n = 20$ coins flips.  The most likely
outcome is $k = 10$ heads, and the probability falls off rapidly for
larger and smaller values of $k$.  These falloff regions to the left
and right of the main hump are usually called the \term{tails of the
distribution}.
%
\begin{center}
% GNUPLOT: LaTeX picture
\setlength{\unitlength}{0.240900pt}
\ifx\plotpoint\undefined\newsavebox{\plotpoint}\fi
\sbox{\plotpoint}{\rule[-0.200pt]{0.400pt}{0.400pt}}%
\begin{picture}(1500,900)(0,0)
\font\gnuplot=cmr10 at 10pt
\gnuplot
\sbox{\plotpoint}{\rule[-0.200pt]{0.400pt}{0.400pt}}%
\put(140.0,82.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(120,82){\makebox(0,0)[r]{0}}
\put(1419.0,82.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(140.0,168.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(120,168){\makebox(0,0)[r]{0.02}}
\put(1419.0,168.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(140.0,255.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(120,255){\makebox(0,0)[r]{0.04}}
\put(1419.0,255.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(140.0,341.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(120,341){\makebox(0,0)[r]{0.06}}
\put(1419.0,341.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(140.0,428.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(120,428){\makebox(0,0)[r]{0.08}}
\put(1419.0,428.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(140.0,514.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(120,514){\makebox(0,0)[r]{0.1}}
\put(1419.0,514.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(140.0,601.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(120,601){\makebox(0,0)[r]{0.12}}
\put(1419.0,601.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(140.0,687.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(120,687){\makebox(0,0)[r]{0.14}}
\put(1419.0,687.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(140.0,774.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(120,774){\makebox(0,0)[r]{0.16}}
\put(1419.0,774.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(140.0,860.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(120,860){\makebox(0,0)[r]{0.18}}
\put(1419.0,860.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(140.0,82.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(140,41){\makebox(0,0){0}}
\put(140.0,840.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(465.0,82.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(465,41){\makebox(0,0){5}}
\put(465.0,840.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(790.0,82.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(790,41){\makebox(0,0){10}}
\put(790.0,840.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(1114.0,82.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(1114,41){\makebox(0,0){15}}
\put(1114.0,840.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(1439.0,82.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(1439,41){\makebox(0,0){20}}
\put(1439.0,840.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(140.0,82.0){\rule[-0.200pt]{312.929pt}{0.400pt}}
\put(1439.0,82.0){\rule[-0.200pt]{0.400pt}{187.420pt}}
\put(140.0,860.0){\rule[-0.200pt]{312.929pt}{0.400pt}}
\put(140.0,82.0){\rule[-0.200pt]{0.400pt}{187.420pt}}
\put(140,82){\usebox{\plotpoint}}
\put(140.0,82.0){\rule[-0.200pt]{25.294pt}{0.400pt}}
\put(245.0,82.0){\usebox{\plotpoint}}
\put(245.0,83.0){\rule[-0.200pt]{15.899pt}{0.400pt}}
\put(311.0,83.0){\rule[-0.200pt]{0.400pt}{0.964pt}}
\put(311.0,87.0){\rule[-0.200pt]{15.658pt}{0.400pt}}
\put(376.0,87.0){\rule[-0.200pt]{0.400pt}{3.613pt}}
\put(376.0,102.0){\rule[-0.200pt]{15.899pt}{0.400pt}}
\put(442.0,102.0){\rule[-0.200pt]{0.400pt}{10.600pt}}
\put(442.0,146.0){\rule[-0.200pt]{15.658pt}{0.400pt}}
\put(507.0,146.0){\rule[-0.200pt]{0.400pt}{23.126pt}}
\put(507.0,242.0){\rule[-0.200pt]{15.899pt}{0.400pt}}
\put(573.0,242.0){\rule[-0.200pt]{0.400pt}{38.544pt}}
\put(573.0,402.0){\rule[-0.200pt]{15.899pt}{0.400pt}}
\put(639.0,402.0){\rule[-0.200pt]{0.400pt}{47.939pt}}
\put(639.0,601.0){\rule[-0.200pt]{15.658pt}{0.400pt}}
\put(704.0,601.0){\rule[-0.200pt]{0.400pt}{41.676pt}}
\put(704.0,774.0){\rule[-0.200pt]{15.899pt}{0.400pt}}
\put(770.0,774.0){\rule[-0.200pt]{0.400pt}{16.863pt}}
\put(770.0,844.0){\rule[-0.200pt]{12.527pt}{0.400pt}}
\put(822.0,774.0){\rule[-0.200pt]{0.400pt}{16.863pt}}
\put(822.0,774.0){\rule[-0.200pt]{15.899pt}{0.400pt}}
\put(888.0,601.0){\rule[-0.200pt]{0.400pt}{41.676pt}}
\put(888.0,601.0){\rule[-0.200pt]{15.899pt}{0.400pt}}
\put(954.0,402.0){\rule[-0.200pt]{0.400pt}{47.939pt}}
\put(954.0,402.0){\rule[-0.200pt]{15.658pt}{0.400pt}}
\put(1019.0,242.0){\rule[-0.200pt]{0.400pt}{38.544pt}}
\put(1019.0,242.0){\rule[-0.200pt]{15.899pt}{0.400pt}}
\put(1085.0,146.0){\rule[-0.200pt]{0.400pt}{23.126pt}}
\put(1085.0,146.0){\rule[-0.200pt]{15.658pt}{0.400pt}}
\put(1150.0,102.0){\rule[-0.200pt]{0.400pt}{10.600pt}}
\put(1150.0,102.0){\rule[-0.200pt]{15.899pt}{0.400pt}}
\put(1216.0,87.0){\rule[-0.200pt]{0.400pt}{3.613pt}}
\put(1216.0,87.0){\rule[-0.200pt]{15.899pt}{0.400pt}}
\put(1282.0,83.0){\rule[-0.200pt]{0.400pt}{0.964pt}}
\put(1282.0,83.0){\rule[-0.200pt]{15.658pt}{0.400pt}}
\put(1347.0,82.0){\usebox{\plotpoint}}
\put(1347.0,82.0){\rule[-0.200pt]{22.163pt}{0.400pt}}
\end{picture}
\end{center}
%
An enormous number of analyses in computer science come down to
proving that the tails of the binomial and similar distributions are
very small.  In the context of a problem, this typically means that
there is very small probability that something \textit{bad} happens,
which could be a server or communication link overloading or a
randomized algorithm running for an exceptionally long time or
producing the wrong result.

\subsubsection{The General Binomial Distribution}

Now let $J$ be the number of heads that come up on $n$ independent
coins, each of which is heads with probability $p$.  Then $J$ has a
\textit{general binomial density function}:
%
\[
\pdf_J(k) = \binom{n}{k} p^k (1-p)^{n-k}
\]
%
As before, there are $\binom{n}{k}$ sequences with $k$ heads and $n -
k$ tails, but now the probability of each such sequence is $p^k
(1-p)^{n-k}$.

As an example, the plot below shows the probability density function
$\pdf_J(k)$ corresponding to flipping $n=20$ independent coins that
are heads with probabilty $p = 0.75$.  The graph shows that we are
most likely to get around $k = 15$ heads, as you might expect.  Once
again, the probability falls off quickly for larger and smaller values
of $k$.
%
\begin{center}
% GNUPLOT: LaTeX picture
\setlength{\unitlength}{0.240900pt}
\ifx\plotpoint\undefined\newsavebox{\plotpoint}\fi
\sbox{\plotpoint}{\rule[-0.200pt]{0.400pt}{0.400pt}}%
\begin{picture}(1500,900)(0,0)
\font\gnuplot=cmr10 at 10pt
\gnuplot
\sbox{\plotpoint}{\rule[-0.200pt]{0.400pt}{0.400pt}}%
\put(140.0,82.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(120,82){\makebox(0,0)[r]{0}}
\put(1419.0,82.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(140.0,238.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(120,238){\makebox(0,0)[r]{0.05}}
\put(1419.0,238.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(140.0,393.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(120,393){\makebox(0,0)[r]{0.1}}
\put(1419.0,393.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(140.0,549.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(120,549){\makebox(0,0)[r]{0.15}}
\put(1419.0,549.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(140.0,704.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(120,704){\makebox(0,0)[r]{0.2}}
\put(1419.0,704.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(140.0,860.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(120,860){\makebox(0,0)[r]{0.25}}
\put(1419.0,860.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(140.0,82.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(140,41){\makebox(0,0){0}}
\put(140.0,840.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(449.0,82.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(449,41){\makebox(0,0){5}}
\put(449.0,840.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(759.0,82.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(759,41){\makebox(0,0){10}}
\put(759.0,840.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(1068.0,82.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(1068,41){\makebox(0,0){15}}
\put(1068.0,840.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(1377.0,82.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(1377,41){\makebox(0,0){20}}
\put(1377.0,840.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(140.0,82.0){\rule[-0.200pt]{312.929pt}{0.400pt}}
\put(1439.0,82.0){\rule[-0.200pt]{0.400pt}{187.420pt}}
\put(140.0,860.0){\rule[-0.200pt]{312.929pt}{0.400pt}}
\put(140.0,82.0){\rule[-0.200pt]{0.400pt}{187.420pt}}
\put(140,82){\usebox{\plotpoint}}
\put(140.0,82.0){\rule[-0.200pt]{113.705pt}{0.400pt}}
\put(612.0,82.0){\rule[-0.200pt]{0.400pt}{0.482pt}}
\put(612.0,84.0){\rule[-0.200pt]{15.899pt}{0.400pt}}
\put(678.0,84.0){\rule[-0.200pt]{0.400pt}{1.686pt}}
\put(678.0,91.0){\rule[-0.200pt]{12.527pt}{0.400pt}}
\put(730.0,91.0){\rule[-0.200pt]{0.400pt}{5.300pt}}
\put(730.0,113.0){\rule[-0.200pt]{15.899pt}{0.400pt}}
\put(796.0,113.0){\rule[-0.200pt]{0.400pt}{12.768pt}}
\put(796.0,166.0){\rule[-0.200pt]{15.899pt}{0.400pt}}
\put(862.0,166.0){\rule[-0.200pt]{0.400pt}{25.294pt}}
\put(862.0,271.0){\rule[-0.200pt]{12.527pt}{0.400pt}}
\put(914.0,271.0){\rule[-0.200pt]{0.400pt}{38.785pt}}
\put(914.0,432.0){\rule[-0.200pt]{15.899pt}{0.400pt}}
\put(980.0,432.0){\rule[-0.200pt]{0.400pt}{42.157pt}}
\put(980.0,607.0){\rule[-0.200pt]{15.658pt}{0.400pt}}
\put(1045.0,607.0){\rule[-0.200pt]{0.400pt}{25.294pt}}
\put(1045.0,712.0){\rule[-0.200pt]{15.899pt}{0.400pt}}
\put(1111.0,672.0){\rule[-0.200pt]{0.400pt}{9.636pt}}
\put(1111.0,672.0){\rule[-0.200pt]{12.527pt}{0.400pt}}
\put(1163.0,499.0){\rule[-0.200pt]{0.400pt}{41.676pt}}
\put(1163.0,499.0){\rule[-0.200pt]{15.899pt}{0.400pt}}
\put(1229.0,290.0){\rule[-0.200pt]{0.400pt}{50.348pt}}
\put(1229.0,290.0){\rule[-0.200pt]{15.899pt}{0.400pt}}
\put(1295.0,148.0){\rule[-0.200pt]{0.400pt}{34.208pt}}
\put(1295.0,148.0){\rule[-0.200pt]{12.527pt}{0.400pt}}
\put(1347.0,92.0){\rule[-0.200pt]{0.400pt}{13.490pt}}
\put(1347.0,92.0){\rule[-0.200pt]{15.899pt}{0.400pt}}
\put(1413.0,83.0){\rule[-0.200pt]{0.400pt}{2.168pt}}
\put(1413.0,83.0){\rule[-0.200pt]{6.263pt}{0.400pt}}
\end{picture}
\end{center}

\subsubsection{Approximating the Binomial Density Function}

There is an approximate closed-form formula for the general binomial
density function, though it is a bit unwieldy.  First, we need an
approximation for a key term in the exact formula, $\binom{n}{k}$.
For convenience, let's replace $k$ by $\alpha n$ where $\alpha$ is a
number between 0 and 1.  Then, from Stirling's formula, we find that:
%
\begin{align*}
\binom{n}{\alpha n}
        & \leq \frac{2^{n H(\alpha)}}{\sqrt{2 \pi \alpha (1 - \alpha) n}}
\end{align*}
%
where $H(\alpha)$ is the famous \term{entropy function}:
%
\begin{align*}
H(\alpha) & \eqdef \alpha \log_2 \frac{1}{\alpha} +
                (1 - \alpha) \log_2 \frac{1}{1 - \alpha}
\end{align*}
%
This upper bound on $\binom{n}{\alpha n}$ is very tight and serves as
an excellent approximation.

Now let's plug this formula into the general binomial density
function.  The probability of flipping $\alpha n$ heads in $n$ tosses
of a coin that comes up heads with probability $p$ is:
%
\begin{equation}\label{binbnd}
\pdf_J(\alpha n) \leq
        \frac{2^{n H(\alpha)}}{\sqrt{2 \pi \alpha (1 - \alpha) n}} 
        \cdot p^{\alpha n} (1-p)^{(1 - \alpha) n}
\end{equation}
%
This formula is ugly as a bowling shoe, but quite useful.  For
example, suppose we flip a fair coin $n$ times.  What is the
probability of getting \textit{exactly} $\frac{1}{2}n$ heads?
Plugging $\alpha = 1/2$ and $p = 1/2$ into this formula gives:
%
\begin{align*}
\pdf_J(\alpha n) & \leq
        \frac{2^{n H(1/2)}}{\sqrt{2 \pi (1/2) (1 - (1/2)) n}}
        \cdot 2^{-n} \\
        & = \sqrt{\frac{2}{\pi n}}
\end{align*}
%
Thus, for example, if we flip a fair coin 100 times, the probability
of getting exactly 50 heads is about $1 / \sqrt{50 \pi} \approx 0.079$
or around 8\%.

\subsection{Approximating the Cumulative Binomial Distribution Function}

Suppose a coin comes up heads with probability $p$.  As before, let
the random variable $J$ be the number of heads that come up on $n$
independent flips.  Then the probability of getting \textit{at most}
$k$ heads is given by the cumulative binomial distribution function:
%
\begin{align*}
\cdf_J(k)
        & = \pr{J \leq k} \\
        & = \sum_{i = 0}^{k} \pdf_J(i) \\
        & = \sum_{i = 0}^{k} \binom{n}{i} p^i (1-p)^{n-i}
\end{align*}

Evaluating this expression directly would be a lot of work for large
$k$ and $n$, so now an approximation would be really helpful.  Once
again, we can let $k = \alpha n$; that is, instead of thinking of the
absolute number of heads ($k$), we consider the fraction of flips that
are heads ($\alpha$).  The following approximation holds provided
$\alpha < p$:
%
\begin{align*}
\cdf_J(\alpha n)
        & \leq \frac{1 - \alpha}{1 - \alpha / p} \cdot \pdf_J(\alpha n) \\
        & \leq \frac{1 - \alpha}{1 - \alpha / p} \cdot
                \frac{2^{n H(\alpha)}}{\sqrt{2 \pi \alpha (1 - \alpha) n}} 
                \cdot p^{\alpha n} (1-p)^{(1 - \alpha) n}
\end{align*}
%
In the first step, we upper bound the summmation with a geometric sum and
apply the formula for the sum of a geometric series.  (The details are
dull and omitted.)  Then we insert the approximate formula~\eqref{binbnd}
for $\pdf_J(\alpha n)$ from the preceding section.

You have to press a lot of buttons on a calculator to evaluate this
formula for a specific choice of $\alpha$, $p$, and $n$.  (Even
computing $H(\alpha)$ is a fair amount of work!)  But for large $n$,
evaluating the cumulative distribution function exactly requires
vastly \textit{more} work!  So don't look gift blessings in the mouth
before they hatch.  Or something.

As an example, the probability of flipping at most 25 heads in 100
tosses of a fair coin is obtained by setting $\alpha = 1/4$, $p = 1/2$
and $n = 100$:
%
\[
\cdf_J\paren{\frac{n}{4}} \leq \frac{1 - (1/4)}{1 - (1/4) / (1/2)}
                             \cdot \pdf_J\paren{\frac{n}{4}}
                    \leq \frac{3}{2} \cdot 1.913 \cdot 10^{-7}.
\]
%
This says that flipping 25 or fewer heads is extremely unlikely, which
is consistent with our earlier claim that the tails of the binomial
distribution are very small.  In fact, notice that the probability of
flipping \textit{25 or fewer} heads is only 50\% more than the
probability of flipping \textit{exactly 25} heads.  Thus, flipping
exactly 25 heads is twice as likely as flipping any number between 0
and 24!  

\noindent \textbf{Caveat}: The upper bound on $\cdf_J(\alpha n)$ holds
only if $\alpha < p$.  If this is not the case in your problem, then
try thinking in complementary terms; that is, look at the number of
tails flipped instead of the number of heads.  In our example,
the probability of flipping 75 or more heads is the same as
the probability of flipping 25 or fewer tails.  By the above
analysis, this is also extremely small.

\iffalse
\section{Philosophy of Polling}

One place where the binomial distribution comes up is in polling.
Polling involves not only some tricky mathematics, but also some
philosophical issues.
The difficulty is that polling tries to apply probabilty theory to
resolve a question of fact.  We can make a
convincing argument that a statement about public opinion is true, but
can not actually say that the statement is true with any particular
probability.  Suppose we're conducting a yes/no poll on some question.
Then we assume that some fraction $p$ of the population would answer
``yes'' to the question and the remaining $1 - p$ fraction would
answer ``no''.  (Let's forget about the people who hang up on
pollsters or launch into long stories about their little dog Fi-Fi---
real pollsters have no such luxury!)  Now, $p$ is a fixed number, not
a randomly-determined quantity.  

Probability slips into a poll since the pollster samples the opinions
of a people selected uniformly and independently at random.  The
results are qualified by saying something like this:
%
\begin{quotation}
``One can say with 95\% confidence that the maximum margin of sampling
error is $\pm 3$ percentage points.''
\end{quotation}
%
This means that either the number reported in the poll is within 3\%
of the actual fraction $p$ or else an unlucky 1-in-20 event happened
during the polling process; specifically, the pollster's random sample
was not representative of the population at large.  This is
\textit{not} the same thing as saying that there is a 95\% chance that
the poll is correct; it either is or it isn't. 

\fi


\subsection{Polling}

Suppose we want to estimate the fraction of the U.S. voting population who
would favor Hillary Clinton over Rudy Giuliani in the year 2008
presidential election.\footnote{We can only keep our fingers crossed for
this race to happen --
when they ran against each other for the U.S. Senate
in 2000, they generated some of the best entertainment in TV history.}
Let $p$ be this unknown fraction.  Let's suppose
we have some random process ---say throwing darts at voter registration
lists--- which will select each voter with equal probability.  We can
define a Bernoulli variable, $K$, by the rule that $K=1$ if the random
voter most prefers Clinton, and $K=0$ otherwise.

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

The variable $S_n/n$ describes the fraction of voters \emph{in our sample}
who favor Clinton.  We would expect that $S_n/n$ should
be something like $p$.
%Note that
%\[
%\expect{\frac{S_n}{n}} = \sum_{i=1}^n \expect{K_i} = pn.
%\]
We will use the sample value, $S_n/n$, as our \emph{statistical estimate} of
$p$.

In particular, suppose we want our estimate of $p$ to be within $0.04$
of $p$ at least 95\% of the time.  Namely, we want
\[
\pr{\abs{\frac{S_n}{n} - p} \leq 0.04} \geq 0.95\ .
\]
Let $\epsilon$ be the margin of error we can tolerate, and let $\delta$ be
the probability that our result lies outside this margin.  We're
interested in having $\epsilon = 0.04$ and $\delta \le 0.05$, but the
derivation will be clearer if we postpone plugging these values in until
the end.

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

We can define $\delta$, the probability that our poll is off by more
than the margin of error $\epsilon$, as follows:
\begin{eqnarray*}
\delta  & = &
        \underbrace{\pr{\frac{S_n}{n} \leq p - \epsilon}}_{
\begin{array}{c}
\mbox{too many in sample} \\
\mbox{prefer ``Giuliani''}
\end{array}}
        + \underbrace{\pr{\frac{S_n}{n} \geq p + \epsilon}}_{
\begin{array}{c}
\mbox{too many in sample} \\
\mbox{prefer ``Clinton''}
\end{array}} \\
        & = & \pr{S_n \leq (p - \epsilon) n} + \pr{S_n \geq (p + \epsilon) n}.
\end{eqnarray*}

Now
\[
\cdf_{S_n}((p-\epsilon)n) \eqdef \pr{S_n \leq (p - \epsilon) n}
\]
%where $F_{n,p}$ is the \emph{cumulative} binomial distribution function.
Also,
\[
\pr{S_n \geq (p + \epsilon) n} = \pr{n- S_n \leq ((1-p) - \epsilon)n}.
\]
But $T_n \eqdef n - S_n$ is simply the number of voters in the sample who prefer
Giuliani, which is a sum of Bernoulli random variables
with parameter $1-p$, and therefore
\[
\pr{T_n \leq ((1-p) - \epsilon)n} = \cdf_{T_n}((1-p) - \epsilon)n.
\]
Hence
\begin{equation}\label{Fnpe}
\delta = \cdf_{S_n}((p - \epsilon) n) + \cdf_{T_n}(((1-p) - \epsilon) n).
\end{equation}
So we have reduced getting a good estimate of the required sample size to
finding good bounds on two cumulative binomial distributions
with parameters $p$ and $1-p$ respectively.

Using the bound on the cumulative binomial distribution function allows us
to calculate an expression bounding~\eqref{Fnpe} in terms of $n, \epsilon$
and $p$.  The problem is that this bound would contain $p$, the fraction
of Americans that prefer Clinton.  This is the unknown number we are
trying to determine by polling!  Fortunately, there is a simple way out of
this circularity.  Since~\eqref{Fnpe} is symmetric in $p$, it has an
inflection point when $p=1/2$, and this inflection point is, in fact, its
maximum:
\begin{fact*}
For all $\epsilon,n$, the maximum value of $\delta$ in
equation~\eqref{Fnpe} occurs when $p = 1/2$.
\end{fact*}
In other words, the binomial tails fall off most slowly when $p=1/2$.
Using this fact, and plugging into 
the equations for 
$\cdf_{S_n}((p - \epsilon) n)$ and $\cdf_{T_n}(((1-p) - \epsilon) n)$,
we get the following theorem:

\iffalse
So, letting $\alpha = (1/2) - \epsilon$, we have
\begin{align*}
\delta & \leq F_{n,1/2}((\frac{1}{2} - \epsilon) n) +
   F_{n,1 - 1/2}((1 -\frac{1}{2}-\epsilon) n)\notag\\
   & = 2 F_{n,1/2}(\alpha n)\notag\\
 & \le 2 \cdot \frac{\beta}{1 - \alpha / (1/2)} \cdot
                \frac{2^{n H(\alpha)}}{\sqrt{2 \pi \alpha \beta  n}} 
                \cdot (1/2)^{\alpha n} (1/2)^{\beta n}
   &\text{(by~\eqref{1 - H} and~\eqref{Fbyf})}\notag\\
 & =  2 \cdot \frac{\beta}{1 - 2\alpha} \cdot
                \frac{2^{n H(\alpha)}}{\sqrt{2 \pi \alpha \beta  n}}
                \cdot (1/2)^n\notag\\
 & = 2 \cdot \frac{\beta}{1 - 2\alpha} \cdot
                \frac{2^{-n (1 - H(\alpha))}}{\sqrt{2 \pi \alpha \beta n}}\\
 & = \frac{1 - 2\epsilon}{2\epsilon} \cdot
     \frac{2^{-n (1 - H((1/2) - \epsilon))}}{\sqrt{2 \pi (1/4 - \epsilon^2) n}}.
\end{align*}

To summarize, we have established
\fi
\begin{theorem}[Binomial Sampling]\label{bs}
Let $K_1, K_2, \dots$, be a sequence of mutually independent 0-1-valued
random variables with the same expectation, $p$, and let
\[
S_n \eqdef \sum_{i=1}^n K_i.
\]
Then, for $1/2 > \epsilon > 0$,
\begin{equation}\label{delta bound}
\pr{\abs{\frac{S_n}{n} - p} \geq \epsilon}
\leq 
\frac{1 + 2\epsilon}{2\epsilon} \cdot
        \frac{2^{-n (1 - H((1/2) - \epsilon))}}{\sqrt{2 \pi (1/4 - \epsilon^2) n}}.
\end{equation}

\end{theorem}

We want $\epsilon = 0.04$, so plugging into~\eqref{delta bound} gives 
\begin{equation}\label{db2}
\delta \leq 13.5 \cdot \frac{2^{-n(0.00462)}}{1.2492 \sqrt{n}}
\end{equation}
where $\delta$ is the probability that our estimate is not within
$\epsilon$ of $p$.  We want to poll enough people so that $\delta \leq
0.05$.  The easiest way to find the necessary sample size $n$ is to plug
in values for $n$ to find the smallest one where in the righthand side
of~\eqref{db2} is $ \leq 0.05$:
\[
\begin{array}{c|l}
\mbox{$n$ = people polled} & \begin{array}{cc}
\mbox{upper bound on} \\
\mbox{probability poll is wrong}
\end{array} \\
\hline
500 &  9.7\% \\
600 &  6.4\% \\
623 &  5.9\% \\
650 &  5.3\% \\
664 &  5.0\% \quad \leftarrow \quad \mbox{our poll size} \\
700 &  4.3\% \\
\end{array}
\]
So 95\% of the time, polling 664\footnote{An exact calculation of the
binomial \cdf\ shows that a somewhat smaller poll size of 612 would be
sufficient.}  people will yield a fraction that is within 0.04 of the
actual fraction of voters preferring Clinton.

A remarkable point is that the population of the country has no
effect on the poll size!  Whether there are a thousand people or a
billion in the country, polling only a few hundred is sufficient!

This method of estimation by sampling a quantity ---voting preference in
this example--- is a technique that can obviously be used to estimate many
other unknown quantities.

\begin{notesproblem} \textbf{Explaining Sampling to a Jury}

We just showed that merely sampling 662 voters will yield a fraction that,
95\% of the time, is within 0.04 of the of the actual fraction of voters
who prefer Clinton.  The actual size of the voting population (10's of
millions) was never considered because \emph{it did not matter}.

Suppose you were going to serve as an expert witness in a trial.  How
would you explain why the number of people necessary to poll \emph{does
not depend on the population size}?

\solution{This was intended to be a thought-provoking, conceptual
question.  In past terms, although most of the class could follow the
derivations and crank through the formulas to calculate poll size and
confidence levels, many students couldn't articulate, and indeed didn't
really believe that the derived sample sizes were actually adequate to
produce reliable estimates.

Here's a way to explain why we model polling people about Clinton as
independent coin tosses that a jury might be able to follow:

\begin{quote}
Of the approximately 100,000,000 voters in the US, there are some
\emph{unknown} number, say 51,000,000, who favor Clinton.  So in this case,
the \emph{fraction} of voters favoring Clinton would be
51,000,000/100,000,000 = 0.51.

To estimate this unknown fraction, we randomly select one person from the
100,000,000 in such a way that \emph{everyone has an equal chance of being
picked}.  For example, we might get computer files from the Census Bureau
listing all 100,000,000 voters in the US.  Then we would generate a number
between 1 and 100,000,000 by some physical or computational process that
generated each number with equal probability, and then we would interview
the person whose number came up.  Picking a person this way amounts to
flipping a coin that had a chance of coming up ``Clinton'' that was equal to
the unknown fraction.  In our example, there would be a 51\% chance of the
``coin'' coming up ``Clinton'' and a 49\% chance of coming up ``Giuliani.''  

After we have picked a person and learned their voting preference, we
perform the procedure again, making sure that everyone is equally likely
to be picked the second time, and so on, for picking a third, fourth, \etc
person.  Each pick is like flipping a coin whose probability of coming up
``Clinton'' is the same unknown fraction.

Now we all understand that if we keep flipping a coin with a 51\% chance
of coming up Heads, then the more we flip, the closer the fraction of
Heads flipped will be to 51\%.  Mathematical theory lets us calculate us
how many times to flip coins to make the fraction of Heads very likely
close to 51\%, but we need't go into the details of the calculation.

Now suppose we had two coins, say a penny and a nickel, which had the same
51\% probability of coming up Heads.  Then it's not going to make any
difference which coin we use in our coin flips: the number of flips we
need to get the fraction of Heads flipped being very likely close to 51\%
will be the same whether we flip pennies or nickels.

Different size populations correspond to different coins: the nickel might
correspond to selecting a voter from a population 100,000,000 people, and
the dime might correspond to selecting one from a population of 100.  The
same number of flips of pennies or nickels will allow us to estimate the
probability of ``Heads,'' and hence to estimate the fraction of voters
favoring Clinton.  All that mattered is that the ``penny'' population had the
same probability of Heads, namely, 51,000,000 out of a population of
100,000,000, as the ``nickel'' population, namely, 51 out of 100.

So the number of ``flips'' needed does not depend on whether we're
flipping a ``51\% penny'' or a ``51\% nickel.''  That is, if two
populations have the same fraction of voters favoring Clinton, then \emph{the
number of people we need to poll is the same}, even if the populations are
of very different sizes.
\end{quote}
}

\end{notesproblem}


\section{Confidence Levels}

Suppose a pollster uses a sample of 662 random voters to estimate the
fraction of voters who prefer Clinton, and the pollster finds that 364 of them
prefer Clinton.  It's tempting, \textbf{but sloppy}, to say that this means:
\begin{falseclm*}
With probability 0.95, the fraction, $p$, of voters who prefer
Clinton is $364/662 \pm 0.04$.  Since $364/662 -0.04 >0.50$, there is a 95\%
chance that more than half the voters prefer Clinton.
\end{falseclm*}
What's objectionable about this statement is that it talks about the
probability or ``chance'' that a real world fact is true, namely that the
actual fraction, $p$, of voters favoring Clinton is more than 0.50.  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.49;
then it's nonsense to ask about the probability that it is within 0.04 of
364/662 ---it simply isn't.

A more careful summary of what we have accomplished goes this way:
\begin{quote}
We have described a probabilistic procedure for estimating the value of
the actual fraction, $p$.  The probability that \emph{our estimation
procedure} will yield a value within 0.04 of $p$ is 0.95.
\end{quote}
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
\begin{quote}
At the 95\% \emph{confidence level}, the fraction of voters
who prefer Clinton is $364/662 \pm 0.04$.
\end{quote}
It's important to remember that confidence levels refer to the results of
estimation procedures for real-world quantities.  The real-world quantity
being estimated is typically unknown, but fixed; it is not a random
variable, so it makes no sense to talk about the probability that it has
some property.

\section{Expected Value}

The \term{expectation} or \term{expected value} of a random variable
is a single number that tells you a lot about the behavior of the
variable.  Roughly, the expectation is the average value, where each
value is weighted according to the probability that it comes up.
Formally, the expected value of a random variable $R$ defined on a
sample space $S$ is:
%
\[
\expect{R} = \sum_{w \in S} R(w) \pr{w}
\]
%
To appreciate its signficance, suppose $S$ is the set of students in a
class, and we select a student uniformly at random.  Let $R$ be the
selected student's exam score.  Then $\expect{R}$ is just the class
average--- the first thing everyone want to know after getting their
test back!  In the same way, expectation is usually the first thing
one wants to determine about any random variable.

Let's work through an example.  Let $R$ be the number that comes up on
a fair, six-sided die.  Then the expected value of $R$ is:
%
\begin{align*}
\expect{R}
    & = \sum_{k=1}^6 k \cdot \frac{1}{6} \\
    & = 1 \cdot \frac{1}{6} + 2 \cdot \frac{1}{6} + 3 \cdot \frac{1}{6} +
        4 \cdot \frac{1}{6} + 5 \cdot \frac{1}{6} + 6 \cdot \frac{1}{6} \\
    & = \frac{7}{2}
\end{align*}
%
This calculation shows that the name ``expected value'' is a little
misleading; the random variable might \textit{never} actually take on
that value.  You can't roll a $3 \frac{1}{2}$ on an ordinary die!

\subsection{Equivalent Definitions of Expectation}

There are some other ways of writing the definition of expectation.
Sometimes using one of these other formulations can make computing an
expectation a lot easier.  One option is to group together all
outcomes on which the random variable takes on the same value.

\begin{theorem}
\[
\expect{R} = \sum_{x \in \range{R}} x \cdot \pr{R = x}
\]
\end{theorem}

\begin{proof}
We'll transform the left side into the right.  Let $[R=x]$ be the event
that $R = x$.
%
\begin{align*}
\expect{R}
    & = \sum_{w \in S} R(w) \pr{w} \\
    & = \sum_{x \in \range{R}} \sum_{w \in [R=x]} R(w) \pr{w} \\
    & = \sum_{x \in \range{R}} \sum_{w \in [R=x]} x \pr{w} \\
    & = \sum_{x \in \range{R}}
             \paren{x \cdot \sum_{w \in [R=x]} \pr{w}} \\
    & = \sum_{x \in \range{R}} x \cdot \pr{R = x}
\end{align*}
%
On the second line, we break the single sum into two.  The outer sum
runs over all possible values $x$ that the random variable takes
on, and the inner sum runs over all outcomes taking on that value.
Thus, we're still summing over every outcome in the sample space
exactly once.  On the last line, we use the definition of the
probability of the event $[R = x]$.
\end{proof}

\begin{corollary}\label{exRcor}
If $R$ is a natural-valued random variable, then:
%
\[
\expect{R} = \sum_{i=0}^{\infty} i \cdot \pr{R = i}
\]
\end{corollary}

When you are considering a random variable {\em
that takes on values only in the natural numbers,} $\naturals \eqdef
\set{0, 1, 2, \dots}$,
there is yet another way to write the expected value:

\begin{theorem}
If $R$ is a natural-valued random variable, then:
%
\[
\expect{R} = \sum_{i=0}^{\infty} \pr{R > i}
\]
\end{theorem}

\begin{proof}
Consider the sum:
%
\[
\begin{array}{ccccccc}
\pr{R = 1} & + & \pr{R = 2} & + & \pr{R = 3} & + & \cdots \\
           & + & \pr{R = 2} & + & \pr{R = 3} & + & \cdots \\
           &   &            & + & \pr{R = 3} & + & \cdots \\
           &   &            &   &            & + & \cdots
\end{array}
\]
%
The columns sum to $1 \cdot \pr{R = 1}$, $2 \cdot \pr{R = 2}$, $3
\cdot \pr{R = 3}$, etc.  Thus, the whole sum is equal to:
%
\[
\sum_{i=0}^{\infty} i \cdot \pr{R = i} = \expect{R}
\]
%
Here, we're using Corollary~\ref{exRcor}.  On the other hand, the
rows sum to $\pr{R > 0}$, $\pr{R > 1}$, $\pr{R > 2}$, etc.  Thus, the
whole sum is also equal to:
%
\[
\sum_{i=0}^{\infty} \pr{R > i}
\]
%
These two expressions for the whole sum must be equal, which proves
the theorem.
\end{proof}

\subsection{Expected Value of an Indicator Variable}

The expected value of an indicator random variable for an event is
just the probability of that event.  (Remember that a random variable
$I_A$ is the indicator random variable for event $A$, if $I_A = 1$
when $A$ occurs and $I_A= 0$ otherwise.)
\begin{lemma}\label{expindic}
If $I_A$ is the indicator random variable for event $A$, then
\[
\expect{I_A} = \pr{A}.
\]
\end{lemma}

\begin{proof}
\begin{align*}
\expect{I_A} 
& =  1 \cdot \pr{I_A = 1} + 0 \cdot \pr{I_A = 0} 
& 
\\
& = \pr{I_A = 1}
\\
& =  \pr{A}. & \text{(Def. of $I_A$)}
\end{align*}
\end{proof}
For example, if $A$ is the event that a coin
with bias $p$ comes up heads, $\expect{I_A} = \pr{I_A=1} = p$.

\subsection{Mean Time to Failure}

Let's look at a problem where one of these alternative definitions of
expected value is particularly helpful.  A computer program crashes at
the end of each hour of use with probability $p$, if it has not
crashed already.  What is the expected time until the program crashes?

If we let $R$ be the number of hours until the crash, then the answer
to our problem is $\expect{R}$.  This is a natural-valued variable, so we
can use the formula:
%
\[
\expect{R} = \sum_{i=0}^{\infty} \pr{R > i}
\]
%
We have $R > i$ only if the system remains stable after $i$
opportunities to crash, which happens with probability $(1-p)^i$.
Plugging this into the formula above gives:
%
\begin{align*}
\expect{R} & = \sum_{i=0}^{\infty} (1-p)^i \\
       & = \frac{1}{1 - (1-p)} \\
       & = \frac{1}{p}
\end{align*}
%
The closed form on the second line comes from the formula for the sum
of an infinite geometric series where the ratio of consecutive terms
is $1 - p$.

So, for example, if there is a 1\% chance that the program crashes at
the end of each hour, then the expected time until the program crashes
is $1 / 0.01 = 100$ hours.  The general principle here is well-worth
remembering: if a system fails at each time step with probability $p$,
then the expected number of steps up to the first failure is $1 / p$.

\subsubsection{Making a Baby Girl}

A couple really wants to have a baby girl.  There is a 50\% chance
that each child they have is a girl, and the genders of their children
are mutually independent.  If the couple insists on having children
until they get a girl, then how many baby boys should they expect
first?

This is really a variant of the previous problem.  The question, ``How
many hours until the program crashes?'' is mathematically the same as
the question, ``How many children must the couple have until they get
a girl?''  In this case, a crash corresponds to having a girl, so we
should set $p = 1/2$.  By the preceding analysis, the couple
should expect a baby girl after having $1/p = 2$ children.  Since the
last of these will be the girl, they should expect just one boy.

Something to think about: 
If every couple follows the strategy of having children
until they get a girl, what will eventually happen to the fraction
of girls born in this world?


\end{document}
\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 same rule holds
for 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}
Corollary~\ref{linexp-k-thm} follows from Theorem~\ref{linexp-2-thm} by a
routine induction on $k$ which we omit.

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
glued together!\footnote{This is provided that gluing does not change
weights to make the individual dice unfair.}

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.  By
Lemma~\ref{expindic}, we have
\[
\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.
\]
That is, the expectation of a $(n,p)$-binomially distributed variable is
$pn$.

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

\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 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{thm:condexp}
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=$``$P$ is male'' and $F=$``$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{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{(Def.~\ref{defcondexp})}\\
   & = \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{(Theorem~\ref{condexplin})}\\
   & = \sum_{r} r \cdot \expect{R_2} \cdot \pr{R_1 = r}
                     & \text{($R_2$ independent of $R_1$)}\\
   & = \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 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*}

\newcommand{\IQ}{\text{I.Q.\@\xspace}}
\end{document}
