\documentclass[11pt]{article}
\usepackage{macros-course-lectures}

\lectureformat

\showsolutionstrue

\newcommand{\expcond}[2]{\expect{#1\mid#2}}
\newcommand{\range}[1]{\mathop{\textup{range}}\nolimits(#1)}
\newcommand{\sspace}{\mathcal{S}}

\begin{document}

\lecture{notes12}{Random Variables and Expectation}{November 19, 2001}{\stamp}

\section{Random Variables}
 
When we perform an experiment, we expect the results to be observable---
did the player hit a home run or not?---or measurable---how far did the
ball travel? how fast was the pitch?  To describe the behavior of such
probabilistic experiments with measurable outcomes, we use \emph{random
variables}.

\begin{definition}
A \emph{random variable} over a given sample space is a function that maps
every outcome to a real number.
\end{definition}

For example, consider the experiment of tossing three independent,
unbiased coins.  The sample space, $\sspace$, for this experiment consists
of eight outcomes: $\mathtt{HHH}$, $\mathtt{HHT}$, $\mathtt{HTH}$, etc.
Let $C: S \to \reals$ be the function defined by:
\[
C(w) \eqdef \mbox{number of heads appearing in outcome $w \in \sspace$}.
\]
Then $C$ is a random variable, because it maps every outcome in the sample
space $\sspace$ to a real number.  For example, $C(\mathtt{HHH}) = 3$,
$C(\mathtt{HTH}) = 2$, $C(\mathtt{TTT}) = 0$, etc.

Similarly, for the same experiment, we can define a random variable
$M: \sspace \to \reals$ as follows.
\[
M(w) \eqdef \left\{ \begin{array}{cl}
        1 & \mbox{ if all 3 coins match in outcome $w \in \sspace$}, \\
        0 & \mbox{ otherwise}.
\end{array} \right.
\]
For example, $M(\mathtt{HHH}) = 1$, $M(\mathtt{HTH}) = 0$,
$M(\mathtt{TTT}) = 1$, and so on.

Notice that calling a random variable a ``variable'' a misnomer: it is
actually a function.

We will use these two random variables, $C$ and $M$, as continuing
examples; keep in mind that $C$ \textbf{c}ounts heads and $M$ indicates
that all coins \textbf{m}atch.

\subsection{Indicator Random Variables}

\emph{Indicator} random variables describe experiments to detect whether
or not something happened.  The random variable $M$ is an example of an
indicator variable, indicating whether or not all three coins match.

\begin{definition}
An \emph{indicator random variable} is a random variable that maps
every outcome to either 0 or 1.
\end{definition}

Indicator random variables are also called \emph{Bernoulli} or
\emph{characteristic} random variables.  Typically, indicator random
variables identify all outcomes that share some property
(``characteristic''): outcomes with the property are mapped to 1, and
outcomes without the property are mapped to 0.

\subsection{Events Defined by a Random Variable}

There is a natural relationship between random variables and events.
Recall that an event is just a subset of the outcomes in the sample
space of an experiment.

The relationship is simplest for an indicator random variable.  An
indicator random variable partitions the sample space into two blocks:
outcomes mapped to 1 and outcomes mapped to 0.  These two sets of
outcomes are events.  For example, the random variable $M$ partitions
the sample space as follows:
\[
\underbrace{\mathtt{HHH} \quad \mathtt{TTT}}_{\mbox{mapped to 1}} \quad
\underbrace{\mathtt{HHT} \quad \mathtt{HTH} \quad \mathtt{HTT} \quad
        \mathtt{THH} \quad \mathtt{THT} \quad \mathtt{TTH}}_{\mbox{mapped to 0}}
\]

Thus, the random variable $M$ defines two events, the event that all
coins match (denoted $M = 1$) and the event that not all coins match
(denoted $M = 0$).

A general random variable may partition the sample space into many
blocks.  A block contains all outcomes mapped to the same value by the
random variable.  Each block is a set of outcomes and theheefore an
event.  For example, the random variable $C$ partitions the sample
space into four blocks:

\[
\underbrace{\mathtt{TTT}}_{\mbox{mapped to 0}} 
\underbrace{\mathtt{TTH} \quad \mathtt{THT} \quad \mathtt{HTT}}_{\mbox{mapped to 1}} \quad
\underbrace{\mathtt{THH} \quad \mathtt{HTH} \quad \mathtt{HHT}}_{\mbox{mapped to 2}} \quad
\underbrace{\mathtt{HHH}}_{\mbox{mapped to 3}} 
\]

Thus, the random variable $C$ defines four events, namely that $C=0$ or
$C= 1$ or 2 or 3.  These are the events that no coin is heads, that one
coin is heads, that two coins are heads, and finally that three coins are
heads.

We can define other events in terms of random variables as well.  For
example, the event $[C \geq 2]$, consists of all outcomes mapped to 2 or
more.  This event is simply the union of the events $[C = 2]$ and $[C =
3]$.  Similarly, $[C \in \set{1, 3}]$ is the event that there are an odd
number of heads.

Now consider the event $[C \cdot M >0]$; since neither $C$ nor
$M$ take negative values, $C\cdot M>$ iff both $C>0$ and $M>0$---in other
words, there is a head, and all three dice match.  So saying $C \cdot M
>0$ is just an obscure way of saying that all three coin flips come up
heads.  That is, $[C \cdot M >0] = \set{\mathtt{HHH}}$.

\iffalse
In general, suppose $P(r_1,\dots,r_n)$ is a proposition about real numbers
$r_1,\dots,r_n$, and $R_1,\dots,R_n$ are random variables.  Then we use
the notation $[P(R_1,\dots,R_n)]$ to denote the event that the values of
$R_1,\dots,R_n$ satisfy $P$.  That is,
\[
[P(R_1,\dots,R_n)] \eqdef \set{ w \in \sspace \suchthat P(R_1(w),\dots,R_n(w))}.
\]
\fi

When the meaning is clear, we often omit the square brackets denoting
events.  For example, we say ``the event $C=0$'' instead of ``the event
$[C=0]$,'' or $\pr{C=0}$ instead of $\pr{[C=0]}$.

\subsection{Probability of Events Defined by a Random Variable}

Recall that the probability of an event is the sum of the probabilities of
the outcomes it contains.  From this rule, we can compute the probability
of various events associated with a random variable.  For example, if $R :
\sspace \to \reals$ is a random variable and $x$ is a real number, then
\begin{equation*}
\pr{[R = x]}  =  \sum_{w \in [R = x]} \pr{w}.
\end{equation*}
For example, we can compute $\pr{C = 2}$ as follows:
\begin{eqnarray}
\pr{C = 2}      & = & \sum_{w \in [C = 2]} \pr{w} \label{C2.1}\\
                & = & \pr{\mathtt{THH}} + \pr{\mathtt{HTH}} + \pr{\mathtt{HHT}}\label{C2.2} \\
                & = & \frac{1}{8} + \frac{1}{8} + \frac{1}{8} = \frac{3}{8}. \label{C2.3}
\end{eqnarray}

Here $\sspace$ is the sample space $\set{\mathtt{HHH}, \mathtt{HHT},
\mathtt{HTH}, \dots}$.  Equation~(\ref{C2.1}) uses the definition of the
probability of an event.  In equation~(\ref{C2.2}), the three outcomes
corresponding to terms in the summation are explicitly shown.
In~(\ref{C2.3}), we observe that every outcome has probability $1/8$,
since the three coins are fair and independent.

Similarly, we can compute $\pr{M = 1}$:
\begin{eqnarray*}
\pr{M = 1}      & = & \sum_{w \in [M = 1]} \pr{w} \\
                & = & \pr{\mathtt{HHH}} + \pr{\mathtt{TTT}}\\
                & = & \frac{1}{8} + \frac{1}{8} = \frac{1}{4}.
\end{eqnarray*}
The justification for each step is the same as before.

We can find the probability of the event that $C \geq 2$ in the same way:
\begin{eqnarray*}
\pr{C \geq 2}   & = &   \sum_{w \in [C \geq 2]} \pr{w} \\
                & = &   \pr{\mathtt{THH}} + \pr{\mathtt{HTH}} + \pr{\mathtt{HHT}} + \pr{\mathtt{HHH}} \\
             & = &   \frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8} = \frac{1}{2}.
\end{eqnarray*}

It's common in such calculations to group outcomes by their value.
For instance, in the example just above, we could calculate:
\begin{eqnarray*}
\pr{C \geq 2}   & = &   \sum_{i \geq 2} \pr{C = i} \\
                & = &   \pr{C = 2} + \pr{C = 3} \\
                & = &   \pr{\mathtt{THH}, \mathtt{HTH}, \mathtt{HHT}} + \pr{\mathtt{HHH}} \\
                & = &   \frac{3}{8}+\frac{1}{8} = \frac{1}{2}
\end{eqnarray*}

\iffalse
If the range of $R$ is $\set{a_0,a_1,\dots} \subset \reals$, an expression
of the form $\pr{R \geq x}$ can also be evaluated with the summation
$\sum_{a_i \geq x} \pr{R = a_i}$.  That is, instead of summing over outcomes
mapped to at least $x$ as above, we can sum probabilities over all values
of the random variable that are greater than or equal to $x$.  The result
is the same, since both summations cover the same outcomes.
\fi

Similarly, we find the probability of the event that $C \in \set{ 1, 3}$.
\iffalse
\begin{eqnarray*}
\pr{C \in \{1, 3 \}}
        & = &   \sum_{w \in [C \in \set{1, 3}]} \pr{w} \\
        & = &   \pr{\mathtt{TTH}}+\pr{\mathtt{THT}}+\pr{\mathtt{HTT}} + \pr{\mathtt{HHH}} \\
        & = &   \frac{1}{8} + \frac{1}{8} + \frac{1}{8} + \frac{1}{8} = \frac{1}{2}
\end{eqnarray*}

As in the preceding example, this probability could be evaluated by
summing probabilities over values of $C$ instead of by summing over
outcomes:
\fi
\begin{eqnarray*}
\pr{C \in \{1, 3 \}}
        & = &   \sum_{i \in \set{ 1, 3}} \pr{C = i} \\
        & = &   \pr{C = 1} + \pr{C = 3} \\
        & = &   \pr{\mathtt{TTH}, \mathtt{THT}, \mathtt{HTT} } + \pr{\mathtt{HHH}} \\
        & = &   \frac{3}{8}+\frac{1}{8} = \frac{1}{2}
\end{eqnarray*}

In general, for a set $A = \set{a_0,a_1,\dots}$ of reals, $\pr{R \in A}$
can also be evaluated by summing over the values in $A$.  That is,
\[
\pr{R \in A} = \sum_{i \in \naturals} \pr{R = a_i} = \sum_{a \in A} \pr{R = a}.
\]

\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 all three coins are not the same ($M = 0$).  We can compute
this probability using the familiar Product Rule:

\begin{eqnarray*}
\prcond{C \geq 2}{M = 0}
        & = &   \frac{\pr{C \geq 2 \land M = 0}}{\pr{M = 0}} \\
        & = &   \frac{\pr{\set{\mathtt{THH}, \mathtt{HTH}, \mathtt{HHT}}}}
                     {\pr{\set{\mathtt{THH}, \mathtt{HTH}, \mathtt{HHT},
                             \mathtt{HTT}, \mathtt{THT}, \mathtt{TTH}}}} \\
        & = &   \frac{3/8}{6/8} =  \frac{1}{2}.
\end{eqnarray*}

\subsection{Independence}

The notion of independence does not carry over to random variables so
easily.  In analogy to event independence, we will first define
independence for a pair of random variables and then define mutual
independence for two or more random variables.

\subsubsection{Independence for Two Random Variables}

\begin{definition}\label{ind1}
Two random variables $R_1$ and $R_2$ are \emph{independent}\footnote{This
definition works for sample spaces $\sspace = \set{w_0,w_1,\dots}$ of the
kind we consider in 6.042.  For more general sample spaces, the definition
is that
\[
\prcond{y_1 \le R_1  \le x_1}{y_2 \le R_2 \le x_2} =
                         \pr{y_1 \le R_1 \le x_1}
\]
for all $y_1,x_1,y_2, x_2 \in \reals$ and $\pr{y_2 \le R_2 \le x_2} \neq 0$.}
if for all $x_1, x_2 \in \reals$ such that $\pr{R_2 = x_2} \neq 0$,
we have:
\[
\prcond{R_1 = x_1}{R_2 = x_2} = \pr{R_1 = x_1}
\]
\end{definition}

As with independence of events, we can also formulate independence of two
random variables in terms of the conjunction of events:
\begin{definition}\label{ind2}
Two random variables $R_1$ and $R_2$ are \emph{independent} if for all
$x_1, x_2 \in \reals$ , we have:
\[
\pr{R_1 = x_1 \land R_2 = x_2} = \pr{R_1 = x_1} \cdot \pr{R_2 = x_2}.
\]
\end{definition}

Definition~(\ref{ind1}) says that the probability that $R_1$ has a
particular value is unaffected by the value of $R_2$, reflecting the
intuition behind independence.  Definition~(\ref{ind2}) has the slight
technical advantage that it applies even if $\pr{R_2 = x_2} = 0$.
Otherwise, the two definitions are equivalent, and we will use both.

\subsubsection{Proving that Two Random Variables are Not Independent}

Are $C$ and $M$ independent?  Intuitively, no: the number of heads
($C$) not only affects, but completely determines whether all three
coins match ($M$).  To prove this, let's use the first definition of
independence.  We must find some $x_1, x_2 \in \reals$ such that the
condition in the first definition is false.  For example, the
condition does not hold for $x_1 = 2$ and $x_2 = 1$:
\begin{eqnarray*}
\pr{C = 2 \land M = 1} = 0
        & \mbox{ but } &
\pr{C = 2} \cdot \pr{M = 1} = \frac{3}{8} \cdot \frac{1}{4} \neq 0
\end{eqnarray*}

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.

\subsubsection{A Dice Example}

Suppose that we roll two fair, independent dice.  We can regard the
numbers that turn up as random variables, $D_1$ and $D_2$.  For
example, if the outcome is $w = (3, 5)$, then $D_1(w) = 3$ and $D_2(w)
= 5$.

Let $T = D_1 + D_2$.  Then $T$ is also a random variable, since it is
a function mapping each outcome to a real number, namely the sum of
the numbers shown on the two dice.  For outcome $w = (3, 5)$, we have
$T(w) = 3 + 5 = 8$.

Define $S$ as follows:

\[
S \eqdef \left\{
\begin{array}{cl}
1 & \mbox{if $T = 7$}, \\
0 & \mbox{if $T \neq 7$}.
\end{array}
\right.
\]

That is, $S = 1$ if the sum of the dice is 7, and $S = 0$ if the sum
of the dice is not 7.  For example, for outcome $w = (3, 5)$, we have
$S(w) = 0$, since the sum of the dice is 8.  Since $S$ is a function
mapping each outcome to a real number, $S$ is also a random variable.
In particular, $S$ is an indicator random variable, since every
outcome is mapped to 0 or 1.

The definitions of random variables $T$ and $S$ illustrate a general
rule: \emph{any function of random variables is also random variable}.

Are $D_1$ and $T$ independent?  That is, is the sum of the two dice
($T$) independent of the outcome of the first die ($D_1$)?  Intuitively,
the answer appears to be no!  To prove this let's use the second
definition of independence.  We must find $x_1, x_2
\in \reals$ such that $\pr{x_2} \neq 0$ and the condition in the
second definition does not hold.  For example, we can choose $x_1 = 2$
and $x_2 = 3$:
\[
\prcond{T = 2}{D_1 = 3} = 0 \neq \frac{1}{36} = \pr{T = 2}.
\]

The first probability is zero, since if we roll a three on the first
die ($D_1 = 3$), then there is no way that the sum of both dice is two
($T = 2$).  On the other hand, if we throw both dice, the probability
that the sum is two is $1/36$, since we could roll two ones.

Are $S$ and $D_1$ independent?  That is, is the probability that the sum
of both dice is seven ($S$) independent of the outcome of the first die
($D_1$)?  Once again, intuition suggests that the answer is ``no''.
Surprisingly, however, these two random variables \emph{are} actually
independent!

Proving that two random variables are independent requires some work.
Let's use the definition of independence based on conditional probability.
We must show that for all $x_1, x_2$ in $\reals$ such that $\pr{D_1 = x_2}
\neq 0$:
\[
\prcond{S = x_1}{D_1 = x_2} = \pr{S = x_1}.
\]

First, notice that we only have to show the equation for values of
$x_2$ such that $\pr{D_1 = x_2} \neq 0$.
This means we only have to consider $x_2$ equal to 1, 2, 3, 4, 5, or 6. 
If $x_1$ is neither 0 nor 1, then the condition holds trivially
because both sides are zero.  
So it remains to check the equation for the cases where $x_1 \in \{ 0,
1 \}$ and $x_2 \in \{ 1,2,3,4,5,6 \}$, that is, a total of $2 \cdot 6
= 12$ cases. 

Two observations make this easier.
First, there are $6 \cdot 6 = 36$ outcomes in the sample space for
this experiment.  The outcomes are equiprobable, so each outcome has
probability $1/36$.  The two dice sum to seven in six outcomes:
$1+6$, $2+5$, $3+4$, $4+3$, $5+2$, and $6+1$.  Therefore, the
probability of rolling a seven, $\pr{S = 1}$, is $6/36 =
1/6$.

Second, after we know the result of the first die, there is always
exactly one value for the second die that makes the sum seven.  For
example, if the first die is 2, then the sum is seven only if the
second die is a 5.  Therefore, $\prcond{S = 1}{D_1 = x_2} =
1/6$ for $x_2 = 1, 2, 3, 4, 5,$ or $6$.

These two observations establish the independence condition in six
cases:

\begin{eqnarray*}
\prcond{S = 1}{D_1 = 1} = & \cfrac{1}{6} & = \pr{S = 1} \\
\prcond{S = 1}{D_1 = 2} = & \cfrac{1}{6} & = \pr{S = 1} \\
                    &    \vdots   &  \\
\prcond{S = 1}{D_1 = 6} = & \cfrac{1}{6} & = \pr{S = 1}
\end{eqnarray*}

The remaining cases are complementary to the the first six.  For
example, we know that $\pr{S = 0} = 5/6$, since the
complementary event, $S = 1$, has probability $1/6$.

\begin{eqnarray*}
\prcond{S = 0}{D_1 = 1} = & \cfrac{5}{6} & = \pr{S = 0} \\
\prcond{S = 0}{D_1 = 2} = & \cfrac{5}{6} & = \pr{S = 0} \\
                    &    \vdots   &  \\
\prcond{S = 0}{D_1 = 6} = & \cfrac{5}{6} & = \pr{S = 0}
\end{eqnarray*}

We have established that the independence condition holds for all
necessary $x_1, x_2 \in \reals$.  This proves that $S$ and $D_1$ are
independent after all!

\subsubsection{Mutual Independence}

The definition of mutual independence for random variables is similar
to the definition for events.

\begin{definition}
Random variables $R_1, R_2, \ldots R_n$ are \emph{mutually independent}
if for all $x_1, x_2, \ldots x_n$, we have:

\[
\pr{R_1 = x_1 ] \land R_2 = x_2 \land \dots \land R_n = x_n} =
        \prod_{i=1}^{n} \pr{R_i = x_i}.
\]
\end{definition}

For example, consider the experiment of throwing three independent,
fair dice.  Random variable $R_1$ is the value of the first die.
Random variable $R_2$ is the sum of the first two dice, mod 6.  Random
variable $R_3$ is the sum of all three values, mod 6. These three
random variables are mutually independent. Can you prove it?

\section{Probability Distributions}

A random variable is a function from the sample space of an experiment
to the real numbers.  As a result, every random variable is bound up
in some particular experiment.  Often, however, we want to describe a
random variable independent of any experiment.  This consideration
motivates the notion of a \emph{probability distribution}.

%%\subsection{Definitions}

\begin{definition}
  The \emph{probability distribution function (pdf)} for a random
  variable $R : \sspace \to \reals$ is the function $f_R : \reals \to
  [0,1]$ defined by:
  \begin{eqnarray*}
    f_R(x) & = & \pr{R = x}
  \end{eqnarray*}
\end{definition}
The probability distribution function is also sometimes called the
point distribution function.  A consequence of this definition is that
$\sum_x f_R(x) = 1$, since we are summing the probabilities of all
outcomes in the sample space.
\begin{definition}
The \emph{cumulative distribution function} for a random variable $R:
\sspace \to \reals$ is the function $F_R: \reals \to [0,1]$ defined by:
\[
F_R(x) \eqdef \pr{R \leq x} = \sum_{y \leq x} f_R(y).
\]
\end{definition}
Note that neither the probability distribution function nor the
cumulative distribution function involves the sample space of an
experiment; both are functions from $\reals$ to $[0,1]$.  This
allows us to study random variables without reference to a particular
experiment.  In particular, we will look at three distributions today
and will see more in upcoming lectures.

\subsection{Bernoulli Distribution}

For our first example, let $B$ be a Bernoulli (indicator) random
variable that is 0 with probability $p$ and 1 with probability $1-p$.
We can compute the probability distribution function $f_B$ at 0 and 1 as
follows:
\begin{eqnarray*}
f_B(0) &=& \pr{R = 0} = p, \\
f_B(1) &=& \pr{R = 1} = 1-p.
\end{eqnarray*}

Similarly, we can compute the cumulative distribution function $F_B$:
\begin{eqnarray*}
F_B(0) &=& \pr{R \leq 0} = p, \\
F_B(1) &=& \pr{R \leq 1} = 1.
\end{eqnarray*}

\subsection{Uniform Distribution}

Now let $U$ be a random variable that is uniform on $\set{1,\dots, N}$.
That is, $U$ takes on value $k$ with probability $1/N$ for all $1 \leq k
\leq N$.  The probability distribution function and the cumulative
distribution function are:
\begin{eqnarray*}
f_U(k) &=& \pr{R = k} = \frac{1}{N}, \\
F_U(k) & =& \pr{R \leq k} = \frac{k}{N},\\
\end{eqnarray*}
for $1 \leq k \leq N$.

Uniform distributions are very common.  For example, the outcome of a
fair die is uniform on $\set{1,\dots, 6}$.
An example based on uniform distributions will be presented in the
next section.
But first, let's define the third distribution.

\subsection{Binomial Distribution}

We now introduce a third distribution, called the \emph{binomial
distribution}.  This is the most important and commonly occurring
distribution in computer science.  It is used to describe the
probabilities for all possible numbers of occurrences of independent
events, for example the number of faulty connections in a circuit
where the probabilities of failure for the individual connections are
independent. We will first define one important special case of the
binomial distribution and then define the general case.

\begin{definition}
The \emph{unbiased binomial distribution} is the function $f_n: \reals
\to [0,1]$ defined by

\[
f_n(k) = \binom{n}{k} \frac{1}{2^n}
\]
where $n$ is a positive integer parameter.
\end{definition}

\begin{definition}
The \emph{general binomial distribution} is the function $f_{n,p}: \reals
\to [0,1]$ defined by
\[
f_{n,p}(k) = \binom{n}{k} p^k (1-p)^{n-k}
\]
where parameter $n$ is a positive integer and $0 < p < 1$.
\end{definition}

In both definitions, if $k$ is not an integer $0, 1, \ldots, n$, then
$f$ is zero.

The unbiased binomial distribution is a special case of the general
binomial distribution where the parameter $p$ is equal to
$1/2$.

\section{Examples Involving Probability Distributions}

\subsection{Uniform Distributions and the Numbers Game}

%%\subsubsection{Rules of the Game}

Suppose we are given two envelopes, each containing an integer in the
range $0, 1, \ldots 100$, and we are guaranteed that the two integers are
distinct.  To win the game, we must determine which envelope contains the
larger number.  Our only advantage is that we are allowed to peek at the
number in one envelope; we can choose which one.  Can we devise a strategy
that gives us a better than 50\% chance of winning?

For example, suppose we are playing the game and are shown the two
envelopes.  Now we could guess randomly which envelope contains the
larger number, and not even bother to peek in one envelope.  With this
strategy, we have a 50\% chance of winning.

Suppose we try to do better.  We peek in the left envelope and see the
number 12.  Since 12 is a small number, we guess that the right envelope
probably contains the larger number.  Now, we might be correct.  On the
other hand, maybe the the person who wrote the numbers decided to be
tricky, and made \emph{both} numbers small!  Then our guess is not so
good!

An important point to remember is that the integers in the envelope might
\emph{not} be random.  We should assume that the person who writes the
numbers is trying to defeat us; she may use randomness or she may not---
we don't know!

\subsubsection{A Winning Strategy}

Amazingly, there is a strategy that wins more than 50\% of the time,
regardless of the integers in the envelopes.
Here is the basic idea:

Suppose we somehow knew a number $x$ between the larger and smaller
number.  Now we peek in an envelope and see some number.  If this
number is larger than $x$, then it must be the larger number.  If the
number we see is smaller than $x$, then the larger number must be in
the other envelope.  In other words, if we know $x$, then we are
guaranteed to win.

Of course, we do not know the number $x$, so what can we do?  Guess!

With some positive probability, we will guess $x$ correctly.  If we
guess correctly, then we are guaranteed to win!  If we guess
incorrectly, then we are no worse off than before; our chance of
winning is still 50\%.  Combining these two cases, our overall chance
of winning is better than 50\%!

This argument may sound implausible, but we can justify it rigorously.
The key is \emph{how} we guess the number $x$.  That is, what is the
probability distribution function of $x$?  The best answer turns out
to be a uniform distribution.

Let's describe the strategy more formally and then compute our chance
of winning.  Call the integers in the envelopes $y$ and $z$ and suppose
$y < z$.  For generality, suppose that each number is in the range $0,
1, \ldots, n$.  Above, we considered the case $n = 100$.  The number
we see by peeking is denoted $r$.  Here is the winning strategy:

\begin{enumerate}

\item Guess a number $x$ from the set
\[
\set{ 1-\frac{1}{2}, 2-\frac{1}{2}, \dots, n - \frac{1}{2} }
\]
with the uniform distribution.  That is, each value is selected with
probability $1/n$.  (We pick $x$ to be something-and-a-half simply to
avoid ties with integers in the envelopes.)

\item Peek into a random envelope.  We see a value $r$ that is either
$y$ or $z$.  Each envelope is chosen with probability $1/2$,
and the choice is independent of the number $x$.

\item Hope that $y < x < z$.  

\item If $r > x$, then guess that $r$ is the larger number, that is
the envelope we peeked into is the one that contains the larger
number. 
On the other hand, if $r < x$, then guess that the larger number is in
the other envelope.
\end{enumerate}

We can compute the probability of winning by using the tree diagram in
Figure~\ref{fig:game100} and the usual four-step method.
\begin{figure}
  \centerline{\resizebox{!}{2.5in}{\mbox{\includegraphics{figures/game100}}}}
  \caption{This is the tree diagram for the Numbers Game.}
  \label{fig:game100}
\end{figure}

%[[[Carl:  There are two typos in this figure.
%``too high'' should be changed to ``just right'', and vice versa.]]]

\emph{Step 1: Find the sample space.} We either choose $x$ too low, too
high, or just right.  Then we either choose $r=y$ or $r=z$.  As
indicated in the figure, this gives a total of six outcomes.

\emph{Step 2: Define events of interest.} We are interested in the
event that we correctly pick the larger number.  This event consists
of four outcomes, which are marked ``win'' in the figure.

\emph{Step 3: Compute outcome probabilities.} As usual, we first assign
probabilities to edges.  First, we guess $x$.  The probability that our
guess of $x$ is too low is $y/n$, the probability that our
guess is too high is $(n-z)/n$, and the probability of a correct
guess is $(z-y)/n$.  We then select an envelope; $r=y$ and $r=z$
occur with equal probability, independent of the choice of $x$.  The
probability of an outcome is the product of the probabilities on the
corresponding root-to-leaf path, as shown in the figure.

\emph{Step 4: Compute event probabilities.} The probability of winning
is the sum of the probabilities of the four winning outcomes.  This
gives:

\begin{eqnarray*}
\pr{\mbox{winning}}
        & = & \frac{y}{2n} + \frac{z-y}{2n} + \frac{z-y}{2n} + \frac{n-z}{2n}\\
        & = & \frac{n + z - y}{2n} \\
        & = & \frac{1}{2} + \frac{z - y}{2n} \\
        & \geq & \frac{1}{2} + \frac{1}{2n}
\end{eqnarray*}

In the final equality, we use the fact that the larger number $z$ is
at least 1 greater than the smaller number $y$, since they must be
distinct.

We conclude that the probability of winning with this strategy is at
least $1/2 + 1/2n$, regardless of the integers in the
envelopes!

For example, if the numbers in the envelopes are in the range $0,
\ldots 100$, then the probability of winning is at least $1/2 +
1/200 = 50.5\%$.  Even better, if the numbers are constrained to
be in the range $0, \ldots, 10$, then the probability of winning rises
to 55\%!  By Las Vegas standards, these are great odds!

\subsubsection{Optimality of the Winning Strategy}

What strategy should our opponent use in putting the numbers into the
envelopes?  That is, how can he ensure that we do not get, say, a 60\%
chance of winning?

Of course, our opponent could try to be clever, putting in two low
numbers and then two high numbers, etc.  But then there is no
guarantee that we will not catch on and start winning every time!

It turns out that our opponent should also use a randomized strategy
involving the uniform distribution.  In particular, he should choose $y$
from $\set{0,\dots n-1}$ uniformly, and then let $z = y+1$.  That is, he
should randomly choose a pair of consecutive integers like $(6,7)$ or
$(73, 74)$ with the uniform distribution.

\begin{claim}
If the opponent uses the strategy above, then $\pr{\mbox{we win}} \leq
1/2 + 1/2n$ for every strategy we can adopt.
\end{claim}
This claim is not hard to prove once we define just what a ``strategy''
can be, but we won't elaborate that here.

A consequence of the Claim is that both our strategy above of guessing $x$
and the opponent's strategy above are \emph{optimal}: we can win with
probability \emph{at least} $1/2 + 1/2n$ regardless of what our opponent
does, and our opponent can ensure that we win with probability \emph{at
most} $1/2 + 1/2n$ regardless of what we do.

\iffalse THE PRECISE STATEMENT AND PROOF OF THE CLAIM WAS LAST USED IN
SPRING 01 TUT12:

\ppart A \emph{randomized strategy} for you in this game is a function
that, for each number $i$, assigns a probability $p_i$ of switching {\em
given} that the number in the envelope you picked first was $i$.  Prove
that the strategy described in class for winning with probability at least
$1/2 + 1/2n$ is \emph{optimal} for you.  In particular, if David picks $i
\in [0,n-1]$ with uniform probability, and then places $i$ and $i+1$ in
each envelope with equal probability, then your probability of winning is
\emph{at most} $1/2 + 1/2n$.

\solution{Let $p_i$ denote the probability that you switch if you see the
number $i$.  Then, the probability that you win if David picks the pair
$(i,i+1)$ is the probability that you will see the smaller number and
switch, or that you will see the bigger number and stay.  Since the
probability of picking either number is $1/2$, the probability that you
win is
\[(1/2)p_i + (1/2)(1-p_{i+1}).
\]
Then the probability that you win is:
\[
\sum_{i=0}^{n-1} \frac{1}{n} \left(\frac{1}{2}p_i + \frac{1}{2}(1-p_{i+1})\right)
= \frac{1}{2} + \frac{1}{2n}\sum_{i=0}^{n-1} (p_i-p_{i+1})
= \frac{1}{2} + \frac{1}{2n} (p_0 - p_n) \leq \frac{1}{2} + \frac{1}{2n}
\]
}
\fi

\iffalse
Spring 01 tut12 also considers the case where our opponent is allowed to
put any non-negative integers into the envelopes; he can use numbers as
large as he likes. This case is more complicated, because the uniform
distribution on $\naturals$ is not even well-defined.  Nevertheless, there
is a strategy that guarantees a better than 50\% chance of winning
regardless of what numbers are in the envelopes!
\fi

\subsection{Binomial Distribution Examples}

\subsubsection{The Space Station \emph{Mir}}

The troubled space station \emph{Mir} has $n$ parts, each of which is
faulty with probability $p$.  Assume that faults occur independently, and
let the random variable $R$ be the number of faulty parts.  What is the
probability distribution of $R$, that is, what is $\pr{R = k}$?  We can
answer this with the usual four-step method, though we will not draw a
tree diagram.

\emph{Step 1: Find the sample space. } We can characterize Mir with a
string of $W$'s and $F$'s of length $n$.  A $W$ in the $i$-th position
indicates that the $i$-th part is working, and an $F$ indicates that
the $i$-th part is faulty.  Each such string is an outcome, and the
sample space $\sspace$ is the set of all $2^n$ such strings.

\emph{Step 2: Define events of interest. } We want to find the
probability that there are exactly $k$ faulty parts; that is, we are
interested in the event that $R = k$.

\emph{Step 3: Compute outcome probabilities. } Since faults occur
independently, the probability of an outcome such as $FWFWW$ is simply
a product such as $p(1-p)p(1-p)(1-p) = p^2(1-p)^3$.  Each $F$
contributes a $p$ term and each $W$ contributes a $(1-p)$ term.  In
general, the probability of an outcome with $k$ faulty parts and $n-k$
working parts is $p^k (1-p)^{n-k}$.

\emph{Step 4: Compute event probabilities. }

We can compute the probability that $k$ parts are faulty as follows:
\begin{eqnarray}
\pr{R = k} & = & \sum_{w \in [R=k]}
              p^k (1-p)^{n-k} \label{Rk.1}\\
& = & \mbox{(\# of length-$n$ strings with $k$ $F$'s)} \cdot p^k (1-p)^{n-k} \label{Rk.2}\\
& = & \binom{n}{k} p^k (1-p)^{n-k}\label{Rk.3}
\end{eqnarray}

Equation~(\ref{Rk.1}) uses the definition of the probability of an event.
Then~(\ref{Rk.2}) follows because all terms in the summation are equal,
and then~(\ref{Rk.3}) follows because there are $\dbinom{n}{k}$ strings of
length $n$ with $k$ occurrrences of $F$.

We can now see that the probability distribution function for the
number of faulty parts is precisely the general binomial distribution:
\[
f_R(k) \eqdef \pr{R = k} = \binom{n}{k} p^k (1-p)^{n-k} = f_{n, p}(k).
\]
As a ``sanity'' check, we should confirm that the sum, $\sum_k f_R(k)$, of
these probabilities is one.  This fact follows from the Binomial Theorem:
\[
1 = (p + (1 - p))^n = \sum_{k=0}^n \binom{n}{k}p^k(1-p)^{n-k}.
\]

In general, the binomial distribution arises whenever we have $n$
independent Bernoulli variables with the same distribution.  In this
case, the Bernoulli variables indicated whether a part was faulty or
not.  As another example, if we flip $n$ fair coins, then the number
of heads is an unbiased binomial distribution.

\subsubsection{Leader Election}

There are $n$ persons in a room. They wish to pick one of themselves as
their leader. They wish to do this in a fair and democratic way, so that
each and everyone has the same chance to be the leader. The scheme they
employ is for everyone to toss a coin. If exactly one person tosses a head
that person is elected the leader. If no persons or more than one person
tosses heads then they repeat the entire process.  

If the coins they use have probability $p$ of coming up heads then
what should $p$ be to maximize the probability of selecting a leader
in a given round? If $n$ coins are tossed then the probability of
having exactly one head is $\dbinom{n}{1} p(1-p)^{n-1}$. Notice that
if $p$ is too large then the likelihood of tossing multiple heads
becomes high, whereas if $p$ is too small then no one tosses a
head. By differentiating the probability w.r.t. $p$ and then equating
to $0,$ we find that the maximum occurs when $p = 1/n$. Hence, they
should use coins so that the probability of coming up heads is $1/n$.
When they use such coins then the probability of selecting a leader in
a given round is
\[
\binom{n}{1}\frac{1}{n}(1-\frac{1}{n})^{n-1} \sim 1/e.
\]

Leader election is a very common and important idea in distributed
computing. One example is how a set of devices that share a single
communication channel (whether wireless or an ethernet cable) may
decide which device gets to broadcast. If more than one device
broadcasts at the same time, the message will be lost. So the devices
keep trying to elect a leader and when they succeed, the leader gets
to broadcast on the channel.\footnote{Ethernet uses a variant of this
idea called \emph{binary exponential backoff}, where the bias $p$ of
the leader election coin is constantly adjusted because $n$ is
unknown. Probabilistic analysis is an important part of Network
theory.} An interesting question is: given some probability of
successfully choosing a leader in a given round, how many rounds do we
expect the devices have to try before they successfully send a
message? This type of question will be addressed in Section
\ref{shortcut}.


\subsection{The Shape of the Binomial Distribution}

The binomial distribution is somewhat complicated, and it's hard to see
its qualitative behavior for large $k$ and $n$.
\iffalse

More generally, we would like to know the shape of the binomial
distribution.  That is, what is the value of $f_{n, p}(k)$ for
particular $n$, $p$, and $k$?  Of course, we could simply plug in the
values of these variables, but a simpler, approximate expression would
be nice.

For example, if we flip 100 fair coins, what is the probability that
we get exactly 50 heads?  What is the probability that we get 25 heads
or fewer?

\fi

For example, suppose I flip $100$ coins.
\begin{itemize}
\item what is the most likely number of heads?
\item what the probability of exactly $50$ heads?
\item the probability of exactly $25$ heads?
\item the probability of less than $25$ heads?
\item probability of exactly $25$ heads, given at most $25$?
\end{itemize}

%vote: $1$, $.5$, $.1$, $.01$, $.000001$

To answer these questions, we will develop some closed form approximations
that will help us understand the properties of the distribution.  Let's
first consider the case when the coin is fair: the \emph{unbiased}
distribution, namely,
\[
f_{n,1/2}(k) \eqdef \binom{n}{k}2^{-n}.
\]

\subsubsection{The central term}

Where is $f_{n,p}(k)$ maximized?  We saw in
\hyperref{http://theory.lcs.mit.edu/classes/6.042/fall01/handouts/tutsol11.pdf}
{binomial}{max-term}{tutorial} that
\iffalse
\begin{eqnarray*}
f_{n,p}(k)/f_{n.p}(k-1) &=& \frac{n-k+1)p}{k(1-p)}\\
&=& 1+\frac{(n+1)p-k}{k(1-p)}
\end{eqnarray*}
Therefore,
\fi
$f_{n,p}(k)$ increases until $k=p(n+1)$, and decreases after.
So for $p=1/2$, the central term is essentially at $k=n/2$.  Now, by
Stirling's formula we have
\[
\binom{n}{n/2} = \frac{n!}{\cfrac{n}{2}!\cfrac{n}{2}!} \sim 
\frac{\sqrt{2\pi n}\left(\cfrac{n}{e}\right)^n}{\left(\sqrt{\pi
    n}\left(\cfrac{n}{2e}\right)^{n/2}\right)^2} =
\sqrt{\frac{2}{\pi n}}2^n.
\]
So 
\begin{equation}\label{unbiased central term}
f_{n,1/2}(n/2) \sim \sqrt{\frac{2}{\pi n}}.
\end{equation}
Note this is an asymptotic bound.  For $n=100$ (our question about coins)
we have $1/\sqrt{50 \pi} \approx 0.079788$, so the probability of
throwing exactly 50 heads in 100 tosses is about 8\%.  In fact, the bound
given above is very close to the true value; in this case, the exact
answer is $0.079589\ldots$.  In general, to determine the accuracy of this
estimate we'll need to use the form of Stirling's formula that gives upper
and lower bounds, which we consider below.

\subsubsection{The tails}

We can generalize the estimate of the central term at $(1/2)n$ to terms at
factors other than 1/2.  Namely, we estimate $f_{n,1/2}(\alpha n)$ when
for $\alpha \neq 1/2$ by first estimating the binomial coefficient
\begin{lemma*}
\begin{equation}\label{binom-est}
\binom{n}{\alpha n} \sim 2^{nH(\alpha)}/\sqrt{2\pi \alpha(1-\alpha)n}
\end{equation}
where
\[
H(\alpha) \eqdef - (\alpha\log_2 \alpha + (1-\alpha)\log_2 (1-\alpha)).
\]
\end{lemma*}
\begin{proof}

\begin{eqnarray*}
\binom{n}{\alpha n} &\eqdef& \frac{n!}{(\alpha n)!((1-\alpha) n)!}\\ 
  &\sim& \frac{\sqrt{2\pi n}\left(\cfrac{n}{e}\right)^n}
         {\sqrt{2\pi \alpha n}\left(\cfrac{\alpha n}{e}\right)^{\alpha n}
          \sqrt{2\pi (1-\alpha) n}\left(\cfrac{(1-\alpha) n}{e}\right)^{(1-\alpha)n}}\\
&=& \left(\frac{1}{\alpha^\alpha(1-\alpha)^{(1-\alpha)}}\right)^n/\sqrt{2\pi \alpha(1-\alpha)n} \\
 &=&     2^{-(\alpha\log_2 \alpha+(1-\alpha)\log_2 (1-\alpha))n}/\sqrt{2\pi \alpha(1-\alpha)n} \\
  &=& 2^{nH(\alpha)}/\sqrt{2\pi \alpha(1-\alpha)n}.
\end{eqnarray*}
\end{proof}

$H(\alpha)$ is only defined for $0 \le \alpha \le 1$.  Its values lie
between 0 and 1, and its maximum is $H(1/2) =1$.

                                % 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(220.0,113.0){\rule[-0.200pt]{292.934pt}{0.400pt}}
  \put(220.0,113.0){\rule[-0.200pt]{0.400pt}{184.048pt}}
  \put(220.0,113.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
  \put(198,113){\makebox(0,0)[r]{0}}
  \put(1416.0,113.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
  \put(220.0,266.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
  \put(198,266){\makebox(0,0)[r]{0.2}}
  \put(1416.0,266.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
  \put(220.0,419.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
  \put(198,419){\makebox(0,0)[r]{0.4}}
  \put(1416.0,419.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
  \put(220.0,571.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
  \put(198,571){\makebox(0,0)[r]{0.6}}
  \put(1416.0,571.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
  \put(220.0,724.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
  \put(198,724){\makebox(0,0)[r]{0.8}}
  \put(1416.0,724.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
  \put(220.0,877.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
  \put(198,877){\makebox(0,0)[r]{1}}
  \put(1416.0,877.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
  \put(220.0,113.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
  \put(220,68){\makebox(0,0){0}}
  \put(220.0,857.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
  \put(463.0,113.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
  \put(463,68){\makebox(0,0){0.2}}
  \put(463.0,857.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
  \put(706.0,113.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
  \put(706,68){\makebox(0,0){0.4}}
  \put(706.0,857.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
  \put(950.0,113.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
  \put(950,68){\makebox(0,0){0.6}}
  \put(950.0,857.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
  \put(1193.0,113.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
  \put(1193,68){\makebox(0,0){0.8}}
  \put(1193.0,857.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
  \put(1436.0,113.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
  \put(1436,68){\makebox(0,0){1}}
  \put(1436.0,857.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
  \put(220.0,113.0){\rule[-0.200pt]{292.934pt}{0.400pt}}
  \put(1436.0,113.0){\rule[-0.200pt]{0.400pt}{184.048pt}}
  \put(220.0,877.0){\rule[-0.200pt]{292.934pt}{0.400pt}}
  \put(45,495){\makebox(0,0){$H(\alpha)$}}
  \put(828,23){\makebox(0,0){$\alpha$}}
  \put(220.0,113.0){\rule[-0.200pt]{0.400pt}{184.048pt}}
  \put(232,175){\usebox{\plotpoint}}
  \multiput(232.58,175.00)(0.493,1.845){23}{\rule{0.119pt}{1.546pt}}
  \multiput(231.17,175.00)(13.000,43.791){2}{\rule{0.400pt}{0.773pt}}
  \multiput(245.58,222.00)(0.492,1.746){21}{\rule{0.119pt}{1.467pt}}
  \multiput(244.17,222.00)(12.000,37.956){2}{\rule{0.400pt}{0.733pt}}
  \multiput(257.58,263.00)(0.492,1.573){21}{\rule{0.119pt}{1.333pt}}
  \multiput(256.17,263.00)(12.000,34.233){2}{\rule{0.400pt}{0.667pt}}
  \multiput(269.58,300.00)(0.492,1.401){21}{\rule{0.119pt}{1.200pt}}
  \multiput(268.17,300.00)(12.000,30.509){2}{\rule{0.400pt}{0.600pt}}
  \multiput(281.58,333.00)(0.493,1.250){23}{\rule{0.119pt}{1.085pt}}
  \multiput(280.17,333.00)(13.000,29.749){2}{\rule{0.400pt}{0.542pt}}
  \multiput(294.58,365.00)(0.492,1.272){21}{\rule{0.119pt}{1.100pt}}
  \multiput(293.17,365.00)(12.000,27.717){2}{\rule{0.400pt}{0.550pt}}
  \multiput(306.58,395.00)(0.492,1.142){21}{\rule{0.119pt}{1.000pt}}
  \multiput(305.17,395.00)(12.000,24.924){2}{\rule{0.400pt}{0.500pt}}
  \multiput(318.58,422.00)(0.493,1.052){23}{\rule{0.119pt}{0.931pt}}
  \multiput(317.17,422.00)(13.000,25.068){2}{\rule{0.400pt}{0.465pt}}
  \multiput(331.58,449.00)(0.492,1.056){21}{\rule{0.119pt}{0.933pt}}
  \multiput(330.17,449.00)(12.000,23.063){2}{\rule{0.400pt}{0.467pt}}
  \multiput(343.58,474.00)(0.492,0.970){21}{\rule{0.119pt}{0.867pt}}
  \multiput(342.17,474.00)(12.000,21.201){2}{\rule{0.400pt}{0.433pt}}
  \multiput(355.58,497.00)(0.492,0.970){21}{\rule{0.119pt}{0.867pt}}
  \multiput(354.17,497.00)(12.000,21.201){2}{\rule{0.400pt}{0.433pt}}
  \multiput(367.58,520.00)(0.493,0.853){23}{\rule{0.119pt}{0.777pt}}
  \multiput(366.17,520.00)(13.000,20.387){2}{\rule{0.400pt}{0.388pt}}
  \multiput(380.58,542.00)(0.492,0.841){21}{\rule{0.119pt}{0.767pt}}
  \multiput(379.17,542.00)(12.000,18.409){2}{\rule{0.400pt}{0.383pt}}
  \multiput(392.58,562.00)(0.492,0.841){21}{\rule{0.119pt}{0.767pt}}
  \multiput(391.17,562.00)(12.000,18.409){2}{\rule{0.400pt}{0.383pt}}
  \multiput(404.58,582.00)(0.493,0.734){23}{\rule{0.119pt}{0.685pt}}
  \multiput(403.17,582.00)(13.000,17.579){2}{\rule{0.400pt}{0.342pt}}
  \multiput(417.58,601.00)(0.492,0.712){21}{\rule{0.119pt}{0.667pt}}
  \multiput(416.17,601.00)(12.000,15.616){2}{\rule{0.400pt}{0.333pt}}
  \multiput(429.58,618.00)(0.492,0.755){21}{\rule{0.119pt}{0.700pt}}
  \multiput(428.17,618.00)(12.000,16.547){2}{\rule{0.400pt}{0.350pt}}
  \multiput(441.58,636.00)(0.492,0.669){21}{\rule{0.119pt}{0.633pt}}
  \multiput(440.17,636.00)(12.000,14.685){2}{\rule{0.400pt}{0.317pt}}
  \multiput(453.58,652.00)(0.493,0.616){23}{\rule{0.119pt}{0.592pt}}
  \multiput(452.17,652.00)(13.000,14.771){2}{\rule{0.400pt}{0.296pt}}
  \multiput(466.58,668.00)(0.492,0.625){21}{\rule{0.119pt}{0.600pt}}
  \multiput(465.17,668.00)(12.000,13.755){2}{\rule{0.400pt}{0.300pt}}
  \multiput(478.58,683.00)(0.492,0.582){21}{\rule{0.119pt}{0.567pt}}
  \multiput(477.17,683.00)(12.000,12.824){2}{\rule{0.400pt}{0.283pt}}
  \multiput(490.00,697.58)(0.497,0.493){23}{\rule{0.500pt}{0.119pt}}
  \multiput(490.00,696.17)(11.962,13.000){2}{\rule{0.250pt}{0.400pt}}
  \multiput(503.58,710.00)(0.492,0.539){21}{\rule{0.119pt}{0.533pt}}
  \multiput(502.17,710.00)(12.000,11.893){2}{\rule{0.400pt}{0.267pt}}
  \multiput(515.58,723.00)(0.492,0.539){21}{\rule{0.119pt}{0.533pt}}
  \multiput(514.17,723.00)(12.000,11.893){2}{\rule{0.400pt}{0.267pt}}
  \multiput(527.00,736.58)(0.496,0.492){21}{\rule{0.500pt}{0.119pt}}
  \multiput(527.00,735.17)(10.962,12.000){2}{\rule{0.250pt}{0.400pt}}
  \multiput(539.00,748.58)(0.590,0.492){19}{\rule{0.573pt}{0.118pt}}
  \multiput(539.00,747.17)(11.811,11.000){2}{\rule{0.286pt}{0.400pt}}
  \multiput(552.00,759.58)(0.600,0.491){17}{\rule{0.580pt}{0.118pt}}
  \multiput(552.00,758.17)(10.796,10.000){2}{\rule{0.290pt}{0.400pt}}
  \multiput(564.00,769.58)(0.543,0.492){19}{\rule{0.536pt}{0.118pt}}
  \multiput(564.00,768.17)(10.887,11.000){2}{\rule{0.268pt}{0.400pt}}
  \multiput(576.00,780.59)(0.669,0.489){15}{\rule{0.633pt}{0.118pt}}
  \multiput(576.00,779.17)(10.685,9.000){2}{\rule{0.317pt}{0.400pt}}
  \multiput(588.00,789.59)(0.728,0.489){15}{\rule{0.678pt}{0.118pt}}
  \multiput(588.00,788.17)(11.593,9.000){2}{\rule{0.339pt}{0.400pt}}
  \multiput(601.00,798.59)(0.669,0.489){15}{\rule{0.633pt}{0.118pt}}
  \multiput(601.00,797.17)(10.685,9.000){2}{\rule{0.317pt}{0.400pt}}
  \multiput(613.00,807.59)(0.758,0.488){13}{\rule{0.700pt}{0.117pt}}
  \multiput(613.00,806.17)(10.547,8.000){2}{\rule{0.350pt}{0.400pt}}
  \multiput(625.00,815.59)(0.950,0.485){11}{\rule{0.843pt}{0.117pt}}
  \multiput(625.00,814.17)(11.251,7.000){2}{\rule{0.421pt}{0.400pt}}
  \multiput(638.00,822.59)(0.874,0.485){11}{\rule{0.786pt}{0.117pt}}
  \multiput(638.00,821.17)(10.369,7.000){2}{\rule{0.393pt}{0.400pt}}
  \multiput(650.00,829.59)(1.033,0.482){9}{\rule{0.900pt}{0.116pt}}
  \multiput(650.00,828.17)(10.132,6.000){2}{\rule{0.450pt}{0.400pt}}
  \multiput(662.00,835.59)(1.033,0.482){9}{\rule{0.900pt}{0.116pt}}
  \multiput(662.00,834.17)(10.132,6.000){2}{\rule{0.450pt}{0.400pt}}
  \multiput(674.00,841.59)(1.123,0.482){9}{\rule{0.967pt}{0.116pt}}
  \multiput(674.00,840.17)(10.994,6.000){2}{\rule{0.483pt}{0.400pt}}
  \multiput(687.00,847.59)(1.267,0.477){7}{\rule{1.060pt}{0.115pt}}
  \multiput(687.00,846.17)(9.800,5.000){2}{\rule{0.530pt}{0.400pt}}
  \multiput(699.00,852.59)(1.267,0.477){7}{\rule{1.060pt}{0.115pt}}
  \multiput(699.00,851.17)(9.800,5.000){2}{\rule{0.530pt}{0.400pt}}
  \multiput(711.00,857.60)(1.797,0.468){5}{\rule{1.400pt}{0.113pt}}
  \multiput(711.00,856.17)(10.094,4.000){2}{\rule{0.700pt}{0.400pt}}
  \multiput(724.00,861.61)(2.472,0.447){3}{\rule{1.700pt}{0.108pt}}
  \multiput(724.00,860.17)(8.472,3.000){2}{\rule{0.850pt}{0.400pt}}
  \multiput(736.00,864.61)(2.472,0.447){3}{\rule{1.700pt}{0.108pt}}
  \multiput(736.00,863.17)(8.472,3.000){2}{\rule{0.850pt}{0.400pt}}
  \multiput(748.00,867.61)(2.472,0.447){3}{\rule{1.700pt}{0.108pt}}
  \multiput(748.00,866.17)(8.472,3.000){2}{\rule{0.850pt}{0.400pt}}
  \put(760,870.17){\rule{2.700pt}{0.400pt}}
  \multiput(760.00,869.17)(7.396,2.000){2}{\rule{1.350pt}{0.400pt}}
  \put(773,872.17){\rule{2.500pt}{0.400pt}}
  \multiput(773.00,871.17)(6.811,2.000){2}{\rule{1.250pt}{0.400pt}}
  \put(785,874.17){\rule{2.500pt}{0.400pt}}
  \multiput(785.00,873.17)(6.811,2.000){2}{\rule{1.250pt}{0.400pt}}
  \put(810,875.67){\rule{2.891pt}{0.400pt}}
  \multiput(810.00,875.17)(6.000,1.000){2}{\rule{1.445pt}{0.400pt}}
  \put(797.0,876.0){\rule[-0.200pt]{3.132pt}{0.400pt}}
  \put(834,875.67){\rule{2.891pt}{0.400pt}}
  \multiput(834.00,876.17)(6.000,-1.000){2}{\rule{1.445pt}{0.400pt}}
  \put(822.0,877.0){\rule[-0.200pt]{2.891pt}{0.400pt}}
  \put(859,874.17){\rule{2.500pt}{0.400pt}}
  \multiput(859.00,875.17)(6.811,-2.000){2}{\rule{1.250pt}{0.400pt}}
  \put(871,872.17){\rule{2.500pt}{0.400pt}}
  \multiput(871.00,873.17)(6.811,-2.000){2}{\rule{1.250pt}{0.400pt}}
  \put(883,870.17){\rule{2.700pt}{0.400pt}}
  \multiput(883.00,871.17)(7.396,-2.000){2}{\rule{1.350pt}{0.400pt}}
  \multiput(896.00,868.95)(2.472,-0.447){3}{\rule{1.700pt}{0.108pt}}
  \multiput(896.00,869.17)(8.472,-3.000){2}{\rule{0.850pt}{0.400pt}}
  \multiput(908.00,865.95)(2.472,-0.447){3}{\rule{1.700pt}{0.108pt}}
  \multiput(908.00,866.17)(8.472,-3.000){2}{\rule{0.850pt}{0.400pt}}
  \multiput(920.00,862.95)(2.472,-0.447){3}{\rule{1.700pt}{0.108pt}}
  \multiput(920.00,863.17)(8.472,-3.000){2}{\rule{0.850pt}{0.400pt}}
  \multiput(932.00,859.94)(1.797,-0.468){5}{\rule{1.400pt}{0.113pt}}
  \multiput(932.00,860.17)(10.094,-4.000){2}{\rule{0.700pt}{0.400pt}}
  \multiput(945.00,855.93)(1.267,-0.477){7}{\rule{1.060pt}{0.115pt}}
  \multiput(945.00,856.17)(9.800,-5.000){2}{\rule{0.530pt}{0.400pt}}
  \multiput(957.00,850.93)(1.267,-0.477){7}{\rule{1.060pt}{0.115pt}}
  \multiput(957.00,851.17)(9.800,-5.000){2}{\rule{0.530pt}{0.400pt}}
  \multiput(969.00,845.93)(1.123,-0.482){9}{\rule{0.967pt}{0.116pt}}
  \multiput(969.00,846.17)(10.994,-6.000){2}{\rule{0.483pt}{0.400pt}}
  \multiput(982.00,839.93)(1.033,-0.482){9}{\rule{0.900pt}{0.116pt}}
  \multiput(982.00,840.17)(10.132,-6.000){2}{\rule{0.450pt}{0.400pt}}
  \multiput(994.00,833.93)(1.033,-0.482){9}{\rule{0.900pt}{0.116pt}}
  \multiput(994.00,834.17)(10.132,-6.000){2}{\rule{0.450pt}{0.400pt}}
  \multiput(1006.00,827.93)(0.874,-0.485){11}{\rule{0.786pt}{0.117pt}}
  \multiput(1006.00,828.17)(10.369,-7.000){2}{\rule{0.393pt}{0.400pt}}
  \multiput(1018.00,820.93)(0.950,-0.485){11}{\rule{0.843pt}{0.117pt}}
  \multiput(1018.00,821.17)(11.251,-7.000){2}{\rule{0.421pt}{0.400pt}}
  \multiput(1031.00,813.93)(0.758,-0.488){13}{\rule{0.700pt}{0.117pt}}
  \multiput(1031.00,814.17)(10.547,-8.000){2}{\rule{0.350pt}{0.400pt}}
  \multiput(1043.00,805.93)(0.669,-0.489){15}{\rule{0.633pt}{0.118pt}}
  \multiput(1043.00,806.17)(10.685,-9.000){2}{\rule{0.317pt}{0.400pt}}
  \multiput(1055.00,796.93)(0.728,-0.489){15}{\rule{0.678pt}{0.118pt}}
  \multiput(1055.00,797.17)(11.593,-9.000){2}{\rule{0.339pt}{0.400pt}}
  \multiput(1068.00,787.93)(0.669,-0.489){15}{\rule{0.633pt}{0.118pt}}
  \multiput(1068.00,788.17)(10.685,-9.000){2}{\rule{0.317pt}{0.400pt}}
  \multiput(1080.00,778.92)(0.543,-0.492){19}{\rule{0.536pt}{0.118pt}}
  \multiput(1080.00,779.17)(10.887,-11.000){2}{\rule{0.268pt}{0.400pt}}
  \multiput(1092.00,767.92)(0.600,-0.491){17}{\rule{0.580pt}{0.118pt}}
  \multiput(1092.00,768.17)(10.796,-10.000){2}{\rule{0.290pt}{0.400pt}}
  \multiput(1104.00,757.92)(0.590,-0.492){19}{\rule{0.573pt}{0.118pt}}
  \multiput(1104.00,758.17)(11.811,-11.000){2}{\rule{0.286pt}{0.400pt}}
  \multiput(1117.00,746.92)(0.496,-0.492){21}{\rule{0.500pt}{0.119pt}}
  \multiput(1117.00,747.17)(10.962,-12.000){2}{\rule{0.250pt}{0.400pt}}
  \multiput(1129.58,733.79)(0.492,-0.539){21}{\rule{0.119pt}{0.533pt}}
  \multiput(1128.17,734.89)(12.000,-11.893){2}{\rule{0.400pt}{0.267pt}}
  \multiput(1141.58,720.79)(0.492,-0.539){21}{\rule{0.119pt}{0.533pt}}
  \multiput(1140.17,721.89)(12.000,-11.893){2}{\rule{0.400pt}{0.267pt}}
  \multiput(1153.00,708.92)(0.497,-0.493){23}{\rule{0.500pt}{0.119pt}}
  \multiput(1153.00,709.17)(11.962,-13.000){2}{\rule{0.250pt}{0.400pt}}
  \multiput(1166.58,694.65)(0.492,-0.582){21}{\rule{0.119pt}{0.567pt}}
  \multiput(1165.17,695.82)(12.000,-12.824){2}{\rule{0.400pt}{0.283pt}}
  \multiput(1178.58,680.51)(0.492,-0.625){21}{\rule{0.119pt}{0.600pt}}
  \multiput(1177.17,681.75)(12.000,-13.755){2}{\rule{0.400pt}{0.300pt}}
  \multiput(1190.58,665.54)(0.493,-0.616){23}{\rule{0.119pt}{0.592pt}}
  \multiput(1189.17,666.77)(13.000,-14.771){2}{\rule{0.400pt}{0.296pt}}
  \multiput(1203.58,649.37)(0.492,-0.669){21}{\rule{0.119pt}{0.633pt}}
  \multiput(1202.17,650.69)(12.000,-14.685){2}{\rule{0.400pt}{0.317pt}}
  \multiput(1215.58,633.09)(0.492,-0.755){21}{\rule{0.119pt}{0.700pt}}
  \multiput(1214.17,634.55)(12.000,-16.547){2}{\rule{0.400pt}{0.350pt}}
  \multiput(1227.58,615.23)(0.492,-0.712){21}{\rule{0.119pt}{0.667pt}}
  \multiput(1226.17,616.62)(12.000,-15.616){2}{\rule{0.400pt}{0.333pt}}
  \multiput(1239.58,598.16)(0.493,-0.734){23}{\rule{0.119pt}{0.685pt}}
  \multiput(1238.17,599.58)(13.000,-17.579){2}{\rule{0.400pt}{0.342pt}}
  \multiput(1252.58,578.82)(0.492,-0.841){21}{\rule{0.119pt}{0.767pt}}
  \multiput(1251.17,580.41)(12.000,-18.409){2}{\rule{0.400pt}{0.383pt}}
  \multiput(1264.58,558.82)(0.492,-0.841){21}{\rule{0.119pt}{0.767pt}}
  \multiput(1263.17,560.41)(12.000,-18.409){2}{\rule{0.400pt}{0.383pt}}
  \multiput(1276.58,538.77)(0.493,-0.853){23}{\rule{0.119pt}{0.777pt}}
  \multiput(1275.17,540.39)(13.000,-20.387){2}{\rule{0.400pt}{0.388pt}}
  \multiput(1289.58,516.40)(0.492,-0.970){21}{\rule{0.119pt}{0.867pt}}
  \multiput(1288.17,518.20)(12.000,-21.201){2}{\rule{0.400pt}{0.433pt}}
  \multiput(1301.58,493.40)(0.492,-0.970){21}{\rule{0.119pt}{0.867pt}}
  \multiput(1300.17,495.20)(12.000,-21.201){2}{\rule{0.400pt}{0.433pt}}
  \multiput(1313.58,470.13)(0.492,-1.056){21}{\rule{0.119pt}{0.933pt}}
  \multiput(1312.17,472.06)(12.000,-23.063){2}{\rule{0.400pt}{0.467pt}}
  \multiput(1325.58,445.14)(0.493,-1.052){23}{\rule{0.119pt}{0.931pt}}
  \multiput(1324.17,447.07)(13.000,-25.068){2}{\rule{0.400pt}{0.465pt}}
  \multiput(1338.58,417.85)(0.492,-1.142){21}{\rule{0.119pt}{1.000pt}}
  \multiput(1337.17,419.92)(12.000,-24.924){2}{\rule{0.400pt}{0.500pt}}
  \multiput(1350.58,390.43)(0.492,-1.272){21}{\rule{0.119pt}{1.100pt}}
  \multiput(1349.17,392.72)(12.000,-27.717){2}{\rule{0.400pt}{0.550pt}}
  \multiput(1362.58,360.50)(0.493,-1.250){23}{\rule{0.119pt}{1.085pt}}
  \multiput(1361.17,362.75)(13.000,-29.749){2}{\rule{0.400pt}{0.542pt}}
  \multiput(1375.58,328.02)(0.492,-1.401){21}{\rule{0.119pt}{1.200pt}}
  \multiput(1374.17,330.51)(12.000,-30.509){2}{\rule{0.400pt}{0.600pt}}
  \multiput(1387.58,294.47)(0.492,-1.573){21}{\rule{0.119pt}{1.333pt}}
  \multiput(1386.17,297.23)(12.000,-34.233){2}{\rule{0.400pt}{0.667pt}}
  \multiput(1399.58,256.91)(0.492,-1.746){21}{\rule{0.119pt}{1.467pt}}
  \multiput(1398.17,259.96)(12.000,-37.956){2}{\rule{0.400pt}{0.733pt}}
  \multiput(1411.58,215.58)(0.493,-1.845){23}{\rule{0.119pt}{1.546pt}}
  \multiput(1410.17,218.79)(13.000,-43.791){2}{\rule{0.400pt}{0.773pt}}
  \put(846.0,876.0){\rule[-0.200pt]{3.132pt}{0.400pt}}
\end{picture}

$H(\alpha)$ is the known as the \emph{entropy function}.  It plays an
important role in thermodynamics and in information theory.  For example,
it arises in the study of how much information is carried in a binary
string with a fraction $\alpha$ of the bits set to one.  Since there are
$\dbinom{n}{\alpha n}$ such $n$-bit strings, they can be numbered using
$nH(\alpha) + o(\log n)$-bit binary numbers.  So the information carried by
these $n$-bits can be ``compressed'' into $nH(\alpha)$ bits.  This observation
underlies information-theoretic bounds on the rate at which bits can be
reliably communicated over an unreliable communication channel.

So with this estimate~(\ref{binom-est}) of the binomial coefficient, we
conclude
\begin{equation}\label{unbiased alpha term}
f_{n,1/2}(\alpha n) = \binom{n}{\alpha n}2^{-n} \sim
2^{-n(1 - H(\alpha))}/\sqrt{2\pi \alpha(1-\alpha)n}.
\end{equation}

For $\alpha = 1/2$, this approximation~(\ref{unbiased alpha term}) matches
our estimate~(\ref{unbiased central term}) above.  But now we can also
estimate the probability of throwing exactly 25 heads in 100 tosses.  In
this case, we substitute $n = 100$, and $\alpha = 1/4$ into~(\ref{unbiased
alpha term}) and obtain $1.913 \cdot 10^{-7}$.  The odds are less than 1
in 5 million for throwing exactly 25 heads in 100 tosses!

The estimate in~(\ref{unbiased alpha term}) also provides some important
qualitative understanding of the binomial distribution.  Note that for
$\alpha \neq 1/2$, we have $1- H(\alpha) > 0$, so
\[
f_{n,1/2}(\alpha n) = O(2^{-\epsilon n})
\]
for $ 1 - H(\alpha) > \epsilon > 0$.  In other words, for $\alpha \neq 1/2$,
\begin{center}
\textbf{$f_{n,1/2}(\alpha n)$ is exponentially small in $n$.}
\end{center}
This means that as $n$ increases, the values away from $n/2$ rapidly
become less likely, and the likely values concentrate more and more
tightly around $n/2$.

\iffalse

\begin{example}

$$ \binom{n}{n/4} \sim \sqrt{\frac{8}{3\pi n}}2^{0.811n} $$

$$ f_{n,1/2}(n/4) \sim \sqrt{\frac{8}{3\pi n}}2^{-0.189n} \;\;
\text{exponetially small} $$

Returning to our beginning questions, 
$$ Pr[\mbox{25 heads}] = f_{100,1/2}(25) \approx 1.88 \times 10^{-7} $$

\end{example}

\subsubsection{Cumulative Distribution}

For a random variable $R$, the {\em cumulative distribution function}
$F_R(k) = \Pr[R \le k]$.

Since $f_{n,1/2}(k)$ is increasing with $k<n/2$, we can bound the
probability $F_R(25) \le 25\cdot f_{n,1/2}(25)$.  But we can do better.

Let $k = \alpha n$ where $\alpha \le 1/2$. Then
%\begin{align*}
%Pr[R\leq \alpha n]
%  &= \sum_{i=0}^{\alpha n} Pr[R=i] \\
%  &= \frac{1}{2^n}\left[ \binom{n}{\alpha n}+\binom{n}{\alpha n - 1}
%  \cdots \binom{n}{0} \right]
%\end{align*}
\begin{eqnarray*}
Pr[R\leq \alpha n]
  &=& \sum_{i=0}^{\alpha n} Pr[R=i] \\
  &=& \frac{1}{2^n}\left[ \binom{n}{\alpha n}+\binom{n}{\alpha n - 1}
  \cdots \binom{n}{0} \right]
\end{eqnarray*}

The term in brackets we can bound by a geometric series by looking
at the ratio of consecutive terms:
%\begin{align*}
%\frac{\binom{n}{r-1}}{\binom{n}{r}} &=
%\frac{\frac{n!}{(r-1)!(n-r+1)!}}{\frac{n!}{r!(n-r)!}}\\
%&= \frac{r}{n-r+1}\\
%&\leq \frac{\alpha n}{n- \alpha n + 1}\\
%&\leq \frac{\alpha}{1-\alpha} \\
%\intertext{
%(Note that we used $r \leq \alpha n$.)
%Therefore,}
%\binom{n}{\alpha n - r} &\le
%\left(\frac{\alpha}{1-\alpha}\right)^r\binom{n}{\alpha n}
%\end{align*}
\begin{eqnarray*}
\frac{\binom{n}{r-1}}{\binom{n}{r}} &=&
\frac{\frac{n!}{(r-1)!(n-r+1)!}}{\frac{n!}{r!(n-r)!}}\\
&=& \frac{r}{n-r+1}\\
&\leq& \frac{\alpha n}{n- \alpha n + 1}\\
&\leq& \frac{\alpha}{1-\alpha}
\end{eqnarray*}
(Note that we used $r \leq \alpha n$.)
Therefore,
\[
\binom{n}{\alpha n - r} \le
\left(\frac{\alpha}{1-\alpha}\right)^r\binom{n}{\alpha n}
\]

Plugging in, we find
%\begin{align*}
%Pr[R\leq \alpha n]
%  &\leq 2^{-n}\left[ \binom{n}{\alpha n} +
%  \frac{\alpha}{1-\alpha}\binom{n}{\alpha n} +
%  \left(\frac{\alpha}{1-\alpha}\right)^2\binom{n}{\alpha n}+ \cdots
%    + \left(\frac{\alpha}{1-\alpha}\right)^{\alpha n}\binom{n}{\alpha
%      n} \right] \\
%    &\leq 2^{-n}\binom{n}{\alpha n}\frac{1}{1-\frac{\alpha}{1-\alpha}}
%    \;\; (\alpha < 1/2 \Rightarrow \frac{\alpha}{1-\alpha}<1) \\
%    &= 2^{-n}\binom{n}{\alpha n}\frac{1-\alpha}{1-2\alpha}
%\end{align*}
\begin{eqnarray*}
Pr[R\leq \alpha n]
  &\leq& 2^{-n}\left[ \binom{n}{\alpha n} +
  \frac{\alpha}{1-\alpha}\binom{n}{\alpha n} +
  \left(\frac{\alpha}{1-\alpha}\right)^2\binom{n}{\alpha n}+ \cdots
    + \left(\frac{\alpha}{1-\alpha}\right)^{\alpha n}\binom{n}{\alpha
      n} \right] \\
    &\leq& 2^{-n}\binom{n}{\alpha n}\frac{1}{1-\frac{\alpha}{1-\alpha}}
    \;\; (\alpha < 1/2 \Rightarrow \frac{\alpha}{1-\alpha}<1) \\
    &=& 2^{-n}\binom{n}{\alpha n}\frac{1-\alpha}{1-2\alpha}
\end{eqnarray*}

Notice that $\frac{1-\alpha}{1-2\alpha}$ is constant!
$$ Pr[\leq 25\mbox{ heads}] \; (n=100, \alpha=1/4) \; = (1.88\times
10^{-7})\frac{3/4}{1/2}  $$

For $\beta = o(\sqrt{n}), f(n/2-\beta\sqrt{n}) \sim \sqrt{\frac{2}{\pi
    n}}e^{-2\beta^2}$.

Furthermore,
%\begin{align*}
%\Pr[\le 24\mbox{ heads}] &\le \frac{\alpha}{1-\alpha}\Pr[\le 25\mbox{
%  heads}]\\
%\intertext{so that}
%\Pr[\mbox{exactly $25$ heads } \mid \mbox{at most $25$ heads}] &> 1/2
%\end{align*}
\[
\Pr[\le 24\mbox{ heads}] \le \frac{\alpha}{1-\alpha}\Pr[\le 25\mbox{
  heads}]
\]
so that
\[
\Pr[\mbox{exactly $25$ heads } \mid \mbox{at most $25$ heads}] > 1/2
\]
\fi

To handle the general case, we define a generalized entropy function
\[
H(\alpha,p) \eqdef - (\alpha \log_2 p + (1 - \alpha) \log_2 (1 - p)).
\]
Then a Stirling formula calculation like the ones above yields
\begin{equation}\label{biased alpha term}
f_{n,p}(\alpha n) = 2^{-n(H(\alpha,p) - H(\alpha))}\overbrace{e^{a_n -
a_{\alpha n} - a_{(1-\alpha) n}}}^{\sim 1}/\sqrt{2 \pi \alpha (1 - \alpha) n}
\end{equation}
The $a_n$ symbols arise from the error in Stirling's approximation; $a_n$
denotes a value between $1/(12n+1)$ and $1/12n$.

The important properties of $H(\alpha,p)$ are:
\begin{eqnarray}
H(\alpha, \alpha) & = & H(\alpha), \text{ the ordinary entropy function,} \label{al1}\\
1 \geq H(\alpha, p) & > & H(\alpha)\geq 0, \text{ for } 0 \leq p \neq \alpha \leq 1, \label{al2}\\
H(\alpha, 1/2) & = & 1\label{al3}.
\end{eqnarray}

We observed that the maximum value of $f_{n, p}(\alpha n)$ occurs when
$\alpha = p$.  For example, in the Mir problem, each part is faulty with
probability $p$, so we would expect $p n$ faulty parts to be the likeliest
case.  Substituting $\alpha = p$ into~(\ref{biased alpha
term}) and then using equation~(\ref{al1}) gives:
\[
f_{n,p}(pn) \leq \frac{1}{\sqrt{2 \pi p (1-p) n}}.
\]
The two sides of this inequality are actually asymptotically equal.

As in the unbiased case, the main term in our approximation~(\ref{biased
alpha term}) of $f_{n, p}(\alpha n)$ is the power of 2.  If $p = \alpha$,
then $H(p,\alpha)=H(\alpha)$ and the exponent is 0.  However, if $p \neq
\alpha$, then by equation~(\ref{al2}), this term is of the form $2^{-cn}$
for $c = H(\alpha, p) - H(\alpha) > 0$.  Again, this tells us that as $n$
grows large, $f_{n,p}(\alpha n)$ shrinks exponentially, indicating that
the general binomial distribution has the shape shown in
Figure~\ref{fig:binom}.
\begin{figure}
%\centerline{\includegraphics[height=2.5in]{figures/binom}}
  \centerline{\resizebox{!}{2.5in}{\mbox{\includegraphics{figures/binom}}}}
  \caption{This diagram shows the approximate shape of the binomial
    distribution function, $f_{n,p}(\alpha n)$.  The central peak is
    centered at $\alpha = p$ and has height
    $\Theta(1/\sqrt{n})$ and width
    $\Theta(\sqrt{n})$.  The ``tails'' on either side fall off very
    quickly.}
  \label{fig:binom}
\end{figure}

In fact, as $n \rightarrow \infty$, the distribution $f_{n,p}$ approaches
the ``Bell curve'' or ``normal distribution''.  Here is a
plot of the normal distribution'' in the unbiased case:

                                % 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(176.0,68.0){\rule[-0.200pt]{303.534pt}{0.400pt}}
  \put(806.0,68.0){\rule[-0.200pt]{0.400pt}{194.888pt}}
  \put(176,68){\usebox{\plotpoint}}
  \put(240,67.67){\rule{2.891pt}{0.400pt}}
  \multiput(240.00,67.17)(6.000,1.000){2}{\rule{1.445pt}{0.400pt}}
  \put(176.0,68.0){\rule[-0.200pt]{15.418pt}{0.400pt}}
  \put(278,68.67){\rule{3.132pt}{0.400pt}}
  \multiput(278.00,68.17)(6.500,1.000){2}{\rule{1.566pt}{0.400pt}}
  \put(291,69.67){\rule{2.891pt}{0.400pt}}
  \multiput(291.00,69.17)(6.000,1.000){2}{\rule{1.445pt}{0.400pt}}
  \put(252.0,69.0){\rule[-0.200pt]{6.263pt}{0.400pt}}
  \put(316,71.17){\rule{2.700pt}{0.400pt}}
  \multiput(316.00,70.17)(7.396,2.000){2}{\rule{1.350pt}{0.400pt}}
  \put(329,72.67){\rule{2.891pt}{0.400pt}}
  \multiput(329.00,72.17)(6.000,1.000){2}{\rule{1.445pt}{0.400pt}}
  \put(341,74.17){\rule{2.700pt}{0.400pt}}
  \multiput(341.00,73.17)(7.396,2.000){2}{\rule{1.350pt}{0.400pt}}
  \put(354,76.17){\rule{2.700pt}{0.400pt}}
  \multiput(354.00,75.17)(7.396,2.000){2}{\rule{1.350pt}{0.400pt}}
  \multiput(367.00,78.61)(2.695,0.447){3}{\rule{1.833pt}{0.108pt}}
  \multiput(367.00,77.17)(9.195,3.000){2}{\rule{0.917pt}{0.400pt}}
  \multiput(380.00,81.60)(1.651,0.468){5}{\rule{1.300pt}{0.113pt}}
  \multiput(380.00,80.17)(9.302,4.000){2}{\rule{0.650pt}{0.400pt}}
  \multiput(392.00,85.60)(1.797,0.468){5}{\rule{1.400pt}{0.113pt}}
  \multiput(392.00,84.17)(10.094,4.000){2}{\rule{0.700pt}{0.400pt}}
  \multiput(405.00,89.59)(1.378,0.477){7}{\rule{1.140pt}{0.115pt}}
  \multiput(405.00,88.17)(10.634,5.000){2}{\rule{0.570pt}{0.400pt}}
  \multiput(418.00,94.59)(0.950,0.485){11}{\rule{0.843pt}{0.117pt}}
  \multiput(418.00,93.17)(11.251,7.000){2}{\rule{0.421pt}{0.400pt}}
  \multiput(431.00,101.59)(0.758,0.488){13}{\rule{0.700pt}{0.117pt}}
  \multiput(431.00,100.17)(10.547,8.000){2}{\rule{0.350pt}{0.400pt}}
  \multiput(443.00,109.59)(0.728,0.489){15}{\rule{0.678pt}{0.118pt}}
  \multiput(443.00,108.17)(11.593,9.000){2}{\rule{0.339pt}{0.400pt}}
  \multiput(456.00,118.58)(0.590,0.492){19}{\rule{0.573pt}{0.118pt}}
  \multiput(456.00,117.17)(11.811,11.000){2}{\rule{0.286pt}{0.400pt}}
  \multiput(469.58,129.00)(0.492,0.539){21}{\rule{0.119pt}{0.533pt}}
  \multiput(468.17,129.00)(12.000,11.893){2}{\rule{0.400pt}{0.267pt}}
  \multiput(481.58,142.00)(0.493,0.576){23}{\rule{0.119pt}{0.562pt}}
  \multiput(480.17,142.00)(13.000,13.834){2}{\rule{0.400pt}{0.281pt}}
  \multiput(494.58,157.00)(0.493,0.655){23}{\rule{0.119pt}{0.623pt}}
  \multiput(493.17,157.00)(13.000,15.707){2}{\rule{0.400pt}{0.312pt}}
  \multiput(507.58,174.00)(0.493,0.774){23}{\rule{0.119pt}{0.715pt}}
  \multiput(506.17,174.00)(13.000,18.515){2}{\rule{0.400pt}{0.358pt}}
  \multiput(520.58,194.00)(0.492,0.927){21}{\rule{0.119pt}{0.833pt}}
  \multiput(519.17,194.00)(12.000,20.270){2}{\rule{0.400pt}{0.417pt}}
  \multiput(532.58,216.00)(0.493,0.972){23}{\rule{0.119pt}{0.869pt}}
  \multiput(531.17,216.00)(13.000,23.196){2}{\rule{0.400pt}{0.435pt}}
  \multiput(545.58,241.00)(0.493,1.052){23}{\rule{0.119pt}{0.931pt}}
  \multiput(544.17,241.00)(13.000,25.068){2}{\rule{0.400pt}{0.465pt}}
  \multiput(558.58,268.00)(0.493,1.171){23}{\rule{0.119pt}{1.023pt}}
  \multiput(557.17,268.00)(13.000,27.877){2}{\rule{0.400pt}{0.512pt}}
  \multiput(571.58,298.00)(0.492,1.401){21}{\rule{0.119pt}{1.200pt}}
  \multiput(570.17,298.00)(12.000,30.509){2}{\rule{0.400pt}{0.600pt}}
  \multiput(583.58,331.00)(0.493,1.369){23}{\rule{0.119pt}{1.177pt}}
  \multiput(582.17,331.00)(13.000,32.557){2}{\rule{0.400pt}{0.588pt}}
  \multiput(596.58,366.00)(0.493,1.448){23}{\rule{0.119pt}{1.238pt}}
  \multiput(595.17,366.00)(13.000,34.430){2}{\rule{0.400pt}{0.619pt}}
  \multiput(609.58,403.00)(0.492,1.659){21}{\rule{0.119pt}{1.400pt}}
  \multiput(608.17,403.00)(12.000,36.094){2}{\rule{0.400pt}{0.700pt}}
  \multiput(621.58,442.00)(0.493,1.607){23}{\rule{0.119pt}{1.362pt}}
  \multiput(620.17,442.00)(13.000,38.174){2}{\rule{0.400pt}{0.681pt}}
  \multiput(634.58,483.00)(0.493,1.607){23}{\rule{0.119pt}{1.362pt}}
  \multiput(633.17,483.00)(13.000,38.174){2}{\rule{0.400pt}{0.681pt}}
  \multiput(647.58,524.00)(0.493,1.646){23}{\rule{0.119pt}{1.392pt}}
  \multiput(646.17,524.00)(13.000,39.110){2}{\rule{0.400pt}{0.696pt}}
  \multiput(660.58,566.00)(0.492,1.789){21}{\rule{0.119pt}{1.500pt}}
  \multiput(659.17,566.00)(12.000,38.887){2}{\rule{0.400pt}{0.750pt}}
  \multiput(672.58,608.00)(0.493,1.607){23}{\rule{0.119pt}{1.362pt}}
  \multiput(671.17,608.00)(13.000,38.174){2}{\rule{0.400pt}{0.681pt}}
  \multiput(685.58,649.00)(0.493,1.567){23}{\rule{0.119pt}{1.331pt}}
  \multiput(684.17,649.00)(13.000,37.238){2}{\rule{0.400pt}{0.665pt}}
  \multiput(698.58,689.00)(0.493,1.488){23}{\rule{0.119pt}{1.269pt}}
  \multiput(697.17,689.00)(13.000,35.366){2}{\rule{0.400pt}{0.635pt}}
  \multiput(711.58,727.00)(0.492,1.444){21}{\rule{0.119pt}{1.233pt}}
  \multiput(710.17,727.00)(12.000,31.440){2}{\rule{0.400pt}{0.617pt}}
  \multiput(723.58,761.00)(0.493,1.250){23}{\rule{0.119pt}{1.085pt}}
  \multiput(722.17,761.00)(13.000,29.749){2}{\rule{0.400pt}{0.542pt}}
  \multiput(736.58,793.00)(0.493,1.052){23}{\rule{0.119pt}{0.931pt}}
  \multiput(735.17,793.00)(13.000,25.068){2}{\rule{0.400pt}{0.465pt}}
  \multiput(749.58,820.00)(0.492,0.927){21}{\rule{0.119pt}{0.833pt}}
  \multiput(748.17,820.00)(12.000,20.270){2}{\rule{0.400pt}{0.417pt}}
  \multiput(761.58,842.00)(0.493,0.655){23}{\rule{0.119pt}{0.623pt}}
  \multiput(760.17,842.00)(13.000,15.707){2}{\rule{0.400pt}{0.312pt}}
  \multiput(774.00,859.58)(0.539,0.492){21}{\rule{0.533pt}{0.119pt}}
  \multiput(774.00,858.17)(11.893,12.000){2}{\rule{0.267pt}{0.400pt}}
  \multiput(787.00,871.59)(1.123,0.482){9}{\rule{0.967pt}{0.116pt}}
  \multiput(787.00,870.17)(10.994,6.000){2}{\rule{0.483pt}{0.400pt}}
  \put(303.0,71.0){\rule[-0.200pt]{3.132pt}{0.400pt}}
  \multiput(812.00,875.93)(1.123,-0.482){9}{\rule{0.967pt}{0.116pt}}
  \multiput(812.00,876.17)(10.994,-6.000){2}{\rule{0.483pt}{0.400pt}}
  \multiput(825.00,869.92)(0.539,-0.492){21}{\rule{0.533pt}{0.119pt}}
  \multiput(825.00,870.17)(11.893,-12.000){2}{\rule{0.267pt}{0.400pt}}
  \multiput(838.58,856.41)(0.493,-0.655){23}{\rule{0.119pt}{0.623pt}}
  \multiput(837.17,857.71)(13.000,-15.707){2}{\rule{0.400pt}{0.312pt}}
  \multiput(851.58,838.54)(0.492,-0.927){21}{\rule{0.119pt}{0.833pt}}
  \multiput(850.17,840.27)(12.000,-20.270){2}{\rule{0.400pt}{0.417pt}}
  \multiput(863.58,816.14)(0.493,-1.052){23}{\rule{0.119pt}{0.931pt}}
  \multiput(862.17,818.07)(13.000,-25.068){2}{\rule{0.400pt}{0.465pt}}
  \multiput(876.58,788.50)(0.493,-1.250){23}{\rule{0.119pt}{1.085pt}}
  \multiput(875.17,790.75)(13.000,-29.749){2}{\rule{0.400pt}{0.542pt}}
  \multiput(889.58,755.88)(0.492,-1.444){21}{\rule{0.119pt}{1.233pt}}
  \multiput(888.17,758.44)(12.000,-31.440){2}{\rule{0.400pt}{0.617pt}}
  \multiput(901.58,721.73)(0.493,-1.488){23}{\rule{0.119pt}{1.269pt}}
  \multiput(900.17,724.37)(13.000,-35.366){2}{\rule{0.400pt}{0.635pt}}
  \multiput(914.58,683.48)(0.493,-1.567){23}{\rule{0.119pt}{1.331pt}}
  \multiput(913.17,686.24)(13.000,-37.238){2}{\rule{0.400pt}{0.665pt}}
  \multiput(927.58,643.35)(0.493,-1.607){23}{\rule{0.119pt}{1.362pt}}
  \multiput(926.17,646.17)(13.000,-38.174){2}{\rule{0.400pt}{0.681pt}}
  \multiput(940.58,601.77)(0.492,-1.789){21}{\rule{0.119pt}{1.500pt}}
  \multiput(939.17,604.89)(12.000,-38.887){2}{\rule{0.400pt}{0.750pt}}
  \multiput(952.58,560.22)(0.493,-1.646){23}{\rule{0.119pt}{1.392pt}}
  \multiput(951.17,563.11)(13.000,-39.110){2}{\rule{0.400pt}{0.696pt}}
  \multiput(965.58,518.35)(0.493,-1.607){23}{\rule{0.119pt}{1.362pt}}
  \multiput(964.17,521.17)(13.000,-38.174){2}{\rule{0.400pt}{0.681pt}}
  \multiput(978.58,477.35)(0.493,-1.607){23}{\rule{0.119pt}{1.362pt}}
  \multiput(977.17,480.17)(13.000,-38.174){2}{\rule{0.400pt}{0.681pt}}
  \multiput(991.58,436.19)(0.492,-1.659){21}{\rule{0.119pt}{1.400pt}}
  \multiput(990.17,439.09)(12.000,-36.094){2}{\rule{0.400pt}{0.700pt}}
  \multiput(1003.58,397.86)(0.493,-1.448){23}{\rule{0.119pt}{1.238pt}}
  \multiput(1002.17,400.43)(13.000,-34.430){2}{\rule{0.400pt}{0.619pt}}
  \multiput(1016.58,361.11)(0.493,-1.369){23}{\rule{0.119pt}{1.177pt}}
  \multiput(1015.17,363.56)(13.000,-32.557){2}{\rule{0.400pt}{0.588pt}}
  \multiput(1029.58,326.02)(0.492,-1.401){21}{\rule{0.119pt}{1.200pt}}
  \multiput(1028.17,328.51)(12.000,-30.509){2}{\rule{0.400pt}{0.600pt}}
  \multiput(1041.58,293.75)(0.493,-1.171){23}{\rule{0.119pt}{1.023pt}}
  \multiput(1040.17,295.88)(13.000,-27.877){2}{\rule{0.400pt}{0.512pt}}
  \multiput(1054.58,264.14)(0.493,-1.052){23}{\rule{0.119pt}{0.931pt}}
  \multiput(1053.17,266.07)(13.000,-25.068){2}{\rule{0.400pt}{0.465pt}}
  \multiput(1067.58,237.39)(0.493,-0.972){23}{\rule{0.119pt}{0.869pt}}
  \multiput(1066.17,239.20)(13.000,-23.196){2}{\rule{0.400pt}{0.435pt}}
  \multiput(1080.58,212.54)(0.492,-0.927){21}{\rule{0.119pt}{0.833pt}}
  \multiput(1079.17,214.27)(12.000,-20.270){2}{\rule{0.400pt}{0.417pt}}
  \multiput(1092.58,191.03)(0.493,-0.774){23}{\rule{0.119pt}{0.715pt}}
  \multiput(1091.17,192.52)(13.000,-18.515){2}{\rule{0.400pt}{0.358pt}}
  \multiput(1105.58,171.41)(0.493,-0.655){23}{\rule{0.119pt}{0.623pt}}
  \multiput(1104.17,172.71)(13.000,-15.707){2}{\rule{0.400pt}{0.312pt}}
  \multiput(1118.58,154.67)(0.493,-0.576){23}{\rule{0.119pt}{0.562pt}}
  \multiput(1117.17,155.83)(13.000,-13.834){2}{\rule{0.400pt}{0.281pt}}
  \multiput(1131.58,139.79)(0.492,-0.539){21}{\rule{0.119pt}{0.533pt}}
  \multiput(1130.17,140.89)(12.000,-11.893){2}{\rule{0.400pt}{0.267pt}}
  \multiput(1143.00,127.92)(0.590,-0.492){19}{\rule{0.573pt}{0.118pt}}
  \multiput(1143.00,128.17)(11.811,-11.000){2}{\rule{0.286pt}{0.400pt}}
  \multiput(1156.00,116.93)(0.728,-0.489){15}{\rule{0.678pt}{0.118pt}}
  \multiput(1156.00,117.17)(11.593,-9.000){2}{\rule{0.339pt}{0.400pt}}
  \multiput(1169.00,107.93)(0.758,-0.488){13}{\rule{0.700pt}{0.117pt}}
  \multiput(1169.00,108.17)(10.547,-8.000){2}{\rule{0.350pt}{0.400pt}}
  \multiput(1181.00,99.93)(0.950,-0.485){11}{\rule{0.843pt}{0.117pt}}
  \multiput(1181.00,100.17)(11.251,-7.000){2}{\rule{0.421pt}{0.400pt}}
  \multiput(1194.00,92.93)(1.378,-0.477){7}{\rule{1.140pt}{0.115pt}}
  \multiput(1194.00,93.17)(10.634,-5.000){2}{\rule{0.570pt}{0.400pt}}
  \multiput(1207.00,87.94)(1.797,-0.468){5}{\rule{1.400pt}{0.113pt}}
  \multiput(1207.00,88.17)(10.094,-4.000){2}{\rule{0.700pt}{0.400pt}}
  \multiput(1220.00,83.94)(1.651,-0.468){5}{\rule{1.300pt}{0.113pt}}
  \multiput(1220.00,84.17)(9.302,-4.000){2}{\rule{0.650pt}{0.400pt}}
  \multiput(1232.00,79.95)(2.695,-0.447){3}{\rule{1.833pt}{0.108pt}}
  \multiput(1232.00,80.17)(9.195,-3.000){2}{\rule{0.917pt}{0.400pt}}
  \put(1245,76.17){\rule{2.700pt}{0.400pt}}
  \multiput(1245.00,77.17)(7.396,-2.000){2}{\rule{1.350pt}{0.400pt}}
  \put(1258,74.17){\rule{2.700pt}{0.400pt}}
  \multiput(1258.00,75.17)(7.396,-2.000){2}{\rule{1.350pt}{0.400pt}}
  \put(1271,72.67){\rule{2.891pt}{0.400pt}}
  \multiput(1271.00,73.17)(6.000,-1.000){2}{\rule{1.445pt}{0.400pt}}
  \put(1283,71.17){\rule{2.700pt}{0.400pt}}
  \multiput(1283.00,72.17)(7.396,-2.000){2}{\rule{1.350pt}{0.400pt}}
  \put(800.0,877.0){\rule[-0.200pt]{2.891pt}{0.400pt}}
  \put(1309,69.67){\rule{2.891pt}{0.400pt}}
  \multiput(1309.00,70.17)(6.000,-1.000){2}{\rule{1.445pt}{0.400pt}}
  \put(1321,68.67){\rule{3.132pt}{0.400pt}}
  \multiput(1321.00,69.17)(6.500,-1.000){2}{\rule{1.566pt}{0.400pt}}
  \put(1296.0,71.0){\rule[-0.200pt]{3.132pt}{0.400pt}}
  \put(1360,67.67){\rule{2.891pt}{0.400pt}}
  \multiput(1360.00,68.17)(6.000,-1.000){2}{\rule{1.445pt}{0.400pt}}
  \put(1334.0,69.0){\rule[-0.200pt]{6.263pt}{0.400pt}}
  \put(1372.0,68.0){\rule[-0.200pt]{15.418pt}{0.400pt}}
\end{picture}

The approximation of the binomial distribution by the normal distribution
is least accurate in the tails, but these are exponentially small anyway.
We'll discuss the normal distribution further in later notes.

\subsection{The Cumulative Distribution Function}

What is the probability of tossing 25 or fewer heads?  Of course, we
could sum the probability of zero heads, one head, two heads,
$\ldots$, and 24 heads.  But there is also a simple formula in terms
of the probability distribution function.

\begin{lemma*}
\begin{equation}\label{Fbyf}
F_{n, p}(\alpha n) \leq
\left(\frac{1 - \alpha}{1 - \alpha/p}\right) f_{n, p}(\alpha n)
\end{equation}
for $\alpha < p$.
\end{lemma*}

This Lemma can be proved using the observation from
\hyperref{http://theory.lcs.mit.edu/classes/6.042/fall01/handouts/tutsol11.pdf}
{binomial}{max-term}{tutorial} that the ratio of successive values of
$f_{n, p}$ from 0 to $pn$ is approximately constant, so the sum of these
values can be bounded by an increasing geometric series.  We omit the
details.

%derivation in fall 96, lect 22

We can compute the probability of throwing 25 \emph{or fewer} heads by
plugging in the values $n = 100$, $\alpha = 1/4$, and $p = 1/2$.  This
gives:
\begin{equation*}
\pr{\mbox{at most 25 heads}}
   = F_{100, 1/2}(\frac{1}{4} \cdot 100)
   \leq \frac{3/4}{1/2} f_{100, 1/2}(25)
   = \frac{3}{2} \cdot 1.913\ldots \cdot 10^{-7}.
\end{equation*}

In other words, the probability of throwing 25 or fewer heads is at most
1.5 times the probability of throwing exactly 25 heads.  Therefore, we are
at least twice as likely to throw exactly 25 heads as to throw 24 or
fewer!  This is somewhat surprising; the cases of 0 heads, 1 head, 2
heads, $\dots$, 24 heads are \emph{together} less likely than the single
case of 25 heads.  This shows how quickly the tails of the binomial
distribution fall off!

\subsubsection{Transmission Across a Noisy Channel}\label{noisy}

Suppose that we are transmitting bits across a noisy channel.  (For
example, say your modem uses a phone line that faintly picks up a
local radio station.)  Suppose we transmit $10,000$ bits, and each
arriving bit is incorrect with probability $0.01$.  Assume that these
errors occur independently.  What is the probability that more than
$2\%$ of the bits are erroneous?

We can solve this problem using our bound~(\ref{Fbyf}) on $F_{n,p}$.
However, one trick is required.  But this bound only holds if $\alpha <
p$, so we switch to working with \emph{correct} bits instead of erroneous
bits.

\begin{equation*}
\pr{> \mbox{ than 2\% errors}}
    =  \pr{\leq \mbox{ 98\% correct}} 
    =  F_{n, 0.99}(0.98n) 
    \leq  1.98 \frac{2^{-0.005646 \cdot 10,000}}{0.3509 \sqrt{10,000}}
    \leq  2^{-60}
\end{equation*}

The probability that more than 2\% of the bits are erroneous is
incredibly small!  This again demonstrates the extreme improbability
of outcomes on the tails of the binomial distribution.

\subsubsection{Polling}

Another good example of binomial distributions comes up in polling.
The Gallup polling service reported that on November 10, only 37\% of
American adults thought Louise Woodward was guilty.  Furthermore,
Gallup asserted that since they asked the opinions of 623 adults,
``one can say with 95 percent confidence that the error attributable
to sampling and other random effects is within plus or minus 4
percentage points''.  Can we confirm this claim?

We want to determine $p$, the fraction of Americans that think Louise
is guilty.  Our plan is to sample the opinion of $n$ people chosen
uniformly and at random, {\em with replacement}.  That is, we might
poll the same person twice!  This may seem inefficient, but it
simplifies the analysis.  If $G$ is the number of people in our sample
that say Louise is guilty, then we will claim that $p$ is about
$G/n$.

The problem is that our sample might not be representative.  For
example, maybe everyone in the country outside of North Dakota thinks
Louise is guilty, but by bad luck the sample contained mostly North
Dakotans.  Then our poll would give the wrong answer.

Let $\epsilon$ be the margin of error we can tolerate, and let
$\delta$ be the probability that our result lies outside this margin.
How many people must we poll so that our result is within $\epsilon$
percent of national opinion with probability at least $1-\delta$?  For
example, Gallup claims that for $\epsilon = 0.04$ and $\delta = 0.05$,
polling $623$ people is sufficient.

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\left(\frac{G}{n} < p - \epsilon\right)}_{
\begin{array}{c}
\mbox{too many in sample} \\
\mbox{say ``not guilty''}
\end{array}}
        + \underbrace{\Pr\left(\frac{G}{n} > p + \epsilon\right)}_{
\begin{array}{c}
\mbox{too many in sample} \\
\mbox{say ``guilty''}
\end{array}} \\
        & = & \pr{G < (p - \epsilon) n} + \pr{G > (p + \epsilon) n}.
\end{eqnarray*}

Each term in the definition of $\delta$ can be evaluated using
bound~(\ref{Fbyf}) on $F_{n,p}$.  In the second term, we must use the same
trick as in the Noisy Channel problem in subsection~\ref{noisy} to
ensure that $\alpha < p$.  We observe that
\[
\pr{\frac{G}{n} > p + \epsilon} = \pr{\frac{n - G}{n} < 1 -p - \epsilon},
\]
where $(n - G)/n$ is the fraction of people polled who say that
Louise is not guilty, and $1-p$ is the fraction of all Americans who say
that she is not guilty.  This gives
\begin{equation}\label{Fnpe}
F_{n,p}((p - \epsilon) n) + F_{n,1-p}((1-p-\epsilon) n)
\end{equation}
as an upper bound for $\delta$.

The problem with the bound~(\ref{Fnpe}) is that the expression contains
$p$, the fraction of Americans that think Louise is guilty.  This is the
number we are trying to determine by polling!  Fortunately, we can bound
$\delta$ by using the following fact:
\begin{fact}
For all $\epsilon$, the maximum value of expression~(\ref{Fnpe}) bounding
$\delta$ occurs when $p = 1/2$.
\end{fact}
\iffalse NEEDS EXPLANATION \fi
This implies that to get an upper bound on $\delta$, we can pretend that
half of the people think Louise is guilty.  So we get
\begin{equation}\label{delta bound}
\delta \leq F_{n,\frac{1}{2}}((\frac{1}{2} - \epsilon) n) +
   F_{n,1-\frac{1}{2}}((1-\frac{1}{2}-\epsilon) n)
 = 2 F_{n}((\frac{1}{2} - \epsilon) n).
\end{equation}

Now suppose that we want a margin of error of $4\%$ as Gallup claimed.
Plugging in $\epsilon = 0.04$ into~(\ref{delta bound}) gives:
\begin{equation*}
\delta \leq   2 F_{n}(0.46 n)
 \leq 
2 \cdot 6.75 \cdot \frac{2^{-0.004622\ldots \cdot n}}{1.2492\ldots \sqrt{n}}.
\end{equation*}

We want to poll enough people so that $\delta$ is less than $0.05$.
The easiest way is to plug in values for $n$, the number of people
polled:
\[
\begin{array}{c|l}
\mbox{$n$ = people polled} & \begin{array}{cc}
\mbox{upper bound on} \\
\mbox{probability poll is wrong}
\end{array} \\
\hline
500 &  9.7\% \\
600 &  6.4\% \\
623 &  5.9\% \quad \leftarrow \quad \mbox{Gallup's poll size} \\
650 &  5.3\% \\
662 &  5.0\% \quad \leftarrow \quad \mbox{our poll size} \\
700 &  4.3\% \\
\end{array}
\]

Gallup's poll size and our poll size are pretty close.  By our
calculation, polling 662 people is sufficient to determine public opinion
to within 4\% with confidence of 95\%.  Gallup only polled 623 people,
which by our calculation gives 94.1\% confidence.  We can look at it
another way: by repeating our calculation with $\epsilon = 0.0413$ plugged
into~(\ref{delta bound}), we can verify that Gallup's poll of 623 people
gives 95\% confidence with at most a 4.13\% margin of error.  Since Gallup
is a first-rate professional pollster, we can assume they have made a more
accurate estimate of appropriate poll size than given by our upper bounds.
Still, our approximations are quite good, since 4.13\% is quite close to
Gallup's announced 4\%.

The 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!

\iffalse

\subsubsection{Summary}
Unbiased $(p=1/2)$ Binomial Distribution: 
\[
f(\frac{n}{2}) \sim \sqrt{\frac{2}{\pi n}} = \Theta(\frac{1}{\sqrt{n}})
\]
\[
f(\alpha n) \sim \sqrt{\frac{2}{\pi n}}\sqrt{\frac{1}{4\alpha(1-\alpha)}}\frac{1}{2^{n(1-H(\alpha))}}
\;\; (\alpha < 1/2)
\]

General $(p \leq 1/2)$ Binomial Distribution:
\[
f(pn) \sim \sqrt{\frac{1}{2 \pi p(1-p)n}} = \Theta(\frac{1}{\sqrt{pn}})
\]
\[
f(\alpha n) \sim \sqrt{\frac{1}{2 \pi \alpha (1-\alpha)
    n}}2^{n(\alpha\log \frac{p}{\alpha} +
  (1-\alpha)\log\frac{p}{1-\alpha})}
\]
\fi

\section{Expected Value}

The \emph{expectation} of a random variable is a central concept in the
study of probability.  The expectation is also called the \emph{expected
value} or the \emph{mean} of the random variable. These terms are all
synonymous.

%%\subsection{Definition}

%% Fix a particular discrete sample space $\sspace$ and 
%% a probability function $\pr{}$.

\begin{definition}
The expected value of a random variable $R$ is denoted $\expect{R}$ and
defined as:
\[
\expect{R} = \sum_{s \in S} R(s) \cdot \pr{s}
\]
\end{definition}
The expected value of a random variable is also sometimes called the
{\em mean} or {\em average}.  Intuitively, the expected value is the
average of all possible values of a random variable, where a value is
weighted according to the probability that it is attained.  Another
equivalent definition is:

\begin{definition}
The \emph{expected value} of random variable $R$ is:
\[
\expect{R} = \sum_{r \in \range{R}} r \cdot \pr{R = r}
\]
\end{definition}

These are equivalent, because the second definition can be obtained
from the first by simply grouping the terms in the summation that have
the same $R$ value.   Letting $r$ take values over $\range{R}$ we have
\begin{eqnarray*}
\expect{R} & =  & \sum_{s \in S} R(s) \cdot \pr{s} \\
       & =  & \sum_{r} \sum_{s \in [R = r]} R(s)
       \cdot \pr{s}\\
       & =  & \sum_{r} \sum_{s \in [R = r]} r
       \cdot \pr{s} \\
       & =  & \sum_{r} r \sum_{s \in [R = r]}
       \pr{s} \\
       & =  & \sum_{r} r \pr{R = r}
\end{eqnarray*}

If the image of a random variable $R$ is not countable, then the
summation above becomes an integral.  We will not deal with this in
6.042.

\iffalse
\emph{Note: In the previous lecture, a random variable was defined as a
function $R : S \to \reals$.  That is, the range of a random variable was
defined to be the real numbers.  In this lecture, we sometimes consider
random variables over a more limited range.  In particular, we often
consider random variables $R : S \to \naturals$.}
\fi

The expected value of a random variable doesn't say anything about
what will happen on one trial.  Rather, it gives information about
what we ``expect'' to happen, ``on the average'', over a large number
of trials.  In fact, in a large number of trials, the probability will
be very high that the average outcome is very close to the expected
value.

\subsection{Expected Value of One Die}

Suppose we roll a fair, six-sided die.  Let the random variable $R$ be
the number that comes up.  We can compute the expected value of $R$
directly from the definition of expected value.
Using the second version of the definition:
\begin{eqnarray*}
\expect{R}  & = &   \sum_{i=1}^6 i \cdot \pr{R = i} \\
        & = &   \frac{1}{6} + \frac{2}{6} + \frac{3}{6} +
                \frac{4}{6} + \frac{5}{6} + \frac{6}{6} \\
        & = &   3 \frac{1}{2}
\end{eqnarray*}

The average value thrown on a fair die is 3.5.  Note, however, that in any
one die roll, we have no reason to expect an outcome near 3.5.  But over
many die rolls, outcomes will almost surely average to around 3.5.

By itself, the mean of a random variable doesn't say too much about the
distribution of values of the variable.  Random variables with very
different distributions can have the same mean.  For example, consider a
funny die with 3 sides of 1 and 3 sides of 6.  The expected value is still
3.5.

\subsection{Expected Value of an Indicator Variable}

If $I$ is the indicator random variable for event $A$, then we calculate 
$\expect{I}$ using the second definition of expectation, as:
\begin{eqnarray*}
\expect{I} & = & 1 \cdot \pr{I = 1} + 0 \cdot \pr{I = 0} \\
       & = & 1 \cdot \pr{A} + 0 \cdot \pr{\bar{A}} \\
       & = & \pr{A}
\end{eqnarray*}
That is, the expected value of the indicator random variable for an
event is just the probability of that event.

\subsection{The Median is Not the Mean}

Expected value, average, and mean are the same thing, but median is
entirely different.  The median is defined below, but only to make the
distinction clear.

\begin{definition}
The {\em median} of a random variable $R$ is the unique value $r$ in the
range of $R$ such that $\pr{R < r} \leq 1/2$ and $\pr{R > r} < 1/2$.  (In
some texts, the $\leq$ and $<$ are swapped in these two conditions.)
\end{definition}


For example, with an ordinary die, the median thrown value is $4$,
which is not the same as the mean 3.5.  The median and the mean can be
very far apart.  For example, consider a $2n$-sided die, with $n$ 0s
and $n$ 100s.  The mean is $50$, and the median is $100$.  We will not
discuss the median further.

\subsection{Modified Carnival Dice}

Let's look at a modified version of Carnival Dice.  The player
chooses a number from 1 to 6.  He then throws three fair and mutually
independent dice.  He wins one dollar for {\em each} die that matches
his number, and he loses one dollar if no die matches.

This is better than the original game where the player received one
dollar if any die matched, and lost a dollar otherwise.  At first
glance the new game appears to be fair; after all, the player is now
``justly compensated'' if he rolls his number on more than one die.
In fact, there is still another variant of Carnival Dice in which the
payoff is \$2.75 instead of \$3 if all three dice match.  In this
case, the game appears fair except for the lost quarter in the rare
case that all three dice match.  This looks like a tiny, tolerable
edge for the house.

Let's check our intuition by computing the expected profit of the
player in one round of the \$3 variant of Carnival Dice.  Let the
random variable $R$ be the amount of money won or lost by the player
in a round.  We can compute the expected value of $R$ as follows:

\begin{eqnarray*}
\expect{R}  & = &   -1 \cdot \pr{\mbox{no dice match}} +
                1 \cdot \pr{\mbox{one die matches}} + \\
        &   &   2 \cdot \pr{\mbox{two dice match}} +
                3 \cdot \pr{\mbox{three dice match}} \\
        & = &   -1 \cdot \left(\frac{5}{6}\right)^3 +
                1 \cdot 3\left(\frac{1}{6}\right)\left(\frac{5}{6}\right)^2+
                2 \cdot 3\left(\frac{1}{6}\right)^2\left(\frac{5}{6}\right)+
                3 \cdot \left(\frac{1}{6}\right)^3 \\
        & = &   \frac{-125 + 75 + 30 + 3}{216} \\
        & = &   \frac{-17}{216}
\end{eqnarray*}

Our intuition was wrong!  Even with a \$3 payoff for three matching
dice, the player can expect to lose $17/216$ of a dollar, or
about 8 cents, in every round.  This is still a horrible game for the
player!

The \$2.75 variant is deceptive.  One is tempted to believe that a
player is shortchanged only a quarter in the rare case that all three
dice match.  This is a tiny amount.  In fact, though, the player loses
this tiny amount {\em in addition} to the comparatively huge 8 cents
per game!

\section{A Shortcut for Computing Expectations}
\label{shortcut}

There is a nice, alternative way to compute the expected value of a
random variable with range $\naturals$.

%%\subsection{The Method}

\begin{theorem}
\label{R>i}
If $R$ is a random variable with range $\naturals$, then
\[
\expect{R} = \sum_{i=0}^{\infty} \pr{R > i}.
\]
\end{theorem}

\begin{proof}
We will begin with the right-hand expression and transform it into
$\expect{R}$.

\begin{eqnarray*}
\sum_{i=0}^{\infty} \pr{R > i}
        & = & \pr{R > 0} + \pr{R > 1} + \pr{R > 2} + \ldots \\
        & = & \underbrace{\pr{R = 1} + \pr{R = 2} + \pr{R = 3} + \ldots}_{= \pr{R > 0}} \\
        &   & + \underbrace{\pr{R = 2} + \pr{R = 3} + \ldots}_{= \pr{R > 1}} \\
        &   & + \underbrace{\pr{R = 3} + \ldots}_{= \pr{R > 2}} \\
        & = & \pr{R = 1} + 2 \cdot \pr{R = 2} + 3 \cdot \pr{R = 3} + \ldots \\
        & = & \sum_{i=0}^{\infty} i \cdot \pr{R = i} \\
        & = & \expect{R}.
\end{eqnarray*}

In the first step, the summation is rewritten with the $\ldots$
notation.  In the second step, we rewrite each term $\pr{R > i}$ as a
series; if $R$ is greater than $i$, then it must be one of $i+1$,
$i+2$, etc.  (This is where we use the fact that the range of $R$ is
$\naturals$.)  Next, we sum all the resulting series, and then revert
to $\Sigma$ notation.  The last summation is the definition of
$\expect{R}$.
\end{proof}

We can now compute the expected value of a random variable $R$ by
summing terms of the form $\pr{R > i}$ instead of terms of the form
$\pr{R = i}$.  Sometimes this makes a problem easier, as we will see
in the next section.  Remember, though, that the theorem only holds if
the range of $R$ is $\naturals$!

\subsection{Mean Time to Failure}

American astronaut David Wolf has just arrived on the Mir space station.
Suppose that Mir's main computer has probability $p$ of failing every
hour, and assume that failures occur independently.  (A failure is not
catastrophic; the Mir computer is constantly on the blink.)  How long
can David expect to wait until the main computer fails?

Let the random variable $R$ be the number of hours until the first
failure; more precisely, assuming that the hours are numbered $1, 2,
3, \ldots$, $R$ is the {\em number of the hour\/} in which the first
failure occurs.  

We want to compute the expected value of $R$.  Since the range of $R$ is
$\naturals$, we can apply Theorem~\ref{R>i} if we can compute $\pr{R >
i}$, the probability that the first failure occurs sometime after hour
$i$.  We can compute this with the usual four-step method.

{\em Step 1: Find the Sample Space.} We can regard the sample space as a
set of finite strings $W^nF$ for $n \in \naturals$.  A $W$ in the $i$th
position means that the main computer is working during hour $i$.  An $F$
in the $n+1$st position means that the computer is down during hour $n+1$.

{\em Step 2: Define Events of Interest.} We are concerned with the
event that $R > i$.  This event consists of all outcomes with no $F$
in the first $i$ positions.

{\em Step 3: Compute Outcome Probabilities.} We want to compute the
probability of a particular outcome $W^nF$.  We reason that since the
probability of a $W$ is $(1-p)$ and of $F$ is $p$, then we shall define
\[
\pr{W^nF} \eqdef (1-p)^np.
\]

{\em Step 4: Compute Event Probabilities.}  We want to compute $\pr{R >
i}$.  There is no $F$ in the first position of an outcome string with
probability $1-p$.  Since failures occur independently, if there is no $F$
in first position, then the probability of $F$ the second position is
$1-p$, etc.  Now we can multiply conditional probabilities: the
probability that there is no $F$ in the first $i$ positions is $(1-p)^i$.
Therefore, $\pr{R > i} = (1-p)^i$.

Now we have
\begin{eqnarray}
\expect{R}  & = &   \sum_{i=0}^{\infty} (1-p)^i \label{fail1}\\
        & = &   1 + (1-p) + (1-p)^2 + (1-p)^3 + \cdots \label{fail2}\\
        & = &   \frac{1}{1 - (1-p)} \label{fail3}\\
        & = &   \frac{1}{p}. \label{fail4}
\end{eqnarray}

Equation~(\ref{fail1}) is simply Theorem~\ref{R>i}.
Equation~(\ref{fail2}) simply rewrites the summation with ellipses to make
clear that we have the sum of a geometric series.  Equation~(\ref{fail3})
is our old formula for the sum of a geometric series.

So we have shown that the expected hour when the main computer fails is
$1/p$.  For example, if the computer has a 1\% chance of failing every
hour, then we would expect the first failure to occur at the 100th hour,
or in about four days.  On the bright side, this means that David Wolf can
expect 99 comfortable hours {\em without} a computer failure.

%% changed waiting for a boy to waiting for a girl :) (RAD)
%% Seems that Leighton's original notes (97) had girl as well but
%% somewhere along the way this was changed to boy. Just changing it back!

\subsection{Waiting for 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
to have first?

This is really a variant of the previous problem.  The question, ``How
many hours until the main computer fails?'' is mathematically the same
as the question, ``How many children must the couple have until they
get a girl?''  In this case, a computer failure 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 1
baby boy.

This strategy may seem to be favoring girls, because the couple keeps
trying until they have one.  However, this effect is counterbalanced
by the small possibility of a long sequence of boys.

Suppose the couple has a $3/4$ chance of having a boy instead of
$1/2$.  Then what is the expected number of children up to and
including the first girl?

Let $R$ be the number of children up to and including the first girl.
Then\[ \expect{R} = \frac{1}{\frac{1}{4}} = 4. \]
That is, the expected number of boys before the first girl is $3$.

{\bf Exercise:} What is the expected number of children needed to get
{\em both} a girl and a boy?

\section{An Expectation Paradox}

Here is a game that reveals a strange property of expectations.

First, you think of a probability distribution function on the natural
numbers.  This distribution can be absolutely anything you like.  For
example, you might choose a uniform distribution on $1, 2, \ldots, 6$,
giving something like a fair die.  Or you might choose a binomial
distribution on $0, 1, \ldots, n$.  You can even give every natural number
a non-zero probability, provided, of course, that the sum of all
probabilities is 1.  Next, I pick a random number $z$ according to
whatever distribution you invent.  In the final stage, you pick a random
number $y$ according to the same distribution.  If your number is bigger
than mine ($y > z$), then the game ends.  Otherwise, if our numbers are
equal or mine is bigger ($y \leq z$), then you pick again, and keep
picking until you get a value that is bigger than $z$.

What is the expected number of picks that you must make?

Certainly, you always need at least one pick---and one pick won't always
work---so the expected number is greater than one.  An answer like 2 or 3
sounds reasonable, though you might suspect that the answer depends on the
distribution.  The real answer is amazing: the expected number of picks
that you need is always \emph{infinite, regardless of the distribution you
choose!}  This makes sense if you choose, say, the uniform distribution on
$1, 2, \ldots, 6$.  After all, there is a $1/6$ chance that I will pick 6.
In this case, you must pick forever--- you can never beat me!

To calculate the expected number of picks, let's first consider the
probability that you need more than one pick.  By symmetry there is at
least a 50-50 chance that my $z$ is greater than or equal to your $y$, and
you will have to pick again.  In other words, you need more than one pick
with probability at least 1/2.

What is the probability that you need more than two picks?  Here is an
erroneous argument.
\begin{falseproof}
On the first pick, you beat me with probability at most $1/2$.  On the
second pick, you beat me with probability at most $1/2$.  The probability
that you fail to beat me on both picks is at most
\[
\frac{1}{2} \cdot \frac{1}{2} = \frac{1}{4}.
\]
Therefore, the probability that you need more than two picks is at most
1/4.
\end{falseproof}

The problem with this reasoning is that beating me on your second pick is
not independent of beating me on your first pick, so multiplying the
probabilities of these two events isn't valid.  It's going to be harder to
beat me on your second pick: the fact that you are picking a second time
implies that $z$ beat a randomly chosen $y$.  So this means $z$ is likely
to be a harder-than-average number to beat on the next pick.

Here is a correct argument: the probability that you need more than two
picks is the same as the probability that if I pick $z$ and you
independently pick $y_1$ and $y_2$, then $z$ is greater than or equal to
the maximum of $z$, $y_1$, and $y_2$.  But by symmetry, each of these
number choices is as likely as any of the others to equal their maximum.
So the probability that any one of them is equal to their maximum is at
least 1/3---it will actually be even larger than 1/3 because of the
possibility of ties for the maximum.  So in particular, the probabilty
that $z$ is the maximum, and hence that you need more than two picks, is
at least $1/3$.

Similarly, we can see that the probability that you need more than $i$
picks is at least $1/(i+1)$---just replace ``2'' by ``$i$'' and ``3'' by
``$i+1$'' in the previous argument for more than two picks.

This argument also shows your chance of needing more picks will be even
larger when there are ties.  So you should choose a distribution such that
ties are very rare.  For example, you might choose the uniform
distribution on $\set{1,\dots, 10^{100}}$.  In this case, the probability
that you need more than $i$ picks to beat me is very close to $1/(i+1)$
for reasonable $i$.  For example, the probability that you need more than
99 picks is almost exactly 1\%.  This may sound very promising to you;
intuitively, you might expect to win within a reasonable number of picks
on average.  But now we can verify the claim that, contrary to intuition,
the expected number of picks that you need in order to beat me is
infinite.  The proof is simple:

\begin{proof}
Let $T$ be the random variable equal to the number of picks you need to be me.
Then
\begin{eqnarray}
\expect{T} & = & \sum_{i=0}^{\infty} \pr{T > i} \label{T1}\\
           & \geq & \sum_{i=0}^{\infty} \frac{1}{i+1} =  \infty
           \label{T3}. \label{T2}
\end{eqnarray}
Here, equation~(\ref{T1}) follows from Theorem~\ref{R>i}, which is
applicable because the range of $T$ is $\naturals$.  The
inequality in~(\ref{T2}) follows from the argument above that you need more
than $i$ picks with probability at least $1/(i+1)$, that is,
\[
\pr{T>i} \geq \frac{1}{i+1}.
\]
But the sum in~(\ref{T2}) is the Harmonic series, which we know diverges.
\end{proof}

This phenomenon can cause all sorts of confusion.  For example, suppose
you have a communication network.  Assume that a packet has a $1/i$ chance
of being delayed by $i$ or more steps.  This sounds good; there is only a
1\% chance of being delayed by 100 or more steps.  But, by the argument
above, the expected delay for a packet is actually infinite!

\section{Linearity of Expectation}

Expected values obey a really nice rule called {\em linearity of
expectation}.  This rule says that the expected value of a sum of
random variables is the sum of the expected values of the variables.

%%\subsection{The Rule}

\begin{theorem}[Linearity of Expectation]\label{2-lin}
For any random variables $R_1$ and $R_2$, 
\[
\expect{R_1 + R_2} = \expect{R_1} + \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{k-lin}
For any random variables $R_1, R_2, \ldots, R_k$,
\[
\expect{R_1 + R_2 + \cdots + R_k} = \expect{R_1} + \expect{R_2} + \cdots +
\expect{R_k}.
\]
\end{corollary}
Given Theorem~\ref{2-lin}, we can prove Corollary~\ref{k-lin} by induction
on $k$.  We omit the proof.

\iffalse
To prove the theorem, we use a basic result about set theory and
probability:
\begin{theorem}[Theorem of Total Probability]
Let $B_1, B_2, \ldots$ be disjoint events such that the union is the
entire sample space $\sspace$.  Then for all events $A \subseteq S$,
\[
\pr{A} = \sum_i \pr{A \cap B_i}.
\]
\end{theorem}
Now we are ready to prove linearity of expectation.

We transform $\expect{R_1 + R_2}$ into $\expect{R_1} + \expect{R_2}$ with
a sequence of equalities.  We start by writing out $\expect{R_1 + R_2}$
using the (second) definition of expectation.  Then we split the sum over
all values of $R_1 + R_2$ into two sums, one over the values, $V_1$ of
$R_1$, and the other over values, $V_2$, of $R_2$.  That is, let $ V_i
\eqdef \range{R_i}$.  Then
\begin{eqnarray*}
\expect{R_1 + R_2}
        & = & \sum_{x \in \range{R_1 + R_2}} x \cdot \pr{R_1 + R_2 = x} \\
        & = & \sum_{x_1 \in V_1} \sum_{x_2 \in V_2} (x_1 + x_2)
                                  \pr{R_1 = x_1 \land R_2 = x_2}.
\end{eqnarray*}
Next, we split the summation into two parts.  We then swap the the
second pair of summation symbols, and continue by pulling out $x_1$ in
the first pair of summations and pulling out $x_2$ in the second pair.
\begin{eqnarray*}
\lefteqn{\sum_{x_1} \sum_{x_2} x_1 \pr{R_1 = x_1 \land R_2 = x_2} +
\sum_{x_1} \sum_{x_2} x_2 \pr{R_1 = x_1 \land R_2 = x_2}} \\
        & = &
\sum_{x_1} \sum_{x_2} x_1 \pr{R_1 = x_1 \land R_2 = x_2} +
\sum_{x_2} \sum_{x_1} x_2 \pr{(R_1 = x_1) \cap (R_2 = x_2)} \\
        & = &
\sum_{x_1} x_1 \sum_{x_2} \pr{R_1 = x_1 \land R_2 = x_2} +
\sum_{x_2} x_2 \sum_{x_1} \pr{R_1 = x_1 \land R_2 = x_2} \\
\end{eqnarray*}
Now we apply the Theorem of Total Probability to each pair of
summations.  For the first pair, event $A$ in the theorem is the event
$R_1 = x_1$.  The $B_i$ events in the theorem correspond to events of
the form $R_2 = x_2$.  The theorem is similarly applied to the second
pair of summations.
\begin{eqnarray*}
\quad \quad \quad \quad
        & = &
\sum_{x_1} x_1 \pr{R_1 = x_1} +
\sum_{x_2} x_2 \pr{R_2 = x_2} \\
        & = &
\expect{R_1} + \expect{R_2}
\end{eqnarray*}

In the final step, we substitute $\expect{R_1}$ and $\expect{R_2}$ in place of
their definitions.

Here is an alternative proof based on the first definition of
expectation, which sums over individual outcomes rather than values of
the random variables.\fi

\begin{proof}
\begin{eqnarray}
\expect{R_1 + R_2}
        & = & \sum_{s \in S} (R_1 + R_2)(s) \pr{s} \label{e1}\\
        & = & \sum_{s \in S} (R_1(s) + R_2(s)) \pr{s} \label{e2}\\
        & = & \sum_{s \in S} R_1(s) \pr{s} + 
              \sum_{s \in S} R_2(s) \pr{s} \label{e3}\\
        & = & \expect{R_1} + \expect{R_2}. \label{e4}
\end{eqnarray}
Here, equation~(\ref{e1}) uses the (first) definition of expectation,
equation~(\ref{e2}) uses the definition of the sum of two random
variables, (\ref{e3}) reorganizes terms into two summations,
and~(\ref{e4}) uses the definition of expectation twice more.
\end{proof}

Another aspect of linearity is:
\begin{lemma}\label{aExp}
For any random variables $R_1$ and $R_2$, and any real numbers $a_1,a_2$,
\[
\expect{a_1 R_1 + a_2 R_2} = a_1 \expect{R_1} + a_2 \expect{R_2}.
\]
\end{lemma}

As common special case of Lemma~\ref{aExp} is worth singling out:
\[
\expect{a R} = a \expect{R}.
\] 

The best thing about linearity of expectation is that no independence
is required.  This is great, because dealing with independence is
pain!  On one hand, we often need to work with random variables that
are not independent.  And even if we believe that some random
variables are independent, we know from previous experience that
proving independence requires a lot of work.

\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 \frac{1}{2} + 3 \frac{1}{2}
 =    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!  (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}^{N} k \cdot \pr{R = k}.
\]

Now we are 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 + \ldots + R_N.
\]

These indicator variables are {\em 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.  That is, if $R_1 = R_2 = \ldots =
R_{N-1} = 1$, then we know that $R_N = 1$.  Therefore, $R_N$ is not
independent of the other indicator variables.  But, since we plan to
use linearity of expectation, we do not {\em care} whether the
indicator variables are independent!

We can take the expected value of both sides of the equation above and
apply linearity of expectation without worrying about independence:
\begin{equation*}
\expect{R}  =   \expect{R_1 + R_2 + \ldots + R_N} 
 =   \expect{R_1} + \expect{R_2} + \ldots + \expect{R_N}.
\end{equation*}

All that remains is to compute the expected value of an indicator variable
$R_i$.  But the expected value of an indicator variable is always the
probability that the indicator is 1:
\begin{equation*}
\expect{R_i} =  1 \cdot \pr{R_i = 1} + 0 \cdot \pr{R_i = 0}
 =  \pr{R_i = 1}.
\end{equation*}

The quantity $\pr{R_i = 1}$ is the probability that the $i$-th man
gets his own hat, which is just $1/N$.  We can now compute the
expected number of men that get their own hat:
\[\begin{array}{rcccccccccc}
\expect{R} &=&  \expect{R_1} &+& \expect{R_2} &+& \ldots &+& \expect{R_N} \\
           &=&  \frac{1}{N} &+& \frac{1}{N} &+& \ldots &+& \frac{1}{N} &=& 1.
\end{array}\]

We should expect exactly one man to get the right hat!

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$.  This makes our solution very general, as the next
example shows.

\subsection{The Chinese Appetizer Problem}

There are $N$ people at a circular table in a Chinese restaurant.  On
the table, there are $N$ different appetizers arranged on a big Lazy
Susan.  Each person starts munching on the appetizer directly in front
of them.  Then someone spins the Lazy Susan so that everyone is faced
with a random appetizer.  What is the expected number of people that
end up with the appetizer that they had originally?

This is just a special case of the hat-check problem, with appetizers in
place of hats.  In the hat check problem, we assumed only that each man
received his own hat with probability $1/N$; we made no assumptions about
how the hats could be permuted.  This problem is a special case, because
we happen to know that appetizers are cyclically shifted relative to their
initial position.  (We assume that each cyclic shift is equally likely.)
Our previous analysis still holds; the expected number of people that get
their original appetizer is one.

Of course the event that exactly one person gets his original appetizer
never happens: either everyone does or no one does.  This illustrates an
important point: the ``expected value'' is not the same as ``the value we
expect,'' since the expected value may never occur!  Another common
example of this is the report that the expected number of children in a
family is 2.1---not many households have 1/10 of a child!  Remembering
that ``expected'' value really means ``average'' value will lower the
potential for confusion about this point.


\subsection{Expected Number of Events that Occur}

We can generalize the hat-check and appetizer problems even further.
Suppose that we have a collection of events in a sample space.  What is
the expected number of events that occur?  For example, $A_i$ might be the
event that the $i$-th man receives his own hat.  The number of events that
occur is then the number of men that receive their own hat.  Linearity of
expectation gives a general solution to this problem:

\begin{theorem}
Given any collection of events $A_1, A_2, \ldots, A_N \subseteq S$,
the expected number of these events that occur is
\[
\sum_{i=1}^N \pr{A_i}.
\]
\end{theorem}

The theorem says that the expected number of events that occur is the
sum the probabilities of the events.  For example, in the hat-check
problem the probability of the event that the $i$-th man receives his
hat is $1/N$.  Since there are $N$ such events, the theorem
says that the expected number of men that receive their hat is $N
(1/N) = 1$.  This matches our earlier result.
No independence assumptions are needed.

\begin{proof}
Let the random variable $R$ be the number of events that occur.  Let
$R_i$ be an indicator variable for the event $A_i$; that is, $R_i(w) =
1$ if event $A_i$ occurs in outcome $w$ (i.e., if $w \in A_i$), and
$R_i(w) = 0$ otherwise.  Then $R_i = 1$ and $A_i$ are the same event.

The number of events that occur is the sum of the indicator variables:
\[
R = R_1 + R_2 + \ldots + R_N.
\]
Taking the expected value of both sides, we find:
\begin{eqnarray*}
\expect{R}  & = &   \expect{\sum_{i=1}^n R_i} \\
        & = &   \sum_{i=1}^n \expect{R_i} \\
        & = &   \sum_{i=1}^n \pr{R_i = 1} \\
        & = &   \sum_{i=1}^n \pr{A_i}.
\end{eqnarray*}
The second equation follows by linearity of expectation.  In the third
step, we use the fact that the expectation of an indicator variable is
the probability that the indicator is 1.  The final step follows
because $R_i = 1$ and $A_i$ are the same event.
\end{proof}


\subsection{Flipping Fair Coins}

Suppose that we flip $N$ fair coins.  What is the expected number that
come up heads?

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.

% This lecture continues the discussion of expected value.  In the last
% lecture, we looked at the expected value of a \emph{sum} of random
% variables.  The main result, called linearity of expectation, says that
% the expected value of a sum is the sum of the expected values; that is,
% $\expect{R_1 + R_2} = \expect{R_1} + \expect{R_2}$.  The wonderful thing
% about linearity of expectation is that $R_1$ and $R_2$ need not be
% independent.

% In this lecture, we will first look at the expected value of a
% \emph{product} of random variables.  If $R_1$ and $R_2$ are
% \emph{independent}, then an analogous result holds.  Namely, the expected
% value of a product is the product of the expected values.

% We will then study the expectation of a sum containing a random number of
% terms. It turns out that expectation is in some sense linear also for
% those sums, provided that the random variables involved are not too
% dependent.

\section{Conditional Expectation}

Just like event probabilities, expectations can be conditioned on some
event.
\begin{definition}
The \emph{conditional expectation of $X$ given event $A$}, written
$\expcond{X}{A}$ is
\[
\sum_x x \cdot\prcond{X=x}{A}
\]
\end{definition}
In other words, it is the expected value of the variable $X$ once we
skew the distribution of $X$ to be conditioned on event $A$.
\begin{example}
Let $D$ be the outcome of a random fair die role.  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 = 5
\]
\end{example}
Since $\expcond{X}{A}$ is just an expectation over a different
probability distribution, it is unsurprising that the rules for
expectation extend to conditional expectation:
\begin{theorem}
  $\expcond{X+Y}{A} = \expcond{X}{A} + \expcond{Y}{A}$.
\end{theorem}
A real benefit of conditional expectation is the way it lets you
divide complicated expectation calculations into simpler ones.
\begin{theorem}
  \label{thm:condexp}
  Let $A_1,A_2,\cdots$ be a partition of the sample space: that is,
  $\cup A_i$ is the entire sample space, but $A_i \cap A_j = \emptyset$
  for any $i \ne j$.  Then
  \[
  \expect{X} = \sum_i \expcond{X}{A_i} \pr{A_i}
  \]
  provided that all the expectations exist and are finite.  
\end{theorem}
\begin{proof}
  \begin{align*}
    \expect{X} &= \sum_x x \cdot\pr{X=x}\\
    &= \sum_x x \cdot \sum_i \prcond{X=x}{A_i} \pr{A_i}\\
    &= \sum_i \sum_x x \cdot \prcond{X=x}{A_i} \pr{A_i}\\
    &= \sum_i \pr{A_i} \sum_x x \cdot \prcond{X=x}{A_i}\\
    &= \sum_i \pr{A_i} \expcond{X}{A_i}.
  \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 probability 
has much more power than one might think.



\section{The Expected Value of a Product}

We have determined that expectation is a linear operator, i.e., that
the expectation of a sum is the sum of the expectations.  The same is
not always true for products, but it is true in an important special
case: when the random variables are \emph{independent}.
\begin{theorem}
  \label{th:prod}
  For any two \emph{independent} random variables $R_1$ and $R_2$
  \[
  \expect{R_1 \cdot R_2} = \expect{R_1} \cdot \expect{R_2}
  \]
\end{theorem}
\begin{proof}
Let $V_i \eqdef \range{R_i}$,for $i=1,2$.

We will transform the left side into the right side.  We first use
the definition of expected value:
\[
\expect{R_1 \cdot R_2} = \sum_{x \in \range{R_1 \cdot R_2}} x \cdot
    \pr{R_1 \cdot R_2 = x}.
\]
Next, we break the summation over the product $R_1 \cdot R_2$ into
separate sums over $R_1$ and $R_2$.
\[
\expect{R_1 \cdot R_2} = \sum_{x_2 \in V_2} \sum_{x_1
    \in V_1} x_1 x_2 \cdot \pr{(R_1 = x_1) \cap (R_2 = x_2)}.
\]
We now use the fact that $R_1$ and $R_2$ are independent.  The
 probability of the intersection of the events $R_1 = x_1$ and $R_2 =
 x_2$ is the product of the probabilities of the two events.
\[
\expect{R_1 \cdot R_2} = \sum_{x_2 \in V_2} \sum_{x_1 \in
    V_1} x_1 x_2 \cdot \pr{R_1 = x_1} \cdot \pr{R_2 = x_2}
\]
  In the remaining four steps, we alternate pulling a term out of a
  summation and applying the definition of expected value.
  \begin{eqnarray*}
    \expect{R_1 \cdot R_2}
    & = &   \sum_{x_2 \in V_2} x_2 \cdot \pr{R_2 = x_2}
    \sum_{x_1 \in V_1} x_1 \cdot \pr{R_1 = x_1} \\
    & = &   \sum_{x_2 \in V_2} x_2 \cdot \pr{R_2 = x_2}
    \cdot \expect{R_1} \\
    & = &   \expect{R_1} \sum_{x_2 \in V_2}
    x_2 \cdot \pr{R_2 = x_2} \\
    \\
    & = &   \expect{R_1} \cdot \expect{R_2}
  \end{eqnarray*}
\end{proof}
There is also a slick proof of Theorem~\ref{th:prod} using the law of
total probability.
\begin{proof}[Alternative Proof of Theorem~\ref{th:prod}]
We apply the law of total probability by conditioning on the value
of~$R_1$.
\[
\expect{R_1 \cdot R_2} = \sum_{x \in V_1} \expcond{R_1 \cdot R_2}{R_1 = x}
    \pr{R_1 = x}
\]
 Now notice that
\[
\expcond{R_1 \cdot R_2}{R_1 = x}   =
\expcond{x \cdot R_2}{R_1 = x}    =
x \expcond{R_2}{R_1 = x}    =
x \expect{R_2},
\]
where the second step follows since~$x$ is a constant, i.e., not a
random variable, and the last step follows since $R_1$ and~$R_2$ are
independent. Putting everything together,
\[
\expect{R_1 \cdot R_2} =
\sum_{x \in V_1} x \expect{R_2} \pr{R_1 = x} =
\expect{R_2} \sum_{x \in V_1} x \pr{R_1 = x} =
\expect{R_1} \expect{R_2}.
\]
The reason we could pull $\expect{R_2}$ out of the summation is that it
it does not depend on the summation index~$x$.
\end{proof}

\subsection{The Product of Two Independent Dice}

Suppose we throw two 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{displaymath}
  \expect{R_1 \cdot R_2}
  = \expect{R_1} \cdot \expect{R_2}
  = 3.5 \cdot 3.5
  = 12.25.
\end{displaymath}
The first equality uses Theorem~\ref{th:prod} and the second uses the
result that the expected value of one die is 3.5.


\subsection{The Product of Two Dependent Dice}

Suppose that the two dice are not independent; in fact, assume that
the second die is always the same as the first.  Now what is the
expected value of the product?

Because the dice are not independent, we can no longer apply
Theorem~\ref{th:prod}.  However, is the expected value of the product
really changed by this loss of independence?  As before, 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{eqnarray*}
\expect{R_1 \cdot R_2}
        & = &   \expect{R_1^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} \\
        & = &   15 \frac{1}{6}
\end{eqnarray*}
The first step uses the fact that the outcome of the second die is
always the same as the first.  In the second step, we expand
$\expect{R_1^2}$ according to the definition of expected value.  In the
third step, we use the fact that the probability of each number coming
up is $1/6$, since the dice are fair.  The last step is
simplification.  The expected value of the product has changed to $15
\frac{1}{6}$.

The preceding example shows that for \emph{dependent} variables,
the expected value of a product need not be the product of the
expected values; that is, $\expect{R_1 \cdot R_2} \neq \expect{R_1} \cdot
\expect{R_2}$.  The general rules for expected values of sums and products
are summarized below:

\bigskip

\fbox{\parbox{6.25in}{
\vspace{.25cm}
For random variables $R_1$ and $R_2$:
\begin{itemize}
\item Regardless of whether $R_1$ and $R_2$ are independent,
$\expect{R_1 + R_2} = \expect{R_1} + \expect{R_2}$.
\item If $R_1$ and $R_2$ are independent, then $\expect{R_1 \cdot R_2} =
\expect{R_1} \cdot \expect{R_2}$.
\end{itemize}
}}

\subsection{Corollaries}

Theorem~\ref{th:prod} extends to a collection of mutually independent
variables.
\begin{corollary}
  If random variables $R_1, R_2, \ldots, R_n$ are mutually
  independent, then
  \[
  \expect{R_1 \cdot R_2 \cdots R_n} = \expect{R_1} \cdot \expect{R_2} \cdots \expect{R_n}
  \]
\end{corollary}
The proof of the corollary is an induction argument using
Theorem~\ref{th:prod} and the definition of mutual independence.
Details are omitted here.

Adjusting a random variable by an additive or multiplicative constant
adjusts the expected value in the same way.
\begin{corollary}
  If $R$ is a random variable and $a$ and $b$ are constants, then
\[
\expect{a R + b} = a \expect{R} + b.
\]
\end{corollary}
This corollary is proved by regarding $a$ and $b$ as random variables
that take on a particular value with probability 1.  We can prove that
$a$ is always independent of $R$.  The result then follows from
linearity of expectation and Theorem~\ref{th:prod}.



\section{The Danger of Expectation of Quotients}

We now know the expected value of a sum or product of random
variables.  Unfortunately, the expected value of a reciprocal is not
so easy to characterize.  Here is a flawed attempt.
\begin{falsethm}
  \label{cor:false}
  If $Z$ and $R$ are independent random variables with $R\ne 0$ (that
  is, $R$ can never be 0) then $\expect{Z/R} = \expect{Z}/\expect{R}$
\end{falsethm}
\begin{proof}[Incorrect proof]
  $\expect{Z} = \expect{(Z/R) \cdot (R)} = \expect{Z/R} \cdot \expect{R}$ by
  Theorem~\ref{th:prod}. Now divide both sides by $\expect{R}$.
\end{proof}
This proof is bogus!  We can not apply Theorem~\ref{th:prod} in the
second step, because $Z/R$ and $R$ are not necessarily independent.
Indeed, one can see the likely dependence: $R$ being large will make
$Z/R$ small. Of course, a bogus proof does not mean a false theorem,
so here is a counterexample:
\begin{example}
  Suppose the random variable $Z=1$ always (with probability 1), while
  the random variable $R$ is 1 with probability $\frac{1}{2}$ and is 2
  with probability $\frac{1}{2}$.  Then
  \begin{eqnarray*}
    \frac{1}{\expect{R}}
    = \frac{1}{1 \cdot \frac{1}{2} + 2 \cdot \frac{1}{2}}
    = \frac{2}{3} \\
    \expect{\frac{1}{R}}
    = \frac{1}{1} \cdot \frac{1}{2} + \frac{1}{2} \cdot \frac{1}{2}
    = \frac{3}{4}
  \end{eqnarray*}
  The two quantities are not equal, so the theorem is false.    
\end{example}



\subsection{A RISC Paradox}

Unfortunately, the fact that Corollary~\ref{cor:false} is false does
not mean that it is never used!  The following data is taken from a
paper by some famous professors.  They wanted to show that programs on
a RISC processor are generally shorter than programs on a CISC
processor.  For this purpose, they made a table of program lengths for
some benchmark problems:
\[
\begin{array}{lccc}
\text{Benchmark}        & \text{RISC}   & \text{CISC}   & \text{CISC / RISC}\\
\hline
\text{E-string search}  & 150           & 120           & 0.8 \\
\text{F-bit test}       & 120           & 180           & 1.5 \\
\text{Ackerman}         & 150           & 300           & 2.0 \\
\text{Rec 2-sort}       & 2800          & 1400          & 0.5 \\
\hline
\text{Average}          &               &               & 1.2
\end{array}
\]
Each row contains the data for one benchmark.  The numbers in the
first two columns are program lengths for each type of processor.  The
third column contains the ratio of the CISC program length to the RISC
program length.  Averaging this ratio over all benchmarks gives the
value 1.2 in the lower right.  The authors conclude that ``CISC
programs are 20\% longer on average''.

This reasoning is wrong!  One problem is that the total amount of RISC
code for all benchmarks is $3220$ bytes versus $2000$ bytes for the
CISC processor.  In other words, the RISC code is much {\em longer}
overall.  One could argue, however, that this is a bad calculation,
since one large, atypical benchmark (e.g. Rec 2-sort) could skew the
whole result.

However, there is a second problem that can not be waved away.
Suppose we redo the final column, taking the other ratio, RISC /
CISC instead of CISC / RISC.
\[
\begin{array}{lccc}
\text{Benchmark}        & \text{RISC}   & \text{CISC}   & \text{RISC / CISC}\\
\hline
\text{E-string search}  & 150           & 120           & 1.25 \\
\text{F-bit test}       & 120           & 180           & 0.67 \\
\text{Ackerman}         & 150           & 300           & 0.5 \\
\text{Rec 2-sort}       & 2800          & 1400          & 2.0 \\
\hline
\text{Average}          &               &               & 1.1
\end{array}
\]
From this table, we would conclude that RISC programs are 10\% longer
than CISC programs on average!  We are using the same reasoning as in
the paper, so this conclusion is equally justifiable--- yet the result
is opposite!  What is going on?



\subsection{A Probabilistic Interpretation}

To shed some light on this paradox, we can model the RISC vs. CISC
debate with the machinery of probability theory.

Let the sample space be the set of benchmark programs.  Let the random
variable $R$ be the length of the RISC program, and let the random
variable $C$ be the length of the CISC program.  We would like to
compare the average length of a RISC program, $\expect{R}$, to the average
length of a CISC program, $\expect{C}$.

To compare average program lengths, we must assign a probability to
each sample point; in effect, this assigns a ``weight'' to each
benchmark.  One might like to weigh benchmarks based on how frequently
similar programs arise in practice.  Lacking such data, however, we
will assign all benchmarks equal weight; that is, our sample space is
uniform.  We can now compute $\expect{R}$ and $\expect{C}$ as follows:
\begin{eqnarray*}
\expect{R}  & = &   \sum_{i \in \text{Range(R)}} i \cdot \pr{R = i} \\
        & = &   \frac{150}{4}+\frac{120}{4}+\frac{150}{4}+\frac{2800}{4} \\
        & = &   805 \\
\\
\expect{C}  & = &   \sum_{i \in \text{Range(C)}} i \cdot \pr{C = i} \\
        & = &   \frac{120}{4}+\frac{180}{4}+\frac{300}{4}+\frac{1400}{4} \\
        & = &   500
\end{eqnarray*}
Since $\expect{R}/\expect{C} = 1.61$, we conclude that the average RISC
program is 61\% longer than the average CISC program.  This is a third
answer, completely different from the other two!  Furthermore, this
answer makes RISC look really bad in terms of code length.  In fact,
both of the earlier results are wrong, and this one is correct.

In terms of our probability model, the paper computes $C / R$ for each
sample point, and then averages to obtain $\expect{C / R} = 1.2$.  This
much is correct.  However, the authors then conclude that ``CISC
programs are 20\% longer on average''; that is, they conclude that
$\expect{C} = 1.2 \ \expect{R}$.  The authors have applied
Corollary~\ref{cor:false}, which we know to be false!

Similarly, our calculation correctly showed that $\expect{R/C} = 1.1$.
However, we then applied the false corollary to conclude that $\expect{R}
= 1.1 \ \expect{C}$; that is, a RISC program is 10\% longer than a CISC
program on average.  Since both arguments are false, it should come as
no surprise that they give contradictory conclusions!

\subsection{A Simpler Example}

The source of the problem is more clear in the following, simpler
example.  Suppose the data were as follows.
\[
\begin{array}{lcccc}
\text{Benchmark}        & \text{Processor A}    & \text{Processor B}
                        & B / A                 & A / B  \\
\hline
\text{Problem 1}        & 2                     & 1             
                        & 1/2                   & 2 \\
\text{Problem 2}        & 1                     & 2
                        & 2                     & 1/2 \\
\hline
\text{Average}          &                       &
                        & 1.25                  & 1.25
\end{array}
\]
Now the data for the processors A and B is exactly symmetric; the two
processors are equivalent.  Yet, from the third column we would
conclude that Processor B programs are 25\% longer on average, and
from the fourth column we would conclude that Processor A programs are
25\% longer on average.  Both conclusions are obviously wrong.  The
moral is that one must be very careful in summarizing data.  Do not
take an average of ratios blindly!

\end{document}



