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

%\newtheorem{falsethm}[theorem]{False Theorem}
%\newtheorem{rul}[theorem]{Rule}
%\newtheorem{guess}{Guess}
%\newtheorem{proposition}[theorem]{Proposition}
%\newtheorem{method}{Method}
%\newtheorem{axiom}{Axiom}

\begin{document}

\lecture{notes21}{Lecture Notes}{25 April 2000}

\section{Random Variables}

This lecture introduces the idea of a {\em random variable}.  This
name is a misnomer, since a random variable is actually a function.

\subsection{Definition}

\begin{defin*}
A {\em random variable} is a function that maps every outcome in the
sample space of an experiment to a real number.
\end{defin*}

For example, consider the experiment of tossing three independent,
unbiased coins.  The sample space $S$ for this experiment consists of
eight outcomes: $HHH$, $HHT$, $HTH$, etc.  
Let $C: S \mapsto {\cal R}$ be the function defined by:

\[
C(w) = \mbox{number of heads appearing in outcome $w \in S$}
\]

Then $C$ is a random variable, because it maps every outcome in the
sample space $S$ to a real number.  For example, $C(HHH) = 3$, $C(HTH)
= 2$, $C(TTT) = 0$, etc.

Similarly, for the same experiment, we can define a random variable
$M: S \mapsto {\cal R}$ as follows.

