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

\newcommand{\beqn}{\begin{eqnarray*}}
\newcommand{\eeqn}{\end{eqnarray*}}
\newcommand{\term}[1]{\textit{\textbf{#1}}}
\newcommand{\mfigure}[3]{\bigskip\centerline{\resizebox{#1}{#2}{\includegraphics{#3}}}\bigskip}

\newcommand{\disease}{\text{Zostritis}}

\begin{document}
\lecturenotes{14}{Introduction to Probability}

Probability is the last topic in this course and perhaps the most
important.  Many algorithms rely on randomization; investigating their
correctness and performance requires probability theory.  Moreover,
aspects of computer systems, such as memory management, branch
prediction, packet routing, and load balancing, are often designed
around probabilistic assumptions and analyses.  Probability also comes
up in information theory, cryptography, artificial intelligence, and
game theory.  Beyond these engineering applications, an understanding
of probability gives insight into many everyday issues, such as
polling, DNA testing, risk assessment, investing, and gambling.

\section{The Four-Step Method}

Every probability problem involves some sort of randomized experiment,
process, or game.  Each such problem involves two distinct challenges:
\begin{enumerate}

\item How do you model the situation mathematically?

\item How do you solve the resulting mathematical problems?

\end{enumerate}
In this section, we introduce a four-step approach to questions of the
form, ``What is the probability that ----- ?''  In this approach, we
build a probabilistic model step-by-step and then formalize the
original question in terms of that model.  Remarkably, the structured
thinking that this approach imposes reduces some famously-confusing
problems to near triviality.  However, more complex probability
questions may spin off challenging counting, summing, and
approximation problems ---which, fortunately, you've already spent
weeks learning how to solve!

\subsection{Ultimate Frisbee}

Let's illustrate the four-step process by analyzing a situation that
arises at the beginning of every Ultimate Frisbee game.  The rules
state:
\begin{quote}
Representatives of the two teams each flip a disc.  The representative
of one team calls ``same'' or ``different'' while the discs are in the
air.  The team winning the flip has the choice of receiving or
throwing the initial throw-off; or selecting which goal they wish to
defend initially.
\end{quote}
The result of the flips is considered ``same'' if both discs land face
up or both land face down and ``different'' if one lands face up and
the other face down.  What is the probability that both discs land the
same way?

\subsubsection*{Step 1:  Find the Sample Space}

Our first objective is to identify all the possible outcomes of the
experiment.  A typical experiment involves several randomly-determined
quantities.  For example, the disc-flipping problem involves two such
quantities: the orientation of the first disc and the orientation of
the second.  Every possible combination of these randomly-determined
quantities is called an \term{outcome}.  The set of all possible
outcomes is called the \term{sample space} for the experiment.  Thus,
the sample space for the Ultimate Frisbee problem consists of four
outcomes:
\begin{equation*}
\sspace = \set{UU, UD, DU, DD}.
\end{equation*}
In outcome $UD$, for example, the first disc lands face-up and the
second face-down.

A \term{tree diagram} is a graphical tool that can help you work
through the four-step approach when the number of outcomes is not too
large or the problem is nicely structured.  In particular, we can use
a tree diagram to help understand the sample space.  The first
randomly-determined quantity in our experiment is the orientation of
the first disc, which may be face-up or face-down.  We represent this
as a tree with two branches:

\mfigure{!}{1.25in}{disc-tree1}

In either case, the second disc can also land up or down, so we create
another level of branches:

\mfigure{!}{1.75in}{disc-tree2}

Now the {\em leaves} of the tree diagram correspond to {\em outcomes}
of the experiment.  More generally, you can regard the whole
experiment as walk from the root down to a leaf, where the branch
taken at each stage is randomly determined.

\subsubsection*{Step 2:  Define Events of Interest}

Our objective is to answer questions of the form ``What is the
probability that ----- ?'', where the horizontal line stands for some
phrase such as ``both discs land the same way''.  Almost any such
phrase can be modeled mathematically as an \term{event}, which is
defined to be a subset of the sample space.  For example, the event
that both discs land the same way is a two-element subset of the sample
space:
\begin{equation*}
\set{UU, DD}.
\end{equation*}
Similarly, the event that the discs land differently also consists
of two outcomes:
\begin{equation*}
\set{UD, DU}.
\end{equation*}
You can $\times$ all the outcomes in the event that interests you on
the tree diagram:

\mfigure{!}{1.75in}{disc-tree3}

\subsubsection*{Step 3: Assign Outcome Probabilities}

So far we've enumerated all the possible outcomes of an experiment;
now we must start assessing the likelihood of those outcomes.  In
particular, the goal of this step is to assign each outcome a
probability, which is a real number between 0 and 1.  The sum of all
outcome probabilities must be 1 to reflect the notion that some
outcome must occur.

Ultimately, the probability of each outcome is determined by the
phenomenon you're modeling and is not a quantity that you derive
mathematically.  However, mathematics can help you compute the
probability of every outcome {\em based on fewer and more elementary
modeling decisions.}

For example, mathematics alone is insufficient to compute the
probability that a 
%regulation 
disc lands face-up when vigorously flipped.  But
let's assume that the first disc lands face-up with some probability
$p$ and thus lands face-down with probablity $1 - p$.  And let's
assume that the second disc also lands face-up with probability $p$,
regardless of what happens to the first disc.  We can record these
assumptions on the edges of our tree diagram:

\mfigure{!}{1.75in}{disc-tree4}

Remember that the whole experiment can be regarded as a walk from the
root down to a leaf, where the branch taken at each stage is randomly
determined.  The probabilities on the edges indicate how likely the
walk is to proceed down each branch.  For example, a walk starting at
the root proceeds along the upper branch with probability $p$ and
proceeds down the lower branch with probabilty $1 - p$.  The sum of
the probabilities on the edges departing a vertex must be 1, since
some branch must be taken.

Now we must convert these edge probabilities to outcome probabilities.
This is purely mechanical: {\em the probability of an outcome is equal
to the product of the edge-probabilities on the path from the root to
that outcome}.  For example, the probability of the outcome $UD$ is $p
(1-p)$ and the probability of the outcome $DD$ is $(1-p)(1-p)$.  We
can add these probabilities to the tree diagram:

\mfigure{!}{1.75in}{disc-tree5}

Specifying the probability of each outcome amounts to defining a
function that maps each outcome to a probability.  This function is
usually called $\Pr$.  In these terms, we've just determined that:
\begin{align*}
\pr{UU} & = p^2 & \pr{UD} & = p(1-p) \\
\pr{DU} & = (1-p)p & \pr{DD} & = (1-p)^2.
\end{align*}
Though $\Pr$ is an ordinary function, just like your old friends $f$
and $g$ from calculus, we subject it to all sorts of horrible
notational abuses that $f$ and $g$ were mercifully spared.  For
example, all of the following are common notations for the probability 
of an outcome $x$:
\[
\begin{array}{ccccccccc}
& \pr{x} & \quad & \Pr(x) & \quad \Pr[x] & \quad & \Pr x & \quad & p(x).
\end{array}
\]
A sample space $\sspace$ and a probability function $\Pr : \sspace \to
[0,1]$ together form a \term{probability space}.  Thus, a probability
space describes all possible outcomes of an experiment and the
probability of each outcome.

\subsubsection*{Step 4: Compute Event Probabilities}

We now have a probability for each \textit{outcome}, but we want to
determine the probability of an \textit{event}.  We can bridge this
gap with a definition: \textit{the probability of an event is the sum
of the probabilities of the outcomes it contains}.  As a notational
matter, the probability of an event $E \subseteq
\sspace$ is written $\pr{E}$.  Thus, our definition is that 
\begin{equation*}
\pr{E} = \sum_{x \in E} \pr{x}.
\end{equation*}
For example, the probability of the event that both discs land the
same way is:
\begin{align*}
\pr{UU, DD} & = \pr{UU} + \pr{DD} \\
            & = p^2 + (1-p)^2.
\end{align*}
In terms of the tree diagram, this amounts to summing the
probabilities of the $\times$-ed outcomes.  In any case, we're done!
That's the answer to our original question!  But let's pause to
interpret the solution.

Below we've plotted $p^2 + (1-p)^2$, the probability that both discs
land the same way, as a function of $p$, the probability that one disc
lands face-up.

\mfigure{!}{2in}{frisbee-graph}
\vspace{-2ex}

The plot shows that if frisbees land face up exactly half the time ($p
= 0.5$), then saying ``same'' wins exactly half the time.  And if
frisbees are biased at all one way or the other, then saying ``same''
wins {\em more} than half the time!  Therefore, the representative
should always say ``same'' during the opening flip!

\subsection{The Monty Hall Problem}\label{monty}

In the September 9, 1990 issue of \textit{Parade} magazine, Marilyn
vos Savant responded to the following letter:

\begin{quotation}
\noindent \textit{Suppose you're on a game show, and you're given the
choice of three doors.  Behind one door is a car, behind the others,
goats.  You pick a door, say number 1, and the host, who knows what's
behind the doors, opens another door, say number 3, which has a goat.
He says to you, "Do you want to pick door number 2?"  Is it to your
advantage to switch your choice of doors?}

\vspace{1ex}

\hspace{3in} Craig. F. Whitaker

\hspace{3in} Columbia, MD
\end{quotation}

The letter roughly describes a situation faced by contestants on the
1970's game show \textit{Let's Make a Deal}, hosted by Monty Hall and
Carol Merrill.  Marilyn replied that the contestant should indeed
switch.  But she soon received a torrent of letters ---many from
mathematicians--- telling her that she was wrong.  The problem
generated thousands of hours of heated debate.  However, as you'll
see, the four-step method cuts through the confusion like a Ginsu
knife.

The original letter is a bit vague, so we must make some assumptions
in order to model the game formally:
\begin{enumerate}

\item The car is equally likely to be hidden behind each of the three
doors.

\item The player is equally likely to pick each of the three doors,
regardless of the car's location.

\item After the player picks a door, the host {\em must} open a
different door with a goat behind it and offer the player the choice
of staying with the original door or switching.

\item If the host has a choice of which door to open, then he is
equally likely to select each of them.

\end{enumerate}
In making these assumptions, we're reading a lot into Craig Whitaker's
letter.  Other interpretations are at least as defensible, and some
actually lead to different answers.  But let's accept these
assumptions for now and address the question, ``What is the
probability that a player who switches wins the car?''

\subsubsection*{Step 1:  Find the Sample Space}

The Monty Hall game involves three randomly-determined quantities:
\begin{enumerate}
\item The door concealing the car.
\item The door initially chosen by the player.
\item The door that the host opens to reveal a goat.
\end{enumerate}
Thus, the tree diagram has three levels:

\mfigure{!}{2.5in}{monty1}

In this diagram, the doors are called $A$, $B$, and $C$ to avoid
confusion between door names and probabilities.

\subsubsection*{Step 2:  Define Events of Interest}

We're interested in the event that a player who switches wins.  So we
put an $\times$ by each of the outcomes in that event:

\mfigure{!}{2.5in}{monty2}

\subsubsection*{Step 3:  Assign Outcome Probabilities}

Next, we must compute the probability of each outcome.  First, we
record a probability on each edge of the tree diagram.  These
edge-probabilities are determined by the assumptions we made at the
outset: that the car is equally likely to be behind each door, that
the player is equally likely to pick each door, and that the host is
equally likely to reveal each goat, if he has a choice.  (Notice that
when the host has no choice, the single branch is assigned probability
1.)  Second, we compute the probability of each outcome by multiplying
the edge-probabilities along the path from the root to that outcome.

\mfigure{!}{2.5in}{monty3}

\subsubsection*{Step 4: Compute Event Probabilities}

All that remains is to compute the probability of the event that a
player who switches wins the car.  The probability of an event is the
sum of the probabilities of its outcomes, which we can read right off
the tree diagram:
\begin{align*}
\pr{\text{player who switches wins}}
    & = \frac{1}{9} + \frac{1}{9} + \frac{1}{9} + 
        \frac{1}{9} + \frac{1}{9} + \frac{1}{9} \\
    & = \frac{2}{3}.
\end{align*}
It seems Marilyn's answer is correct; a player who switches doors wins
the car with probability $2/3$!  In contrast, a player who stays with
his or her original door wins with probability $1/3$, since staying
wins if and only if switching loses.

However, a more accurate conclusion is that Marilyn's answer is
correct \textit{provided we accept her interpretation of the
question}.  There is an equally plausible interpretation in which
Marilyn's answer is wrong.  Notice that Craig Whitaker's original
letter does not say that the host is \textit{required} to reveal a
goat and offer the player the option to switch, merely that he
\textit{did} these things.  In fact, on the \textit{Let's Make a Deal}
gameshow, Monty Hall sometimes simply opened the door that the
contestant picked initially.  Therefore, if he wanted to, Monty could
give the option of switching only to contestants who picked the
correct door initially.  If this is the case, then switching {\em
never} works!

%\subsection{Uniform Sample Spaces}
%
%If all outcomes in a sample space are equally likely, then the sample
%space is said to be \term{uniform}.  For example, if we thoroughly
%shuffle a deck of cards and deal a five-card hand, then the sample
%space consists of $\binom{52}{5}$ equally-probably outcomes and is
%thus uniform.
%
%Uniform sample spaces are nice, because the probability of an event
%over a uniform sample space is just the fraction of outcomes in that
%event.  For example, the probability of a full house is:
%\begin{equation*}
%\pr{\text{full house}} =
%    \frac{13 \cdot \binom{4}{3} \cdot 12 \cdot \binom{4}{2}}
%         {\binom{52}{5}}
%\end{equation*}
%Here we are dividing the number of hands with a full house by the
%total number of hands.

\subsection{Uniform Probability  Spaces}

If all outcomes in the sample space are equally likely, then our
probability space is said to be \term{uniform}.  For example, if we
thoroughly shuffle a deck of cards and deal a five-card hand, then the
sample space consists of $\binom{52}{5}$ outcomes which are all
equally-likely, making our probability space a uniform one.

Uniform probability spaces are nice, because then the probability of
an event is just the fraction of outcomes it contains.  For example,
the probability of a full house is: 
\begin{equation*}
\pr{\text{full house}} =
    \frac{13 \cdot \binom{4}{3} \cdot 12 \cdot \binom{4}{2}}
         {\binom{52}{5}}.
\end{equation*}
Here we are dividing the number of hands with a full house by the
total number of hands.

\subsection{Probability Identities}

The definitions we've introduce lead to some useful identities
involving probabilities.  Many probability problems can be solved
quickly with such identities, once you're used to them.  If $E$ is an
event, then the \term{complement of $E$} consists of all outcomes not
in $E$ and is denoted $\overline{E}$.  The probabilities of
complementary events sum to 1:
\begin{equation*}
\pr{E} + \pr{\overline{E}} = 1.
\end{equation*}
About half of the time, the easiest way to compute the probability of
an event is to compute the probability of its complement and then
apply this formula.

Suppose that events $E_1, \ldots, E_n$ are disjoint; that is, every
outcome is in at most one event $E_i$.  The \term{sum rule} says that
the probability of the union of these events is equal to the sum of
their probabilities:
\begin{equation*}
\pr{E_1 \cup \cdots \cup E_n} = \pr{E_1} + \cdots + \pr{E_n}.
\end{equation*}
The probability of the union of events that are not necessarily
disjoint is given by an \term{inclusion-exclusion formula} analogous
to the one for set sizes:
\begin{equation*}
\pr{E_1 \cup \cdots \cup E_n}
    = \sum_i \pr{E_i} - \sum_{i,j} \pr{E_i \cap E_j}
      + \sum_{i,j,k} \pr{E_i \cap E_j \cap E_k} - \cdots
\end{equation*}
The following inequality, called the \term{union bound}, also holds
even if events $E_1, \ldots, E_n$ are not disjoint:
\begin{equation*}
\pr{E_1 \cup \cdots \cup E_n} \leq \pr{E_1} + \cdots + \pr{E_n}.
\end{equation*}
The union bound is simple and ``good enough'' for many probability
calculations.  For example, suppose that $E_i$ is the event that the
$i$-th critical component in a spacecraft fails.  Then $E_1 \cup
\cdots \cup E_n$ is the event that {\em some} critical component
fails.  The union bound gives an upper bound on this vital probability
and does not require engineers to estimate all the terms in the
gigantic inclusion-exclusion formula.

\section{Conditional Probability}

Suppose that we pick a random person in the world.  Everyone has an
equal chance of being selected.  Let $A$ be the event that the person
is an MIT student, and let $B$ be the event that the person lives in
Cambridge.  Intuitively, we're picking a random point in the big
ellipse below and considering the events that the point falls into
ellipses $A$ and $B$:

\mfigure{!}{2in}{cambridge-conditional}

Clearly, both events $A$ and $B$ have low probability.  But what is
the probability that a person is an MIT student, \emph{given} that the
person lives in Cambridge?

This is a conditional probability question.  It can be concisely
expressed in a special notation.  In general, $\prcond{A}{B}$ denotes
the probability of event $A$, given event $B$.  In this example,
$\prcond{A}{B}$ is the probability that the person is an MIT student,
given that he or she is a Cambridge resident.

How do we compute $\prcond{A}{B}$?  Since we are \emph{given} that the
person lives in Cambridge, all outcomes outside event $B$ are
irrelevant.  Intuitively, $\prcond{A}{B}$ should be the fraction of
Cambridge residents that are also MIT students.  That is, the answer
should be the probability that the person is in set $A \cap B$ (darkly
shaded) divided by the probability that the person is in set $B$
(lightly shaded).  This motivates the definition of conditional
probability:
\begin{equation} \label{eq:def-cond-prob}
\prcond{A}{B} = \frac{\pr{A \cap B}}{\pr{B}}.
\end{equation}
If $\pr{B} = 0$, then the conditional probability $\prcond{A}{B}$ is 
undefined.

\subsection{The Halting Problem}

The MIT EECS department's famed D-league hockey team, The Halting
Problem, is playing a 2-out-of-3 series.  The probability that The
Halting Problem wins the first game is $1/2$.  For subsequent games,
the probability of winning depends on the outcome of the preceding
game; the team is invigorated by victory and demoralized by defeat.
Specifically, if The Halting Problem wins a game, then they have a
$2/3$ chance of winning the next game.  On the other hand, if the team
loses, then they have only a $1/3$ chance of winning the following
game.  What is the probability that The Halting Problem wins the
2-out-of-3 series, given that they win the first game?

We can approach conditional probability problems in the same way as
ordinary problems: using tree diagrams and the four-step method.  A
complete tree diagram is shown below, followed by an explanation of
its construction and use.

\mfigure{!}{3in}{figures/hockey}

\subsubsection*{Step 1:  Find the Sample Space}

The sample space for the hockey series is worked out in the tree
diagram.  Each internal node has two children, one corresponding to a
win for The Halting Problem (labeled $W$) and one corresponding to a
loss (labeled $L$).

\subsubsection*{Step 2:  Define Events of Interest}

Our goal is to find the probability that The Halting Problem wins the
series, given that they win the first game.  This suggests that we
define two events.  Let $A$ be the event that The Halting Problem wins
the series, and let $B$ be the event that they win the first game.
The outcomes in each event are checked in the tree diagram.

\subsubsection*{Step 3:  Compute Outcome Probabilities}

Next, we must assign a probability to each outcome.  We begin by
labeling edges as specified in the problem statement.  Specifically,
The Halting Problem has a $1/2$ chance of winning the first game, so
the two edges leaving the root are each assigned probability $1/2$.
Other edges are labeled $1/3$ or $2/3$ based on the outcome of the
preceding game.  We then find the probability of each outcome by
multiplying all probabilities along the corresponding root-to-leaf
path.

\subsubsection*{Step 4: Compute Event Probabilities}

We can now compute the probability that The Halting Problem wins the
tournament, given that they win the first game:
\begin{align*}
\prcond{A}{B} & = \frac{\pr{A \cap B}}{\pr{B}} \\
              & = \frac{1/3 + 1/18}{1/3 + 1/18 + 1/9} \\
              & = \frac{7}{9}.
\end{align*}

\subsection{\textit{A Posteriori} Probabilities and Bayes' Rule}

In the preceding example, we wanted the probability that The Halting
Problem won a 2-out-of-3 series, given that they won the first game.
Now suppose that we turn the problem around: what is the probability
that The Halting Problem won their first game, given that they won the 
2-out-of-3 series?

This seems like an absurd question!  After all, if we know that The
Halting Problem won the series, then the winner of the first game has
already been determined.  Therefore, one might argue, whether they won
or lost the first game is a question of fact, not a question of
probability. 
However, consider the situation that after the series is over you are
told that The Halting Problem won it, but you are not told the results 
of the individual games. From your perspective, it makes perfect sense
to wonder how likely it is that The Halting Problem have also won the
first game.\footnote{In general, probability applies whenever there is
lack  of knowledge. That the events we care about lie in the future is
only one of the reasons why our klowledge about them may be
restricted.}   

Calculating this {\em a posteriori} probability presents no
difficulties.  As before, let  $A$ be the event that The Halting
Problem wins the series, and let $B$ be the event that they win the
first game.  In these terms, we are asking for $\prcond{B}{A}$, which
we can compute in precisely the same way we found $\prcond{A}{B}$:
\begin{align*}
\prcond{B}{A} & = \frac{\pr{A \cap B}}{\pr{A}} \\
              & = \frac{1/3 + 1/18}{1/3 + 1/18 + 1/9} \\
              & = \frac{7}{9}.
\end{align*}
The probability of The Halting Problem winning the first game, given
that they won the series is $7/9$.  This is equal to the probability
that they win the series, given that they win the first game!

This is only a coincidence.  In general, $\prcond{A}{B}$ and
$\prcond{B}{A}$ can be quite different.  The two quantities are
related by \term{Bayes' Rule}:
\begin{equation*}
\prcond{A}{B} \cdot \pr{B} = \prcond{B}{A} \cdot \pr{A}.
\end{equation*}
You can verify this formula by using the definition of conditional
probability and noting that both sides are equal to $\pr{A \cap B}$.
In the Halting Problem example, $\prcond{A}{B}$ and $\prcond{B}{A}$
turned out to be equal, because $\pr{A}$ and $\pr{B}$ were equal.

\subsection{Conditional Probability Identities}

There are a number of other useful identities involving conditional
probability.  

\paragraph{The usual ones.} 
All the usual identities remain valid if all probabilities are
conditioned on the same event.  For example: 
\begin{equation*}
\prcond{E}{C} + \prcond{\overline{E}}{C} = 1.
\end{equation*}

\paragraph{The Law of Total Probability.}
The following identity 
\begin{equation*}
\pr{A} = \prcond{A}{E} \cdot \pr{E} +
         \prcond{A}{\overline{E}} \cdot \pr{\overline{E}}.
\end{equation*}
is called the Law of Total Probability and lets you compute the
probability of an event $A$ using case analysis based on whether or
not event $E$ occurs.  For example, suppose we conduct the following
experiment. First, we flip a coin.  If heads comes up, then we roll
one die and take the result.  If tails comes up, then we roll two dice
and take the sum of the two results.  What is the probability that
this process yields a 2?  Let $E$ be the event that the coin comes up
heads, and let $A$ be the event that we get a 2 overall.  Assuming
that the coin is fair, $\pr{E} = \pr{\overline{E}} = \frac{1}{2}$.
There are now two cases. If we flip heads, then we roll a 2 on a
single die with probabilty $\prcond{A}{E} = \frac{1}{6}$.  On the
other hand, if we flip tails, then we get a sum of 2 on two dice with
probability $\prcond{A}{\overline{E}} = \frac{1}{36}$.  Therefore, the
probability that the whole process yields a 2 is $\pr{A} = \frac{1}{2}
\cdot \frac{1}{6} + \frac{1}{2} \cdot \frac{1}{36} = \frac{7}{72}$. 

More generally, if $E_1, \ldots, E_n$ are disjoint events whose union
is the whole sample space, then:
\begin{equation*}
\pr{A} = \sum_{i=1}^{n} \prcond{A}{E_i} \cdot \pr{E_i}.
\end{equation*}

\paragraph{The product rule.}
Rearranging terms in the definition of conditional
probability~\eqref{eq:def-cond-prob} gives:  
\begin{equation*}
\pr{A_1 \cap A_2} = \pr{A_1} \prcond{A_2}{A_1}.
\end{equation*}
This generalizes to the \term{product rule} by a routine induction
argument:
\begin{multline*}
\qquad\pr{A_1 \cap A_2 \cap \dots \cap A_n} =
\\
\pr{A_1} \cdot 
\prcond{A_2}{A_1} \cdot 
\prcond{A_3}{A_1 \cap A_2} \cdots
\prcond{A_n}{A_1 \cap \cdots \cap A_{n-1}}.
\qquad
\end{multline*}
This equation looks complicated, but we've been using it all along!
Recall that on a tree diagram we calculate the probability of an
outcome by multiplying the edge-probabilities on the corresponding 
root-to-leaf path.  The justification for this calculation is exactly
the product rule.

For example, let $A_i$ be the event that The Halting Problem wins
their $i$-th game.  According to the problem statement, the Halting
Problem wins the first game with probability $1/2$; that is, $\pr{A_1}
= 1/2$.  Given that they win the first game, they win the second with
probability $2/3$.  In other words, $\prcond{A_2}{A_1} = 2/3$.  These
are the edge probabilities recorded on the tree diagram.  The
probability that The Halting Problem wins both games is:
\begin{align*}
\pr{A_1 \cap A_2}
    & = \pr{A_1} \cdot \prcond{A_2}{A_1} \\
    & = \frac{1}{2} \cdot \frac{2}{3} \\
    & = \frac{1}{3}.
\end{align*}
Thus, when we multiply edge probabilities, we're actually applying the
product rule.

\section{Infinite Sample Spaces}

Suppose two players take turns flipping a fair coin.  Whoever flips
heads first is declared the winner.  What is the probability that the
first player wins?  A tree diagram for this problem is shown below:

\mfigure{!}{2in}{infinite-tree1}

The event that the first player wins contains an infinte number of
outcomes, but we can still sum their probabilities:
\begin{align*}
\pr{\text{first player wins}}
    & = \frac{1}{2} + \frac{1}{8} + \frac{1}{32} + \frac{1}{128} + \cdots \\
    & = \frac{2}{3}.
\end{align*}
The second step uses the formula for the sum of a geometric series.
Similarly, we can compute the probability that the second player wins:
\begin{align*}
\pr{\text{second player wins}}
    & = \frac{1}{4} + \frac{1}{16} + \frac{1}{64} + \frac{1}{256}
                      + \cdots \\
    & = \frac{1}{3}.
\end{align*}
In principle, the game could go on forever if both players kept
flipping tails.  
%We can model this by adding an extra outcome to the
%sample space that corresponds to an infinite sequence of tails.  This
%outcome corresponds not to a leaf in the tree diagram, but rather to
%an infinite path.  The probability of this outcome is necessarily 0,
%however, so there is no practical impact on our calculations.
In our tree diagram, this situation does not correspond to any
leaf ---rather, it corresponds to the infinite path.  So, this is not
an outcome.  If we wanted to consider it as such, we could add an
extra leaf as a child of the root. The probability on the edge to this
leaf should then be the probability of the infinite path
$$
\tfrac{1}{2}\cdot\tfrac{1}{2}\cdot\tfrac{1}{2}\cdots 
= \lim_{n\to\infty} \bigl(\tfrac{1}{2}\bigr)^n 
= 0.
$$
Since this probability is~0, there would be no practical impact on our
calculations. 

The mathematical machinery we've developed is adequate to model and
analyze many interesting probability problems with infinite sample
spaces.  However, some intricate infinite processes require more
powerful (and more complex) measure-theoretic notions of probability.
For example, if we generate an infinite sequence of random bits $b_1,
b_2, b_3, \ldots$, then what is the probability that
\[
\frac{b_1}{2^1} + \frac{b_2}{2^2} + \frac{b_3}{2^3} + \cdots
\]
is a rational number?  We won't take up such problems in this course.

\section{Independence}

Suppose that we flip two fair coins simultaneously on opposite sides
of a room.  Intuitively, the way one coin lands does not effect the
way the other coin lands.  The mathematical concept that captures
this intuition is called \term{independence}.  In particular, events
$A$ and $B$ are independent if and only if:
\begin{equation*}
\pr{A \cap B} = \pr{A} \cdot \pr{B}.
\end{equation*}
Generally, independence is something you assume in modeling a
phenomenon ---or wish you could realistically assume.  Many useful
probability formulas only hold if certain events are independent, so a
dash of independence can greatly simplify the analysis of a system.

For example, let's return to the experiment of flipping two fair
coins.  Let $A$ be the event that the first coin comes up heads, and
let $B$ be the event that the second coin is heads.  If we assume that
$A$ and $B$ are independent, then the probability that both coins come
up heads is:
\begin{align*}
\pr{A \cap B} & = \pr{A} \cdot \pr{B} \\
              & = \frac{1}{2} \cdot \frac{1}{2} \\
              & = \frac{1}{4}.
\end{align*}
On the other hand, let $C$ be the event that tomorrow is cloudy and
$R$ be the event that tomorrow is rainy.  Perhaps $\pr{C} =
\frac{1}{5}$ and $\pr{R} = \frac{1}{10}$ in your area.  If these
events were independent, then we could conclude that the probability
of a rainy, cloudy day is quite small:
\begin{align*}
\pr{R \cap C} & = \pr{R} \cdot \pr{C} \\
              & = \frac{1}{5} \cdot \frac{1}{10} \\
              & = \frac{1}{50}.
\end{align*}
Unfortunately, these events are definitely not independent; in
particular, every rainy day is cloudy.  Thus, the probability of a
rainy, cloudy day is actually $\frac{1}{10}$.

\subsection{Working with Independence}

There is another way to think about independence that you may find
more intuitive.  Recall that events $A$ and $B$ are independent if and
only if:
\begin{equation*}
\pr{A \cap B} = \pr{A} \cdot \pr{B}.
\end{equation*}
This equation always holds if $\pr{B} = 0$.  Otherwise, we can divide
both sides by $\pr{B}$ and use the definition of conditional
probability to obtain an alternative formulation of independence:
\begin{equation*}
\prcond{A}{B} = \pr{A}.
\end{equation*}
In other words, events $A$ and $B$ are independent if the probability
of $A$ is unaffected by the fact that $B$ occurs.  In these terms, the
two coin tosses of the previous section were independent, because the 
probability that one coin comes up heads is unaffected by the fact
that the other came up heads.  On the other hand, the appearance of
clouds and rain tomorrow are not independent; the probability of
clouds is low, but the the probability of clouds given that it rains
is~1. 

\subsection{Independence of the Complement}

The following elementary theorem about independence shows many of our
identities and definitions in action.

\begin{theorem}
If $A$ is independent of $B$, then $A$ is independent of $\overline{B}$.
\end{theorem}

\begin{proof}
We begin with a set identity, $A = (A \cap B) \cup (A \cap
\overline{B})$.  Taking the probability of both sides gives:
\begin{align*}
\pr{A} & = \pr{(A \cap B) \cup (A \cap \overline{B})} \\
       & = \pr{A \cap B} + \pr{A \cap \overline{B}} \\
       & = \pr{A} \cdot \pr{B} + \pr{A \cap \overline{B}}. \\
\intertext{The second equation uses the sum rule (since $A\cap B$ and
$A\cap \overline{B}$ are disjoint), and the third uses the
independence of $A$ and $B$.  Now we rearrange terms and use the fact
that $\pr{\overline{B}} = 1 - \pr{B}$:} 
\pr{A \cap \overline{B}}
    & = \pr{A} - \pr{A} \cdot \pr{B} \\
    & = \pr{A} \cdot (1 - \pr{B}) \\
    & = \pr{A} \cdot \pr{\overline{B}}.
\end{align*}
\end{proof}

\section{Mutual Independence}

We have defined what it means for two events to be independent.  But
how can we talk about independence when there are more than two
events?  For example, how can we say that the orientations of $n$
coins are all independent of one another?

Events $E_1, \ldots, E_n$ are \term{mutually independent} if and only
if \textit{for every subset} of the events, the probability of the
intersection is the product of the probabilities.  In other words, all
of the following equations must hold:
\begin{align*}
\pr{E_i \cap E_j}
    & = \pr{E_i} \cdot \pr{E_j}
    & \text{for all distinct $i$, $j$,} \\
\pr{E_i \cap E_j \cap E_k}
    & = \pr{E_i} \cdot \pr{E_j} \cdot \pr{E_k}
     & \text{for all distinct $i$, $j$, $k$,} \\
\pr{E_i \cap E_j \cap E_k \cap E_l}
    & = \pr{E_i} \cdot \pr{E_j} \cdot \pr{E_k} \cdot \pr{E_l}
    & \text{for all distinct $i$, $j$, $k$, $l$,} \\
    & \ldots \\
\pr{E_1 \cap \cdots \cap E_n} & = \pr{E_1} \cdots \pr{E_n}.
\end{align*}
For example, if we toss 100 fair coins and let $E_i$ be the event that
the $i$th coin lands heads, then we might reasonably assume than
$E_1,\ldots,E_{100}$ are mutually independent. 

\subsubsection{DNA Testing}

This is testimony from the O. J. Simpson murder trial on May 15, 1995:
\begin{description}

\item[MR. CLARKE:] When you make these estimations of frequency ---and
I believe you touched a little bit on a concept called independence?

\item[DR. COTTON:] Yes, I did.

\item[MR. CLARKE:] And what is that again?

\item[DR. COTTON:] It means whether or not you inherit one allele that
you have is not ---does not affect the second allele that you might
get.  That is, if you inherit a band at 5,000 base pairs, that doesn't
mean you'll automatically or with some probability inherit one at
6,000.  What you inherit from one parent is what you inherit from the
other.  \textit{ (Got that?)}

\item[MR. CLARKE:] Why is that important?

\item[DR. COTTON:] Mathematically that's important because if that
were not the case, it would be improper to multiply the frequencies
between the different genetic locations.

\item[MR. CLARKE:] How do you ---well, first of all, are these markers
independent that you've described in your testing in this case?

\end{description}
The jury was told that genetic markers in blood found at the crime
scene matched Simpson's.  Furthermore, the probability that the
markers would be found in a randomly-selected person was at most 1 in
170 million.  This astronomial figure was derived from statistics such
as:
\begin{itemize}
\item 1 person in 100 has marker $A$.
\item 1 person in 50 marker $B$.
\item 1 person in 40 has marker $C$.
\item 1 person in 5 has marker $D$.
\item 1 person in 170 has marker $E$.
\end{itemize}
Then these numbers were multiplied to give the probability that a
randomly-selected person would have all five markers:
\begin{align*}
\pr{A \cap B \cap C \cap D \cap E}
    & = \pr{A} \cdot \pr{B} \cdot \pr{C} \cdot \pr{D} \cdot \pr{E} \\
    & = \frac{1}{100} \cdot \frac{1}{50} \cdot \frac{1}{40}
                      \cdot \frac{1}{5} \cdot \frac{1}{170} \\
    & = \frac{1}{170,000,000}.
\end{align*}
The defense pointed out that this assumes that the markers appear
mutually independently.  Furthermore, all the statistics were based on
just a few hundred blood samples.  The jury was widely mocked for
failing to ``understand'' the DNA evidence.  If you were a juror,
would {\em you} accept the 1 in 170 million calculation?

\subsubsection{Pairwise Independence}

The definition of mutual independence seems awfully complicated
---there are so many conditions!  Here's an example that illustrates
the subtlety of independence when more than two events are involved and
the need for all those conditions.  Suppose that we flip three fair,
mutually-independent coins.  Define the following events:
\begin{itemize}
\item $A_1$ is the event that coin 1 matches coin 2.
\item $A_2$ is the event that coin 2 matches coin 3.
\item $A_3$ is the event that coin 3 matches coin 1.
\end{itemize}
Are $A_1$, $A_2$, $A_3$ mutually independent?

The experiment leads to a uniform probability space, over the sample space:
\[
\set{HHH,HHT,HTH,HTT,THH,THT,TTH,TTT}.
\]
This is easy enough to find that we will dispense with the tree diagram:
there are eight outcomes, corresponding to every possible sequence of
three flips: $HHH$, $HHT$, $HTH$, $\dots$ Each outcome has
probability~$1/8$.  

To see if the three events are mutually independent, we must check a
sequence of equalities.  It will be helpful first to compute the
probability of each event $A_i$:
\begin{eqnarray*}
\pr{A_1} & = & \pr{HHH} + \pr{HHT} + \pr{TTH} + \pr{TTT} \\
         & = & \frac{1}{8} + \frac{1}{8} + \frac{1}{8} + \frac{1}{8}\\
         & = & \frac{1}{2}.
\end{eqnarray*}
By symmetry, $\pr{A_2} = \pr{A_3} = 1/2$.  Now we can begin
checking all the equalities required for mutual independence.
\begin{eqnarray*}
\pr{A_1 \cap A_2}       & = & \pr{HHH} + \pr{TTT} \\
                        & = & \frac{1}{8} + \frac{1}{8} \\
                        & = & \frac{1}{4} \\
                        & = & \frac{1}{2} \cdot \frac{1}{2}\\
                        & = & \pr{A_1} \pr{A_2}.
\end{eqnarray*}
By symmetry, $\pr{A_1 \cap A_3} = \pr{A_1} \pr{A_3}$ and $\pr{A_2 \cap
A_3} = \pr{A_2} \pr{A_3}$ must hold as well.  We have now proven that
every pair of events is independent.  But this is not enough to prove
that $A_1$, $A_2$, and $A_3$ are mutually independent!  We must check
the fourth condition:
\begin{eqnarray*}
\pr{A_1 \cap A_2 \cap A_3}      & = & \pr{HHH} + \pr{TTT} \\
                                & = & \frac{1}{8} + \frac{1}{8} \\
                                & = & \frac{1}{4} \\
                                & \neq & \pr{A_1} \pr{A_2} \pr{A_3} = \frac{1}{8}.
\end{eqnarray*}
The three events $A_1$, $A_2$, and $A_3$ are not mutually independent,
even though all pairs of events are independent!


\section{Random Variables}

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

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

\subsection{Definition}

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

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

\subsection{Indicator Random Variables}

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

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

\subsection{Random Variables and Events}

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

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

\subsection{Conditional Probability}

Mixing conditional probabilities and events involving random variables
creates no new difficulties.  For example, $\pr{C \geq 2 \mid M = 0}$
is the probability that at least two coins are heads ($C \geq 2$),
given that not all three coins are the same ($M = 0$).  We can compute
this probability using the definition of conditional probability:
\begin{eqnarray*}
\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*}
The expression $C \geq 2 \cap M = 0$ on the first like may
look odd; what is the set operation $\cap$ doing between an inequality
and an equality?  But recall that, in this context, $C \geq 2$ and $M
= 0$ are events, {\em sets} of outcomes!

\subsection{Independence}

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

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

The notion of independence generalizes to a set of random variables as
follows.  Random variables $R_1, R_2, \ldots, R_n$ are \term{mutually
independent} if for all \\ $x_1, x_2, \ldots, x_n \in \mathbb{R}$ we
have:
\beqn
\lefteqn{\pr{R_1 = x_1 \cap R_2 = x_2 \cap \cdots \cap R_n = x_n}}
	\hspace{1in} \\
	& = & \pr{R_1 = x_1} \cdot \pr{R_2 = x_2} \cdots \pr{R_n = x_n}.
\eeqn
A consequence of this definition of mutual independence is that the
probability of an assignment to a {\em subset} of the variables is
equal to the product of the probabilites of the individual
assignments.  Thus, for example, if $R_1, R_2, \ldots, R_{100}$ are
mutually independent random variables and $x_1, x_2, \ldots, x_{100}$
are arbitrary real numbers, then it follows that:
\beqn
\pr{R_1 = x_1 \cap R_7 = x_7 \cap R_{23} = x_{23}}
	& = &	\pr{R_1 = x_1} \cdot \pr{R_7 = x_7} \cdot \pr{R_{23} = x_{23}}.
\eeqn


\section{Probability Density Functions}

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 without reference to any experiment.  This consideration
motivates the notion of a \emph{probability density function}.

%%\subsection{Definitions}

\begin{definition}
The \emph{probability density function (pdf)} for a random variable $R$ is
the function $f_R : \range{R} \to [0,1]$ defined by:
\[
f_R(x) \eqdef \pr{R = x}.
\]
\end{definition}
It's sometimes convenient to apply $f_R$ to values that are not in the
range of $R$.  By convention, we say $f_R$ equals zero for such values.

The probability density function is also sometimes called the
\emph{point density} 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$ is
the function $F_R: \reals~\to~[0,1]$ defined by:
\[
F_R(x) \eqdef \pr{R \leq x} = \sum_{\text{\scriptsize{$\begin{array}{c}
                                         y \leq x,\\
                                         y \in \range{R}
                                         \end{array}$}}}   f_R(y).
\]
\end{definition}
Note that neither the probability density 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 these Notes,
we will look at three distributions 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 density function $f_B$ at 0 and 1 as
follows:
\begin{eqnarray*}
f_B(0) &=& \pr{B = 0} = p, \\
f_B(1) &=& \pr{B = 1} = 1-p.
\end{eqnarray*}
Similarly, we can compute the cumulative distribution function $F_B$:
\begin{eqnarray*}
F_B(0) &=& \pr{B \leq 0} = p, \\
F_B(1) &=& \pr{B \leq 1} = 1.
\end{eqnarray*}

\subsection{Uniform Distribution}

Next, 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$.  Its probability density and cumulative distribution functions
are:
\begin{eqnarray*}
f_U(k) & \eqdef & \pr{U = k} = \frac{1}{N}, \\
F_U(k) & \eqdef & \pr{U \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}

The \emph{binomial distribution} is the most important and commonly
occurring distribution in Computer Science.

Let $H$ be the number of heads in $n$ independent flips of a coin.  The
density function of $H$ is called a \emph{binomial} density function.  The
coin need not be fair; we allow biased coins where the probability is $p$
that a head will come up.  To determine exactly what the density function
of $H$ is, we need to know the two parameters $n$ and $p$.

More generally, the binomial distribution describes 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.

\begin{definition}
The \emph{unbiased binomial} density function is the function $f_n: \reals
\to [0,1]$ defined by
\[
f_n(k) \eqdef \binom{n}{k} 2^{-n}
\]
where $n$ is a positive integer parameter.

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

The unbiased binomial density function is the special case of the general
binomial density function where the coin is fair, \viz the parameter $p$
is equal to~$1/2$.

\section{The Birthday Principle}

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

\begin{itemize}

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

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

\end{itemize}

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

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

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

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

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

\section{Expected Value}

The \emph{expectation} of a random variable is a central concept in
the study of probability.  It is the average of all possible values of
a random variable, where a value is weighted according to the
probability that it will appear.  The expectation is sometimes also
called the \emph{average}.  It is also called the \emph{expected
value} or the \emph{mean} of the random variable.  These terms are all
synonymous.

\subsection{Two Equivalent Definitions}

\begin{definition}\label{defexp1}
The \emph{expectation} $\expect{R}$ of a random variable $R$ on
sample space $\sspace$ is defined as:
\begin{equation}\label{expsum1}
\expect{R} \eqdef \sum_{s \in \sspace} R(s) \cdot \pr{s}.
\end{equation}
\end{definition}
An equivalent definition is:
\begin{definition}\label{defexp2}
The \emph{expectation} of random variable $R$ is:
\begin{equation}\label{expsum2}
\expect{R} \eqdef \sum_{r \in \range{R}} r \cdot \pr{R = r}.
\end{equation}
\end{definition}
Actually, there is a technicality implicit in both these definitions that
can cause trouble if ignored and we are working with a random variable
that can take infinitely many distinct values.  In both
series~(\ref{expsum1}) and~(\ref{expsum2}), the order of the terms in
the series is not specified.  This means that the limits of these
series are not well-defined unless the series are \emph{absolutely
convergent}, \ie the sum of the \emph{absolute values} of the terms
converges.  For absolutely convergent series, the order of summation
does not matter ---the series converges to the same value, or else
always diverges, regardless of the order in which the terms are
summed. 

Definition~\ref{defexp2} is equivalent to Definition~\ref{defexp1},
because each can be obtained from the other simply by grouping the terms
in the series that have the same $R$ value.  Regrouping the terms is
justified because the series are supposed to be absolutely convergent.
Namely, letting $r$ take values over $\range{R}$ and $[R=r]$ denote
the set $\{s\in\mathcal{S} \mid R(s)=r \}$ of all outcomes where $R$
takes the value $r$, we have
\begin{align*}
\sum_{s \in \sspace} R(s) \cdot \pr{s}
& =   
\sum_{r} \sum_{s \in [R = r]} R(s)  \cdot \pr{s} 
& \text{(reordering terms)}
\\
& =   
\sum_{r} \sum_{s \in [R = r]} r \cdot \pr{s} 
& \text{(since $s\in[R=r]\Rightarrow R(s)=r$)}
\\
& =   \sum_{r} r \sum_{s \in [R = r]} \pr{s} 
& \text{(factor out constant $r$)}
\\
& =   \sum_{r} r \pr{R = r}. 
& \text{(Def. of $\pr{R=r}$)}
\end{align*}


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

Like other averages, the expected value of a random variable doesn't say
anything about what will happen in one trial.  For example, the
``average'' American mother has 2.1 children, but obviously none of them
has exactly this number.  So we don't expect to see the expected value of
a random variable in one trial.  Remembering that ``expected'' value
really means ``average'' value may reduce confusion about this point.

But over a large number of independent trials, we do expect the values to
average out close to the expected value.  We'll examine this connection
between the average of a large number of independent trials and the
expectation in detail in Course Notes 12.

\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.5.
\end{eqnarray*}
The average value thrown on a fair die is 3.5.  Again, on one trial
---a single die roll--- we will never get an outcome closer to the
expected value than 1/2.  But over many die rolls, the values will
almost surely average to a number very close to 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, a
nonstandard die with half its sides marked 1 and the other half marked 6
will also have expectation 3.5.

\subsection{Expected Value of an Indicator Variable}

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

\begin{proof}
\begin{align*}
\expect{I_A} 
& =  1 \cdot \pr{I_A = 1} + 0 \cdot \pr{I_A = 0} 
& \text{(Def.~\ref{defexp2})} 
\\
& = \pr{I_A = 1}
\\
& =  \pr{A}. & \text{(Def. of $I_A$)}
\end{align*}
\end{proof}

\subsection{Chuck-a-Luck}

Let's look at the following gambling game: The player chooses a number
from 1 to 6.  He then throws three fair and mutually independent dice.
If no die matches his number, he loses 1 dollar. Otherwise, we wins 1 
dollar for \emph{each} die that matches his number. 

Intuitively, a game like this is said to be fair if the odds are
neither for nor against the player. A mathematical way to say this 
is that the expected amount of money that the player wins in every
round is~0. 

Now, is this particular game fair? At first glance, it may seem so. 
The player seems to be ``justly compensated'' whenever he rolls his
number on one or more of the dice. 

To check our intuition, we compute the expected profit of the player
in one round.  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{0 matches}} +
                     1 \cdot \pr{\mbox{1 match}} +
                     2  \cdot \pr{\mbox{2 matches}} +
                     3 \cdot \pr{\mbox{3 matches}} \\
        & = &   -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! The player can expect to lose $17/216$ of a
dollar, or about 8 cents, in every round.  This is a horrible game 
to play! 

\section{Expectation of a Natural-Valued Random Variable}

When the range of a random variable is in $\naturals$, there is an
alternative way to compute the expected value that can be convenient.  We
can 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}$.
Remember, though, that the theorem only holds if the range of $R$ is
in~$\naturals$! 

%%\subsection{The Method}

\begin{theorem}\label{R>i}
If $R$ is a random variable with range in $\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}$.  Because $R$ is natural number valued, we can expand $\pr{R
> i}$ into a series:
\[
\pr{R > i} = \pr{R = i+1} + \pr{R = i+2} + \pr{R = i+3} + \cdots
\]
So,
\begin{eqnarray*}
\sum_{i=0}^{\infty} \pr{R > i}
        & = & \pr{R > 0} + \pr{R > 1} +  \pr{R > 2} + \cdots \\
        & = & \underbrace{\pr{R = 1} +  \pr{R = 2} + \pr{R = 3} + \cdots}_{\pr{R > 0}} \\
        &   & \qquad\qquad\quad
              +\underbrace{\pr{R = 2} + \pr{R = 3} + \cdots}_{\pr{R > 1}} \notag\\
        &   & \qquad\qquad\qquad\qquad\qquad\quad\,
	      +\underbrace{\pr{R = 3} + \cdots}_{\pr{R > 2}} \notag \\
        & = &  \pr{R = 1} + 2 \cdot \pr{R = 2} + 3 \cdot \pr{R = 3} + \cdots \\
        & = &  \sum_{i=0}^{\infty} i \cdot \pr{R = i} \\
        & = &  \expect{R}.
\end{eqnarray*}
In the second line we rewrite each term $\pr{R > i}$ as a series.
Next, we sum all the resulting series, and then revert to $\Sigma$
notation.  The last summation is the definition of $\expect{R}$.
\end{proof}

\subsection{Mean Time to Failure}

The Mir space station computer is constantly on the blink.  Fortunately, a
failure is not catastrophic.  Suppose that Mir's main computer has
probability $p$ of failing every hour, and assume that failures occur
independently.  How long should a cosmonaut expect to wait until the main
computer fails?

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

We want to compute the expected value of $R$.  It turns out to be easy to
compute $\pr{R > i}$, the probability that the first failure occurs
sometime after hour $i$.  Since the range of $R$ is $\naturals$, we can
therefore apply Theorem~\ref{R>i} to compute the expected number of hours.

We can compute $\pr{R > i}$ 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$.  For $1\leq l\leq
n$, a $W$ in the $l$th position means that the main computer is
working during hour $l$.  The $F$ in the $n+1$st position means that
the computer went down during hour $n+1$.

\iffalse
MANY STEPS OMIITED HERE: SHOULD SHOW PROBABILITIES SUM TO 1 AND
THAT FAILURES ARE INDEPENDENT.  WE OUGHT TO DEVELOP A LITTLE THEORY TO
REACH THESE CONCLUSIONS ON GENERAL PRINCIPLE INSTEAD OF BY AD HOC
EVALUATION OF SERIES.
\fi

{\em Step 2: Define Events of Interest.} We are concerned with the
event that $R > i$.  This event consists of all outcomes with their
$F$ after the first $i$ positions. That is,
$$
[R>i] = \{ W^nF \mid n+1>i \}.
$$  

{\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,
%\begin{equation}\label{pR>i}
%\pr{R > i} = (1-p)^i.
%\end{equation}
To compute $\pr{R>i}$ we simply add the probabilities of all outcomes
contained in the event that $R>i$:
\begin{align*}
\pr{R>i}
&= \sum_{n+1>i} \pr{W^nF}
\\
&= \sum_{n=i}^\infty (1-p)^np
&\text{(from Step~3)}
\\
&= (1-p)^ip\sum_{n=0}^\infty (1-p)^n
&\text{(factor $(1-p)^ip$)}
\\
&= (1-p)^ip\frac{1}{1-(1-p)}
&\text{(sum of geometric series)}
\\
&= (1-p)^i.
\end{align*}

Now, to compute the expectation, we have
\begin{align*}
\expect{R}  
&= \sum_{i=0}^{\infty} \pr{R > i} 
& \text{(Thm~\ref{R>i})}
\\
&= \sum_{i=0}^{\infty} (1-p)^i \label{fail1} 
& \text{(by Step~4)}
\\
%        & =   1 + (1-p) + (1-p)^2 + (1-p)^3 + \cdots\\
&= \frac{1}{1 - (1-p)} 
&\text{(sum of geometric series)}
\\
&=   \frac{1}{p}.
\end{align*}

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 the cosmonaut
can expect 99 comfortable hours {\em without} a computer failure.

\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}{1/4} = 4. \]
That is, the expected number of boys before the first girl is $3$.

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

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

\subsection{Expectation of a Sum}

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

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

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

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

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

\begin{corollary}\label{linexp-k-thm}
For any random variables $R_1, \dots, R_k$ and constants $a_1, \dots, a_k
\in \reals$,
\[
\expect{\sum_{i=1}^k a_iR_i} = \sum_{i=1}^k a_i\expect{R_i}.
\]
\end{corollary}
Corollary~\ref{linexp-k-thm} follows from Theorem~\ref{linexp-2-thm} by a
routine induction on $k$ which we omit.

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

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


\subsection{Expected Value of Two Dice}

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

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

Notice that we did {\em not} have to assume that the two dice were
independent.  The expected sum of two dice is 7, even if they are
glued together!\footnote{This is provided that gluing does not change
weights to make the individual dice unfair.}

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

\subsection{The Hat-Check Problem}

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

Without linearity of expectation, this would be a very difficult
question to answer.  We might try the following.  Let the random
variable $R$ be the number of men that get their own hat.  We want to
compute $\expect{R}$.  By the definition of expectation, we have:
\[
\expect{R} = \sum_{k=0}^{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 + \cdots + 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.
\iffalse
That is, if $R_1 = R_2 = \ldots = R_{N-1} = 1$, then we know that $R_N = 1$.
\fi
So $R_N$ is not independent of the other indicator variables.  But, since
we plan to use linearity of expectation, we \emph{don't care} whether the
indicator variables are independent, because no matter what,
we can take the expected value of both sides of the equation above and
apply linearity of expectation:
\begin{equation*}
\expect{R} =  \expect{R_1 + R_2 + \cdots + R_N} 
           =  \expect{R_1} + \expect{R_2} + \cdots + \expect{R_N}.
\end{equation*}
Now by Lemma~\ref{expindic}, the expected value of an indicator variable
is always the probability that the indicator is 1.  In this case, 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} &+& \cdots &+& \expect{R_N} \\
           &=&  \cfrac{1}{N} &+& \cfrac{1}{N} &+& \cdots &+& \cfrac{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$.

\subsection{Expectation of a Binomial Distribution}

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

Let $H_{n,p}$ be the number of heads after the flips.  Then $H_{n,p}$ has
the binomial distribution with parameters $n$ and $p$.  Now let $I_k$ be
the indicator for the $k$th coin coming up heads.  By
Lemma~\ref{expindic}, we have
\[
\expect{I_k} = p.
\]
But
\[
H_{n,p} = \sum_{k=1}^n I_k,
\]
so by linearity
\[
\expect{H_{n,p}} = \expect{\sum_{k=1}^n I_k} = \sum_{k=1}^n \expect{I_k} =
\sum_{k=1}^n p = pn.
\]
That is, the expectation of a $(n,p)$-binomially distributed variable is
$pn$.

\iffalse

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

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

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

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

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

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

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


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

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

\fi

\section{Conditional Expectation}

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

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

Since $\expcond{R}{A}$ is just an expectation over a different probability
space, we know that the rules for expectation will extend to conditional
expectation.  For example, conditional expectation will also be
linear.

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

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

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

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

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



\section{The Expected Value of a Product}

\subsection{The Product of Independent Expectations}

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

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

\begin{proof}
We apply the Law of Total Expectation by conditioning on the value
of~$R_1$.
\begin{align*}
\expect{R_1 \cdot R_2} & = \sum_{r \in \range{R_1}} \expcond{R_1 \cdot
           R_2}{R_1 = r} \cdot \pr{R_1 = r} & \text{(Def.~\ref{defcondexp})}\\
   & = \sum_{r} \expcond{r \cdot
           R_2}{R_1 = r} \cdot \pr{R_1 = r}\\
   & = \sum_{r} r \cdot \expcond{R_2}{R_1 = r} \cdot \pr{R_1 = r}
                 & \text{(Theorem~\ref{condexplin})}\\
   & = \sum_{r} r \cdot \expect{R_2} \cdot \pr{R_1 = r}
                     & \text{($R_2$ independent of $R_1$)}\\
   & = \expect{R_2} \sum_{r} r \cdot \pr{R_1 = r}
              & \text{(factor out constant $\expect{R_2}$)}\\
  & = \expect{R_2} \cdot \expect{R_1}. & \text{(Def.~\ref{defexp2})}
\end{align*}
\end{proof}

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

\subsection{The Product of Two Dice}

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

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

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

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

\end{document}