\[
M(w) = \left\{ \begin{array}{cl}
1 & \mbox{ if all 3 coins match in outcome $w \in S$} \\
0 & \mbox{ otherwise}
\end{array} \right.
\]

For example, $M(HHH) = 1$, $M(HTH) = 0$, $M(TTT) = 1$, and so on.

The remainder of this section is divided into short segments that
describe basic features of random variables.  Throughout, we will use
these two random variables, $C$ and $M$, as examples; keep in mind
that $C$ {\bf c}ounts heads and $M$ indicates that all coins {\bf
m}atch.

\subsection{Indicator Random Variables}

The random variable $M$ is an example of an {\em indicator random
variable}.

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

Indicator random variables are also called {\em Bernoulli} or {\em
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.  For example, the random variable
$M$ indicates outcomes with the property that all three coins
match.

\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{HHH \quad TTT}_{\mbox{mapped to 1}} \quad
\underbrace{HHT \quad HTH \quad HTT \quad THH \quad
        THT \quad 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 therefore an
event.  For example, the random variable $C$ partitions the sample
space into four blocks:

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

Thus, the random variable $C$ defines four events, the event that no
coin is heads (denoted $C = 0$), the event that one coin is heads ($C
= 1$), the event that two coins are heads ($C = 2$), and the event
that three coins are heads ($C = 3$).

We can define other events in terms of a random variable as well.  For
example, the event $C \geq 2$, consists of all outcomes mapped to 2 or
more.  In general, if $A$ is a set of real numbers, the event $C
\in A$ consists of all outcomes mapped to an element of $A$.
For example, $C \in \{1, 3\}$ is the event that there are an odd
number of heads.

\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 : S \mapsto {\cal R}$ is a random
variable and $x$ is a real number, then

\begin{eqnarray*}
\Pr(R = x)      & = & \sum_{w \in S : R(w) = x} \Pr(w)
\end{eqnarray*}

For example, we can compute $\Pr(C = 2)$ as follows:

\begin{eqnarray*}
\Pr(C = 2)      & = & \sum_{w \in S : C(w) = 2} \Pr(w) \\
                & = & \Pr(THH) + \Pr(HTH) + \Pr(HHT) \\
                & = & \frac{1}{8} + \frac{1}{8} + \frac{1}{8} \\
                & = & \frac{3}{8}
\end{eqnarray*}

Here $S$ is the sample space $\{ HHH, HHT, HTH, \ldots \}$.  The first
equation uses the definition of the probability of an event.  In the
second step, we identify the three outcomes corresponding to terms in
the summation.  In the third step, we observe that every outcome has
probability $\frac{1}{8}$, since the three coins are fair and
independent.

Similarly, we can compute $\Pr(M = 1)$ as follows

\begin{eqnarray*}
\Pr(M = 1)      & = & \sum_{w \in S: M(w) = 1} \Pr(w) \\
                & = & \Pr(HHH) + \Pr(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 S: C(w) \geq 2} \Pr(w) \\
                & = &   \Pr(THH) + \Pr(HTH) + \Pr(HHT) + \Pr(HHH) \\
                & = &   \frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8} \\
                & = &   \frac{1}{2}
\end{eqnarray*}

If the range of $R$ is ${\cal N}$, an expression of the form $\Pr(R
\geq x)$ can also be evaluated with the summation $\sum_{i \geq x}
\Pr(R = 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.

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(\{THH, HTH, HHT\}) + \Pr(HHH) \\
                & = &   \frac{3}{8}+\frac{1}{8} \\
                & = &   \frac{1}{2}
\end{eqnarray*}

Finally, we find the probability of the event that $C \in \{ 1,
3 \}$.
\begin{eqnarray*}
\Pr(C \in \{1, 3 \})
        & = &   \sum_{w \in S: C(w) \in \{1, 3\}} \Pr(w) \\
        & = &   \Pr(TTH) + \Pr(THT) + \Pr(HTT) + \Pr(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:
\begin{eqnarray*}
\Pr(C \in \{1, 3 \})
        & = &   \sum_{i \in \{ 1, 3 \}} \Pr(C = i) \\
        & = &   \Pr(C = 1) + \Pr(C = 3) \\
        & = &   (\Pr(\{TTH, THT, HTT \}) + \Pr(HHH) \\
        & = &   \frac{3}{8}+\frac{1}{8} \\
        & = &   \frac{1}{2}
\end{eqnarray*}

In general, for a finite set $A$ of reals,
an expression of the form $\Pr(R \in A)$ can be evaluated by
summing probabilities over values in $A$.
That is, $\Pr(R \in A) = \sum_{a \in A} \Pr(R = a)$.

\subsection{Conditional Probability}

Mixing conditional probabilities and events involving random variables
creates no new difficulties.  For example, $\Pr(C \geq 2 \mid 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*}
\Pr(C \geq 2 \mid M = 0)
        & = &   \frac{\Pr((C \geq 2) \cap (M = 0))}{\Pr(M = 0)} \\
        & = &   \frac{\Pr(\{ THH, HTH, HHT\})}
                     {\Pr(\{ THH, HTH, HHT, HTT, THT, 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 the last lecture, 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{defin*}
Two random variables $R_1$ and $R_2$ are {\em independent} if for all
$x_1, x_2 \in {\cal R}$, we have:

\[
\Pr((R_1 = x_1) \cap (R_2 = x_2)) = \Pr(R_1 = x_1) \Pr(R_2 = x_2)
\]
\end{defin*}

The following is an definition for the independence of two random
variables, in terms of conditional probability.  
This definition is equivalent to the previous one.
We will use both definitions.

\begin{defin*}
Two random variables $R_1$ and $R_2$ are {\em independent} if for all
$x_1, x_2 \in {\cal R}$ such that $\Pr(R_2 = x_2) \neq 0$, we have:

\[
\Pr(R_1 = x_1 \mid R_2 = x_2) = \Pr(R_1 = x_1)
\]
\end{defin*}

The second definition may be more intuitive; it says that the
probability that $R_1$ has a particular value is unaffected by the
value of $R_2$.

\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 {\cal R}$ 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) \cap (M = 1)) = 0
        & \mbox{ but } &
\Pr(C = 2) \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 = \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: {\em 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 {\cal R}$ 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$.

\begin{eqnarray*}
\Pr((T = 2) \mid (D_1 = 3)) = 0
        & \mbox{ but } &
\Pr(T = 2) = \frac{1}{36} \neq 0
\end{eqnarray*}

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 $\frac{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 {\em are} actually
independent!

Proving that two random variables are independent requires some work.
Let's use the second definition of independence.  We must show that
for all $x_1, x_2$ in ${\cal R}$ such that $\Pr(D_1 = x_2) \neq 0$, we
have:

\[
\Pr(S = x_1 \mid 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 $\frac{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 $\frac{6}{36} =
\frac{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, $\Pr(S = 1 \mid D_1 = x_2) =
\frac{1}{6}$ for $x_2 = 1, 2, 3, 4, 5,$ or $6$.

These two observations establish the independence condition in six
cases:

\begin{eqnarray*}
\Pr(S = 1 \mid D_1 = 1) = & \frac{1}{6} & = \Pr(S = 1) \\
\Pr(S = 1 \mid D_1 = 2) = & \frac{1}{6} & = \Pr(S = 1) \\
\ldots                    &    \ldots   & \ldots \\
\Pr(S = 1 \mid D_1 = 6) = & \frac{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) = \frac{5}{6}$, since the
complementary event, $S = 1$, has probability $\frac{1}{6}$.

\begin{eqnarray*}
\Pr(S = 0 \mid D_1 = 1) = & \frac{5}{6} & = \Pr(S = 0) \\
\Pr(S = 0 \mid D_1 = 2) = & \frac{5}{6} & = \Pr(S = 0) \\
\ldots                    &    \ldots   & \ldots \\
\Pr(S = 0 \mid D_1 = 6) = & \frac{5}{6} & = \Pr(S = 0)
\end{eqnarray*}

We have established that the independence condition holds for all
necessary $x_1, x_2 \in {\cal R}$.  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{defin*}
Random variables $R_1, R_2, \ldots R_n$ are {\em mutually independent}
if for all $x_1, x_2, \ldots x_n$, we have:

\[
\Pr(R_1 = x_1 \cap R_2 = x_2 \cap \ldots \cap R_n = x_n) =
        \prod_{i=1}^{n} \Pr(R_i = x_i)
\]
\end{defin*}

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.
Then these three random variables are mutually independent.


\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 {\em probability distribution\/}.

\subsection{Definitions}

\begin{defin*}
The {\em probability distribution function (pdf)} for a random
variable $R:S \mapsto {\cal R}$ is the function $f:{\cal R} \mapsto
[0,1]$ defined by:

\begin{eqnarray*}
f(x) & = & \Pr(R = x)
\end{eqnarray*}
\end{defin*}

The probability distribution function is also sometimes called the
point distribution function.  A consequence of this definition is that
$\sum_x f(x) = 1$, since we are summing the probabilities of all
outcomes in the sample space.

\begin{defin*}
The {\em cumulative distribution function} for a random variable $R:S
\mapsto {\cal R}$ is the function $F:{\cal R} \mapsto [0,1]$
defined by:

\begin{eqnarray*}
F(x)    & = & \Pr(R \leq x) \\
        & = & \sum_{y \leq x} f(y)
\end{eqnarray*}
\end{defin*}

Note that neither the probability distribution function nor the
cumulative distribution function involves the sample space of an
experiment; both are functions from ${\cal R}$ 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 $R$ be a Bernoulli random variable that is
0 with probability $p$ and 1 with probability $1-p$.  We can compute
the probability distribution function $f$ at 0 and 1 as follows:

\begin{eqnarray*}
f(0) = \Pr(R = 0) = p \\
f(1) = \Pr(R = 1) = 1-p
\end{eqnarray*}

Similarly, we can compute the cumulative distribution function $F$:

\begin{eqnarray*}
F(0) = \Pr(R \leq 0) = p \\
F(1) = \Pr(R \leq 1) = 1
\end{eqnarray*}

\subsection{Uniform Distribution}

Now let $R$ be a random variable that is uniform on $[1, N]$.  That
is, $R$ takes on value $k$ with probability $\frac{1}{N}$ for all $1
\leq k \leq N$.  The probability distribution function and the
cumulative distribution function are given below.

\begin{eqnarray*}
\begin{array}{l}
f(k) = \Pr(R = k) = \frac{1}{N} \\
\\
F(k) = \Pr(R \leq k) = \frac{k}{N}
\end{array}
\quad \quad
\mbox{where } 1 \leq k \leq N
\end{eqnarray*}

Uniform distributions are very common.  For example, the outcome of a
fair die is uniform on $[1, 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 {\em 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, e.g., the number of
faulty connections when a circuit is wired with independent
probabilities of failures for individual connections.
We will first define one important special case of the binomial
distribution and then define the general case.

\begin{defin*}
The {\em unbiased binomial distribution} is the function $f_n: {\cal R}
\mapsto [0,1]$ defined by

\[
f_n(k) = \binom{n}{k} \frac{1}{2^n}
\]

where $n$ is a parameter that is at least 1.
\end{defin*}

\begin{defin*}
The {\em general binomial distribution} is the function $f_{n,p}: {\cal
R} \mapsto [0,1]$ defined by

\[
f_{n,p}(k) = \binom{n}{k} p^k (1-p)^{n-k}
\]

where $n$ and $p$ are parameters such that $n \geq 1$ and $0 < p < 1$.
\end{defin*}

(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
$\frac{1}{2}$.

Examples will appear later in this lecture.

\section{An Example Involving Uniform Distributions: the Numbers Game}

\subsection{Rules of the Game}

Suppose we are given two envelopes, each containing a number in the
range $0, 1, \ldots 100$, and we are guaranteed that the two numbers
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 {\em both} numbers small!  Then
our guess is not so good!

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

\subsection{A Winning Strategy}

Amazingly, there is a strategy that wins more than 50\% of the time,
regardless of the numbers 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 {\em 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 numbers 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 $\{ \frac{1}{2}, 1\frac{1}{2},
2\frac{1}{2}, \ldots, n - \frac{1}{2} \}$ with the uniform
distribution.  That is, each value is selected with probability
$\frac{1}{n}$.  (We constrain $x$ to be something-and-a-half to avoid
ties.)

\item Peek into a random envelope.  We see a value $r$ that is either
$y$ or $z$.  Each envelope is chosen with probability $\frac{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}[htbp]
\centerline{\includegraphics[height=2.5in]{figures/game100}}
\caption{\em 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.]]]

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

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

{\em 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 $\frac{y}{n}$, the probability that our
guess is too high is $\frac{n-z}{n}$, and the probability of a correct
guess is $\frac{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.

{\em 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 $\frac{1}{2} + \frac{1}{2n}$, regardless of the numbers 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 $\frac{1}{2} +
\frac{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!

\subsection{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 $[0, n-1]$ uniformly, and then let $z = y+1$.  That is, he
should randomly choose a pair of consecutive numbers like $(6,7)$ or
$(73, 74)$ with the uniform distribution.  In homework, we will prove
that this strategy is optimal:

%[[[Robert:  Can you find this HW problem and solution?]]]

\begin{claim}
If the opponent uses the strategy above, then $\Pr(\mbox{we win}) \leq
\frac{1}{2} + \frac{1}{2n}$ for every strategy we can adopt.
\end{claim}

In summary, we can win with probability {\em at least} $\frac{1}{2} +
\frac{1}{2n}$ regardless of what our opponent does, and our opponent can
ensure that we win with probability {\em at most} $\frac{1}{2} +
\frac{1}{2n}$ regardless of what we do.

The homework 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 ${\cal N}$ 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!

\section{Examples Involving the Binomial Distribution}

\subsection{The Troubled Space Station Mir}

Suppose that the Mir space station has $n$ parts, each of which is
faulty with probability $p$.  Furthermore, assume that faults occur
independently.  Let the random variable $R$ be the number of faulty
parts.  What is the probability distribution of $R$?

Since the probability distribution function is defined by $f(k) =
\Pr(R = k)$, our problem is to find $\Pr(R = k)$.  We can do
this with the usual four-step method, though we will not draw a tree
diagram.

{\em 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 $S$ is the set of all $2^n$ such strings.

{\em 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$.

{\em 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}$.

{\em Step 4: Compute event probabilities. }

We can compute the probability that $k$ parts are faulty as follows:

\begin{eqnarray*}
\Pr(R = k)
        & = & \sum_{\begin{array}{c}
\mbox{$w \in S:$} \\
\mbox{$w$ has $k$ $F$'s}
\end{array}} p^k (1-p)^{n-k} \\
& = & \mbox{(\# of length $n$ strings with $k$ $F$'s)} \cdot p^k (1-p)^{n-k} \\
& = & \binom{n}{k} p^k (1-p)^{n-k}
\end{eqnarray*}

The first equation uses the definition of the probability of an event.
The second line follows because all terms in the summation are equal.
In the final line we use the fact that there are $\binom{n}{k}$
strings of length $n$ with $k$ $F$'s.

We can now see that the probability distribution function for the
number of faulty parts is precisely the general binomial distribution:

\[
f(k) = \Pr(R = k) = \binom{n}{k} p^k (1-p)^{n-k} = f_{n, p}(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.

\subsection{The Shape of the Binomial Distribution}

The binomial distribution is somewhat complicated.  For example, it is
not even immediately clear that $\sum_k f_{n, p}(k) = 1$.  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}
\]

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?

\subsubsection*{Approximating $f_{n, p}(k)$}

We can approximate the value of $f_{n, p}(k)$ using Stirling's
formula.  For convenience, we set $k = \alpha n$ where $\alpha$ is a
number between 0 and 1.  The result is:

\[
f_{n,p}(\alpha n)  = 
        \frac{2^{\left(\alpha     \log_2\left( \frac{p}{\alpha} \right) +
                 (1-\alpha) \log_2\left( \frac{1-p}{1-\alpha} \right)\right) \cdot n}
              \overbrace{e^{a_n - a_{\alpha n} - a_{n-\alpha n}}}^{\sim 1}}
             {\sqrt{2 \pi \alpha (1 - \alpha) n}}
\]

This expression looks nasty, but is really very useful.  As usual, the
$a_i$ symbols arise from the error in Stirling's approximation; $a_i$
denotes a value between $\frac{1}{12i+1}$ and $\frac{1}{12i}$.

\subsubsection*{The Maximum Value of $f_{n, p}(k)$}

The maximum value of $f_{n, p}(\alpha n)$ occurs when $\alpha = p$.
This matches intuition.  For example, in the Mir problem, each part is
faulty with probability $p$, so we would expect exactly $p n$ faulty
parts to be the likeliest case.  Substituting, $\alpha = p$ into our
approximation for $f_{n, p}(\alpha n)$ 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.
We can use this formula to find the probability that exactly 50 heads
come up in 100 tosses of a fair coin by substituting $n = 100$ and $p
=
\frac{1}{2}$:

\begin{eqnarray*}
\Pr(\mbox{50 heads})
        & = & f_{100,\frac{1}{2}}\left(\frac{1}{2}n\right) \\
        & \leq & \frac{1}{\sqrt{50 \pi}} \approx 0.079788
\end{eqnarray*}

The probability of throwing exactly 50 heads in 100 tosses is at most
$8\%$!  In fact, the bound given above is very close to the true
value; in this case, the exact answer is $0.079589\ldots$

We can also compute the probability of throwing exactly 25 heads in
100 tosses.  In this case, we substitute $n = 100$, $p = \frac{1}{2}$,
and $\alpha = \frac{1}{4}$ into the formula for $f_{n,p}(\alpha n)$:

\begin{eqnarray*}
f_{n,p}(\alpha n) & = &
        \frac{2^{\left(\alpha     \log_2\left( \frac{p}{\alpha} \right) +
                 (1-\alpha) \log_2\left( \frac{1-p}{1-\alpha} \right)\right) \cdot n}
              e^{a_n - a_{\alpha n} - a_{n-\alpha n}}}
             {\sqrt{2 \pi \alpha (1 - \alpha) n}} \\
                & = &
        \frac{2^{(-0.1887) \cdot 100} \cdot 0.99\ldots}{10.85\ldots} \\
        & \approx &     1.913 \cdot 10^{-7}
\end{eqnarray*}

The odds are less than 1 in 5 million for throwing exactly 25 heads in
100 tosses!

The main term in our approximation of $f_{n, p}(\alpha n)$ is the
power of 2.  If $p = \alpha$, then this term is 1.  However, if $p
\neq \alpha$, then this term is of the form $2^{-cn}$ for some $c > 0$.
As a consequence, when $n$ grows large, $f_{n, p}(\alpha n)$ shrinks
exponentially.  This suggests that the binomial distribution has the
shape shown in Figure~\ref{fig:binom}.

\begin{figure}[htbp]
\centerline{\includegraphics[height=2.5in]{figures/binom}}
\caption{\em 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(\protect\frac{1}{\protect\sqrt{n}})$ and width
$\Theta(\sqrt{n})$.  The ``tails'' on either side fall off
very quickly.}
\label{fig:binom}
\end{figure}

\subsubsection*{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{theorem}
\label{th:tail}
\[
F_{n, p}(\alpha n) \leq
\frac{1 - \alpha}{1 - \frac{\alpha}{p}} f_{n, p}(\alpha n)
\quad \quad
\mbox{for $\alpha < p$}
\]
\end{theorem}

We can compute the probability of throwing 25 or fewer heads by
plugging in the values $n = 100$, $\alpha = \frac{1}{4}$, and $p =
\frac{1}{2}$.  This gives:

\begin{eqnarray*}
\Pr(\mbox{at most 25 heads})
        & = & F_{100, \frac{1}{2}}(\frac{1}{4} \cdot 100) \\
        & \leq & \frac{3/4}{1/2} f_{100, \frac{1}{2}}(25) \\
        & = & \frac{3}{2} \cdot 1.913\ldots \cdot 10^{-7}
\end{eqnarray*}

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, $\ldots$, 24 heads are all together less
likely than the single case of 25 heads.  This shows how quickly the
tails of the binomial distribution fall off!

\subsection{Transmission Across a Noisy Channel}

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 Theorem~\ref{th:tail}.  However, one
trick is required.  The theorem only holds if $\alpha < p$; therefore,
we have to work in terms of correct bits instead of erroneous bits.

\begin{eqnarray*}
\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{eqnarray*}

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.

\subsection{Polling}

Another good example of binomial distributions comes up in polling.
The Gallup polling service reported that on a particular day a couple
of years ago, 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
$\frac{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
Theorem~\ref{th:tail}.  In the second term, we must use the same trick
as in the Noisy Channel problem to ensure that $\alpha < p$.  We
observe that $\Pr(\frac{G}{n} > p + \epsilon) = \Pr(\frac{n - G}{n} <
1 - p - \epsilon)$, where $\frac{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{eqnarray*}
\delta & \leq & F_{n,p}((p - \epsilon) n) + F_{n,1-p}((1-p-\epsilon) n)
\end{eqnarray*}

This is an expression for the probability that our poll is off by more
than the margin of error.  The problem 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 upper bound $\delta$ by using the following fact:

\begin{fact}
For all $\epsilon$, the maximum value of $\delta$ occurs when $p =
\frac{1}{2}$.
\end{fact}

The fact implies that to get an upper bound on $\delta$, we can
pretend that half of the people think Louise is guilty.  This gives:

\begin{eqnarray*}
\delta & \leq & F_{n,\frac{1}{2}}((\frac{1}{2} - \epsilon) n) +
                F_{n,1-\frac{1}{2}}((1-\frac{1}{2}-\epsilon) n) \\
        & = &   2 F_{n,\frac{1}{2}}((\frac{1}{2} - \epsilon) n)
\end{eqnarray*}

Now suppose that we want a margin of error of $4\%$ as Gallup claimed.
Plugging in $\epsilon = 0.04$ gives:

\begin{eqnarray*}
\delta
        & \leq &  2 F_{n,\frac{1}{2}}(0.46 n) \\
        & \leq & 2 \cdot 6.75 \cdot \frac{2^{-0.004622\ldots \cdot n}}{1.2492\ldots \sqrt{n}}
\end{eqnarray*}

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 is just about right.  By our calculation, polling
662 people is sufficient to determine public opinion to within 4\%
with confidence of 95\%.  We can be certain that Gallup's poll of 623
people gives 95\% confidence with at most a 4.13\% margin of error.
But the real margin of error may be less, since we made several
approximations.  Still, our approximations must be quite good, since
4.13\% is quite close to Gallup's claim of 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!
\end{document}
