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

\renewcommand{\coursecopyrightnames}
{\href{http://theory.lcs.mit.edu/~meyer}{Prof.~Albert~R.~Meyer}}

%\renewcommand{\coursecopyrightyear}{2002}

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

\askaboutsolutions

\begin{document}
\lecturenotes{10}{Introduction to Probability
\instatements{\\(with Monty Hall example postponed)}}

% \reading Rosen \S 4.4 \& 4.5 through Example 7, p.272.

\section{Probability}
Probability will be the topic for the rest of the term.  Probability is
one of the most important subjects in Mathematics and Computer Science.
Most upper level Computer Science courses require probability in some
form, especially in analysis of algorithms and data structures, but also
in information theory, cryptography, control and systems theory, network
design, artificial intelligence, and game theory.  Probability also plays
a key role in fields such as Physics, Biology, Economics and Medicine.

There is a close relationship between Counting/Combinatorics and
Probability.  In many cases, the probability of an event is simply the
fraction of possible outcomes that make up the event.  So many of the
\hyperref{http://theory.lcs.mit.edu/classes/6.042/fall02/handouts/lectures/ln8.pdf}{rule}{incl-excl}{rules}
we developed for finding the cardinality of finite sets carry over to
Probability Theory.  For example, we'll apply an Inclusion-Exclusion
principle for \emph{probabilities} in some examples below.

\iffalse

Probability is also frequently an issue in daily life.  For example, a few
years ago there was national controversy about the probability that the
nuclear-powered spacecraft Cassini would accidentally coat the earth with
super-toxic plutonium dioxide.  This is not an entirely academic question.
In a press release, NASA asserted:
\begin{quote}
Jet Propulsion Laboratory has conducted an in-depth analysis, which
incorporated human error\footnote{This is just a grammar bug.
Yeah.  Well, hopefully.} and historical JPL spacecraft data, to
determine the probability of an inadvertent reentry.  This analysis
determined that the probability of an inadvertent Earth reentry is
less than one in one million.
\end{quote}
Yet some people felt that the probability of disaster was sufficiently
high that they staged vigorous protests and filed suit in federal
court to prevent the launch.  How could there be such intense dispute
about a probability question?
\fi

In principle, probability boils down to a few simple rules, but it remains
a tricky subject because these rules often lead unintuitive conclusions.
Using ``common sense'' reasoning about probabilistic questions is
notoriously unreliable, as we'll illustrate with many real-life examples.

This reading is longer than usual \instatements{and will get even longer
when the sections on the Monty Hall game are included after lecture on
Monday}.  To keep things in bounds, several sections with illustrative
examples that do not introduce new concepts are marked ``[Optional].''
You should read these sections selectively, choosing those where you're
unsure about some idea and think another example would be helpful.

\section{Modelling Experimental Events}

One intuition about probability is that we want to predict how likely it
is for a given experiment to have a certain kind of outcome.  Asking this
question invariably involves four distinct steps:

\begin{description}
\item[Find the sample space.]  Determine all the possible outcomes of
  the experiment.

\item[Define the event of interest.] Determine which of those possible
  outcomes is ``interesting.''

\item[Determine the individual outcome probabilities.] Decide how
  likely each individual outcome is to occur.

\item[Determine the probability of the event.]  Combine the
  probabilities of ``interesting'' outcomes to find the overall
  probability of the event we care about.
\end{description}

In order to understand these four steps, we will begin with a toy
problem.  We consider rolling three dice, and try to determine the
probability that we roll exactly two sixes.

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

Every probability problem involves some experiment or game.  The key to
most probability problems is to look carefully at the \emph{sample space}
of the experiment.  Informally, this is the set of all possible
experimental \emph{outcomes}.  An outcome consists of the total
information about the experiment after it has been performed.  \iffalse
This includes the values of all random choices that were made.\fi An
outcome is also called a ``sample point'' or an ``atomic event''.

In our die rolling experiment, a particular outcome can be expressed as a
triple of numbers from 1 to 6.  For example, the triple $(3,5,6)$
indicates that the first die rolled 3, the second rolled 5, and the third
rolled 6.\footnote{Notice that we're assuming the dice are
distinguishable---say they are different colors---so we know which is
which.  We would need a different sample space of outcomes if we regarded
the dice as \emph{in}distinguishable.}

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

We usually declare some subset of the possible outcomes in the sample
space to be ``good'' or ``interesting.''  Any subset of the sample space
is called an \emph{event}.

For example, the event that all dice are the same consists of six
possible outcomes 
\[
\set{(1,1,1),(2,2,2),(3,3,3),(4,4,4),(5,5,5),(6,6,6)}.
\]

Let $T$ be the event that we roll exactly two sixes.  $T$ has $3\cdot
5=15$ possible outcomes: we need to choose which die is not a six, and
then we need to choose a value for that die.  Namely,
\begin{align*}
T \eqdef  \{ &(1,6,6), (2,6,6), (3,6,6) , (4,6,6) , (5,6,6), \\ 
             &(6,1,6) , (6,2,6),  (6,3,6) , (6,4,6) , (6,5,6),\\
             & (6,6,1) , (6,6,2) , (6,6,3) , (6,6,4) , (6,6,5)\}
\end{align*}
Our goal is to determine the probability that our experiment yields
one of the outcomes in this set $T$.

\subsection*{Step 3: Specify Outcome Probabilities}

Assign a real number between zero and one, called a \emph{probability}, to
each outcome of an experiment so that the sum of the probabilities of all
the outcomes is one.  This is called specifying a \emph{probability space}
appropriate to the experiment.  We use the notation, $\pr{w}$, to denote
the probability of an outcome $w$.

\iffalse
\subsection{Assumptions}
\fi

Assigning probabilities to the atomic outcomes is an \emph{axiomatic}
action.  One of the philosophical bases for probability says that the
probability for an outcome should be the fraction of times that we expect
to see that outcome when we carry out a large number of experiments.
Thinking of the probabilities as fractions of one whole set of outcomes
makes it plausible that probabilities should be nonnegative and sum to
one.

In our experiment (and in many others), it seems quite plausible to
say that all the possible outcomes are equally likely.  Probability spaces
of this kind are called \emph{uniform}:

\begin{definition}
A \emph{uniform} probability space is a finite space in which all the
outcomes have the same probability.  That is, if $\sspace$ is the sample
space, then
\[
\pr{w}=\frac{1}{\card{\sspace}}
\]
for every outcome $w\in \sspace$.
\end{definition}

Since there are $6^3=216$ possible outcomes, we axiomatically declare
that each occurs with probability $1/216$.

\subsection*{Step 4: Compute Event Probabilities}

We now have a probability for each outcome.  To compute the probability of
the event, $T$, that we get exactly two sixes, we add up the probabilities
of all the outcomes that yield exactly two sixes.  In our example, since
there are $15$ outcomes in $T$, each with probability $1/216$, we can
deduce that $\pr{T}=15/216$.

\iffalse

\subsection{Coin Tossing}

Here's another simple example.  Imagine that perform 100 tosses of a
fair coin.  What is the probability that we get an even number of
heads?  We apply the four-step analysis:

\begin{description}
\item[Define the sample space.] We can represent a sequence of 100
  tosses as a length-100 sequence of letters $H$ and $T$; for example
  the an outcome of alternating heads and tails can be written as
  $HTHTHTHT\cdots$.  

\item[Define the interesting event.] We are interested in sequences
  with an even number of $H$ symbols in them.

\item[Assign probabilities to the atomic events.] We will assume
  the coin is fair and is tossed fairly, so we declare that all the
  outcomes are equally likely.  Since our sample space has $2^{100}$
  elements, each has probability $2^{-100}$.  This assumption is a
  strong one: a certain famous mathematician can get heads 3 times out
  of 4 on a fair coin (this took lots of practice using a strobe
  light).

\item[Determine the interesting event probability.]  Since the sample
  space is uniform, this comes down to determining the number of
  sequences with an even number of heads.  We have seen this problem
  before in another guise.  For each sequence, consider a
  corresponding set: the set of coin-toss-numbers (between 1 and 100)
  that yielded heads.  There is an even number of heads precisely when
  the corresponding set is even.  So we just need to count the number
  of even subsets of $\set{1,\dots,100}$.  We saw before that this is
  $2^{99}$.

  So, the overall probability of our event is just
  $2^{99}\cdot2^{-100}=1/2$.
\end{description}


Probability provides a kind of normalization that often makes for
answers that are more pleasant to write down.  For example, our
analysis above really generalizes to say that for any number of coin
tosses, the probability that I get an even number of heads is 1/2---I
have normalized away any dependence on the number of coin tosses.  I
can obviously switch back to the counting version if I just multiply
the probability by the number of outcomes.
\fi

Probability on a uniform sample space such as this one is pretty much the
same as counting.  Another example where it's reasonable to use a uniform
space is for poker hands.  Instead of asking how many distinct full houses
there are in poker, we can ask about the probability that a ``random''
poker hand is a full house.  For example, of the $\binom{52}{5}$ possible
poker hands, we saw that
\begin{itemize}
\item There are 624 ``four of a kind'' hands, so the probability of 4 of a
kind is $624 / \binom{52}{5} = 1/4165$.
\item There are 3744 ``full house'' hands, so the probability of a
  full house is $6/4165\approx 1/694$.
\item There are 123,552 ``two pair'' hands, so the probability of two
  pair $\approx 1/21$.
\end{itemize}

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

In the 1970's, there was a game show called
\href{http://www.letsmakeadeal.com/index.htm}{Let's Make a Deal}, hosted
by Monty Hall and his assistant Carol Merrill.  At one stage of the game,
a contestant is shown three doors.  The contestant knows there is a prize
behind one door and that there are goats behind the other two.  The
contestant picks a door.  To build suspense, Carol always opens a
\emph{different} door, revealing a goat.  The contestant can then stick
with his original door or switch to the other unopened door.  He wins the
prize only if he now picks the correct door.  Should the contestant
``stick'' with his original door, ``switch'' to the other door, or does it
not matter?

\iffalse Hide these two sentences after Monty demo in lecture by
pdflatexing & answering ``y'' to ``include solutions''\fi

\instatements{Intuitive reasoning about this question misleads many
people.  We'll apply our four step discipline for computing probabilities
to arrive at a sound answer after we do a \emph{Let's Make a Deal}
demonstration in class on Monday, November 4.}

\iffalse Unhide the following paragraphs after the Monty demo in lecture
by pdflatexing & answering ``y'' to ``include solutions''\fi

\insolutions{This was the subject of an
\href{http://www.cut-the-knot.com/hall.html}{``Ask Marilyn'' column} in
{\em Parade} Magazine a few years ago.  Marilyn wrote that your chances of
winning were $2/3$ if you switched --- because if you switch, then you win
if the prize was originally behind either of the two doors you didn't
pick.  Now, Marilyn has been listed in the {\em Guiness Book of World
Records} as having the world's highest IQ, but for this answer she got a
tidal wave of critical mail, some of it from people with Ph.D.'s in
mathematics, telling her she was wrong.  Most of her critics insisted that
the answer was 1/2, on the grounds that the prize was equally likely to be
behind each of the doors, and since the contestant knew he was going to
see a goat, it remains equally likely which the two remaining doors has
the prize behind it.  The pros and cons of these arguments
\href{http://www.wiskit.com/marilyn.gameshow.html}{still stimulate
debate}.

It turned out that Marilyn was right, but given the debate, it is clearly
not apparent which of the intuitive arguments for 2/3 or 1/2 is reliable.
Rather than try to come up with our own explanation in words, let's use
our standard approach to finding probabilities.  In particular, we will
analyze the probability that the contestant wins with the ``switch''
strategy; that is, the contestant chooses a random door initially and then
always switches after Carol reveals a goat behind one door.  We break the
down into the standard four steps.

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

In the Monty Hall problem, an outcome is a triple of door numbers:

\begin{enumerate}
\item The number of the door concealing the prize.
\item The number of the door initially chosen by the contestant.
\item The number of the door Carol opens to reveal a goat.
\end{enumerate}

For example, the outcome $(2, 1, 3)$ represents the case where the
prize is behind door 2, the contestant initially chooses door 1, and
Carol reveals the goat behind door 3.  In this case, a contestant
using the ``switch'' strategy wins the prize.

Not every triple of numbers is an outcome; for example, $(1, 2, 1)$ is
not an outcome, because Carol never opens the door with the prize.
Similarly, $(1, 2, 2)$ is not an outcome, because Carol does not open
the door initially selected by the contestant, either.

As with counting, a tree diagram is a standard tool for studying the
sample space of an experiment.  The tree diagram for the Monty Hall
problem is shown in Figure~\ref{fig:monty}.  Each vertex in the tree
corresponds to a state of the experiment.  In particular, the root
represents the initial state, before the prize is even placed.
Internal nodes represent intermediate states of the experiment, such
as after the prize is placed, but before the contestant picks a door.
Each leaf represents a final state, an outcome of the experiment.  One
can think of the experiment as a walk from the root (initial state) to
a leaf (outcome).  In the figure, each leaf of the tree is labeled
with an outcome (a triple of numbers) and a ``W'' or ``L'' to indicate
whether the contestant wins or loses.


\begin{figure}[htbp]
\centerline{\includegraphics[height=3.5in]{figures/monty}}
\caption{This is a tree diagram for the Monty Hall problem.  Each
of the 12 leaves of the tree represents an outcome.  A ``W'' next to
an outcome indicates that the contestant wins, and an ``L'' indicates
that he loses.}
\label{fig:monty}
\end{figure}

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

For the Monty Hall problem, let $\sspace$ denote the sample space, the set
of all 12 outcomes shown in Figure~\ref{fig:monty}.  The event $W
\subset \sspace$ that the contestant wins with the ``switch'' strategy
consists of six outcomes:
\[
W \eqdef \set{ (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)}.
\]
The event $L \subset \sspace$ that the contestant loses is the
complementary set:
\[
L \eqdef \set{ (1,1,2), (1,1,3), (2,2,1), (2,2,3), (3,3,1), (3,3,2)}.
\]

Our goal is to determine the probability of the event $W$; that is,
the probability that the contestant wins with the ``switch'' strategy.

Well, the contestant wins in 6 outcomes and loses in 6 outcomes.  Does
this not imply that the contestant has a $6/12 = 1/2$ chance of winning?
No!  Under our natural assumptions, this sample space is not uniform!
Some outcomes may be more likely than others.  We must compute the
probability of each outcome.

\subsection*{Step 3:  Compute Outcome Probabilities}

\subsection{Assumptions}

To assign a meaningful probability to each outcome in the Monty Hall
problem, we must make some assumptions.  The following three are
sufficient:

\begin{enumerate}
\item The prize is placed behind each door with probability $1/3$.
\item No matter where the prize is placed, the contestant picks each door
with probability $1/3$.
\item No matter where the prize is placed, if Carol has a choice of
which door to open, then she opens each possible door with equal
probability.
\end{enumerate}

The first two assumptions capture the idea that the contestant initially
has no idea where the prize is placed.  The third assumption eliminates
the possibility that Carol somehow secretly communicates the location of
the prize by which door she opens.  Assumptions of this sort almost always
arise in probability problems; making them explicit is a good idea,
although in fact not all of these assumptions are absolutely necessary.
For example, it doesn't matter how Carol chooses a door to open in the
cases when she has a choice, though we won't prove this.

\subsection{Assigning Probabilities to Outcomes}

With these assumptions, we can assign probabilities to outcomes in the
Monty Hall problem by a calculation illustrated in
Figure~\ref{fig:monty2} and described below.  There are two steps.

\begin{figure}[htbp]
\centerline{\includegraphics[height=3.5in]{figures/monty2}}
\caption{This is the tree diagram for the Monty Hall problem,
annotated with probabilities for each outcome.}
\label{fig:monty2}
\end{figure}

The first step is to record a probability on each edge in the tree
diagram.  Recall that each node represents a state of the experiment,
and the whole experiment can be regarded as a walk from the root
(initial state) to a leaf (outcome).  The probability recorded on an
edge is the probability of moving from the state corresponding to the
parent node to the state corresponding to the child node.  These edge
probabilities follow from our three assumptions about the Monty Hall
problem.

Specifically, the first assumption says that there is a $1/3$ chance that
the prize is placed behind each of the three doors.  This gives the
1/3 probabilities on the three edges from the root.  The second
assumption says that no matter how the prize is placed, the contestant
opens each door with probability $1/3$.  This gives the $1/3$
probabilities on edges leaving the second layer of nodes.  Finally, the
third assumption is that if Carol has a choice of what door to open, then
she opens each with equal probability.  In cases where Carol has no
choice, edges from the third layer of nodes are labeled with probability
$1$.  In cases where Carol has two choices, edges are labeled with
probability $1/2$.

The second step is to use the edge weights to compute a probability for
each outcome by multiplying the probabilities along the edges leading to
the outcome.  This way of assigning probabilities reflects our idea that
probability measures the fraction of times that a given outcome should
happen over the course of many experiments.  Suppose we want the
probability of outcome $(2, 1, 3)$.  In $1/3$ of the experiments, the
prize is behind the second door.  Then, in $1/3$ of these experiments when
the prize is behind the second door, and the contestant opens the first
door.  After that, Carol has no choice but to open the third door.
Therefore, the probability of the outcome is the product of the edge
probabilities, which is
\[
\frac{1}{3} \cdot \frac{1}{3} \cdot 1 = \frac{1}{9}.
\]
For example, the probability of outcome $(2, 2, 3)$ is the product of
the edge probabilities on the path from the root to the leaf labeled
$(2, 2, 3)$.  Therefore, the probability of the outcome is
\[
\frac{1}{3} \cdot \frac{1}{3} \cdot \frac{1}{2} = \frac{1}{18}.
\]
Similarly, the probability of outcome $(3, 1, 2)$ is
\[
\frac{1}{3} \cdot \frac{1}{3} \cdot 1 = \frac{1}{9}.
\]
The other outcome probabilities are worked out in Figure~\ref{fig:monty2}.

\iffalse
Notice that we cannot \emph{prove} that these are the right probabilities
to assign, because the assignment of probabilities to atomic outcomes is
\emph{axiomatic}.  Someone could choose another assignment to model the
Monty Hall game, and develop a consistent theory of probabilities for
door-picking strategies.

\fi

\subsection*{Step 4: Compute Event Probabilities}

We now have a probability for each outcome.  All that remains is to
compute the probability of $W$, the event that the contestant wins with
the ``switch'' strategy.  The probabilility of an event is
simply the sum of the probabilities of all the outcomes in it.  So the
probability of the contestant winning with the ``switch'' strategy is the
sum of the probabilities of the six outcomes in event $W$, namely,
$2/3$:
\begin{eqnarray*}
\pr{W} & \eqdef & \pr{(1,2,3)} + \pr{(1,3,2)} + \pr{(2,1,3)} +
\pr{(2,3,1)} + \pr{(3,1,2)} + \pr{(3,2,1)} \\
         & = & \frac{1}{9} + \frac{1}{9} + \frac{1}{9} +
\frac{1}{9} + \frac{1}{9} + \frac{1}{9} \\
         & = & \frac{2}{3}.
\end{eqnarray*}

In the same way, we can compute the probability that a contestant loses
with the ``switch'' strategy.  This is the probability of event $L$:
\begin{eqnarray*}
\pr{L} & \eqdef & \pr{(1,1,2)} + \pr{(1,1,3)} + \pr{(2,2,1)} +
\pr{(2,2,3)} + \pr{(3,3,1)} + \pr{(3,3,2)} \\
& = & \frac{1}{18} + \frac{1}{18} + \frac{1}{18} + \frac{1}{18} +
\frac{1}{18} + \frac{1}{18}\\
& = & \frac{1}{3}.
\end{eqnarray*}

The probability of the contestant losing with the switch strategy is
$1/3$.  This makes sense; the probability of winning and the probability
of losing ought to sum to 1!

We can determine the probability of winning with the ``stick'' strategy
without further calculations.  In every case where the ``switch'' strategy
wins, the ``stick'' strategy loses, and vice versa.  Therefore, the
probability of winning with the stick strategy is $1 - 2/3 = 1/3$.

Solving the Monty Hall problem formally requires only simple addition
and multiplication.  But trying to solve the problem with ``common
sense'' leaves us running in circles!
}

%% END OF MONTY HALL HIDE

\section{Intransitive Dice}\label{intrans-dice}

\hyperdef{ln10}{intrans-dice}{There is a game involving three dice and two
players.}  The dice are not normal; rather, they are numbered as shown in
Figure~\ref{fig:dice}.  Each hidden face has the same number as the
opposite, exposed face.  As a result, each die has only three distinct
numbers, and each number comes up $1/3$ of the time.

\begin{figure}[htbp]
\begin{center}
\includegraphics[height=1.5in]{figures/dice}
\end{center}
\caption{This figure shows the strange numbering of the three dice
``intransitive'' dice.  The number on each concealed face is the same as
the number on the exposed, opposite face.}
\label{fig:dice}
\end{figure}

In the game, the first player can choose any one of the three dice.  Then
the second player chooses one of the two remaining dice.  They both
roll and the player with the higher number wins.  Which of the three
dice should player one choose?  That is, which of the three dice is
best?

% \forlecture{\bf 3 beats 2, 2 beats 1, 1 beats 3}

% \forlecture{\bf I'm much better at this game than at magic, since it involves luck rather than skill}

For example, die $B$ is attractive, because it has a 9, the highest number
overall; on the other hand, it also has a 1, the lowest number.  Intuition
gives no clear answer!  We can solve the problem with our standard
four-step method.

\begin{claim}
Die $A$ beats die $B$ more than half of the time.
\end{claim}

\begin{proof}
The claim concerns the experiment of throwing dice $A$ and $B$.

{\em Step 1: Find the Sample Space. } The sample space for this
experiment is indicated by the tree diagram in
Figure~\ref{fig:diceAB}.

{\em Step 2: Define Events of Interest. } We are interested in the
event that die $A$ comes up greater than die $B$.  The outcomes in
this event are marked ``A'' in the figure.

{\em Step 3: Compute Outcome Probabilities. } To find outcome
probabilities, we first assign probabilities to edges in the tree
diagram.  Each number comes up with probability $1/3$,
regardless of the value of the other die.  Therefore, we assign all
edges probability $1/3$.  The probability of an outcome is the
product of probabilities on the corresponding root-to-leaf path; this
means that every outcome has probability $1/9$.

{\em Step 4: Compute Event Probabilities. } The probability of an
event is the sum of the probabilities of the outcomes in the event.
Therefore, the probability that die $A$ comes up greater than die
``B'' is 
\[
\frac{1}{9} + \frac{1}{9} + \frac{1}{9} + \frac{1}{9} +
\frac{1}{9} = \frac{5}{9}.
\]

As claimed, the probability that die $A$ beats die $B$ is greater than
half.

\begin{figure}[htbp]
\centerline{\includegraphics[height=3.5 in]{figures/diceAB}}
\caption{This is the tree diagram arising when die $A$ is played
against die $B$.  Die $A$ beats die $B$ with probability $5/9$.}
\label{fig:diceAB}
\end{figure}
\end{proof}

The analysis may be even clearer by giving the outcomes in a table:
\begin{center}
\begin{tabular}{|l|c|c|c|c|} \hline
\multicolumn{2}{|l|}{Winner}  & \multicolumn{3}{c|}{B roll} \\ \cline{3-5}
\multicolumn{2}{|l|}{}     
         & 1   & 5    & 9 \\ \hline
      &2 & A   & B    & B \\ \cline{2-5}
A roll&6 & A   & A    & B \\ \cline{2-5}
      &7 & A   & A    & B \\ \hline
\end{tabular}
\end{center}
All the outcomes are equally likely, and we see that A wins 5 of
them.  This table works because our probability space is based on 2
pieces of information, A's roll and B's roll.  For more complex
probability spaces, the tree diagram is necessary.


\begin{claim}
Die $B$ beats die $C$ more than half of the time.
\end{claim}

\begin{proof}
The proof is by the same case analysis as for the preceding claim,
summarized in the table:

\begin{center}
\begin{tabular}{|l|c|c|c|c|} \hline
\multicolumn{2}{|l|}{Winner}  & \multicolumn{3}{c|}{C roll} \\ \cline{3-5}
\multicolumn{2}{|l|}{}     
         & 3   & 4    & 8 \\ \hline
      &1 & C   & C    & C \\ \cline{2-5}
B roll&5 & B   & B    & C \\ \cline{2-5}
      &9 & B   & B    & B \\ \hline
\end{tabular}
\end{center}

\iffalse
\begin{figure}[htbp]
\centerline{\includegraphics[height=3.5in]{figures/diceBC}}
\caption{Die $B$ beats die $C$ with probability $5/9$.}
\label{fig:diceBC}
\end{figure}
\fi

\end{proof}

We have shown that $A$ beats $B$ and that $B$ beats $C$.  From these
results, we might conclude that $A$ is the best die, $B$ is second
best, and $C$ is worst.  But this is totally wrong!

\begin{claim}
Die $C$ beats die $A$ more than half of the time!
\end{claim}

\begin{proof}
See the tree diagram in Figure~\ref{fig:diceCA}.  Again, we can present
this analysis in a tabular form:
\begin{center}
\begin{tabular}{|l|c|c|c|c|} \hline
\multicolumn{2}{|l|}{Winner}  & \multicolumn{3}{c|}{A roll} \\ \cline{3-5}
\multicolumn{2}{|l|}{}     
         & 2   & 6    & 7 \\ \hline
      &3 & C   & A    & A \\ \cline{2-5}
C roll&4 & C   & A    & A \\ \cline{2-5}
      &8 & C   & C    & C \\ \hline
\end{tabular}
\end{center}

\begin{figure}[htbp]
\centerline{\includegraphics[height=3.5in]{figures/diceCA}}
\caption{Die $C$ beats die $A$ with probability $5/9$.  Amazing!}
\label{fig:diceCA}
\end{figure}

\end{proof}

Die $A$ beats $B$, $B$ beats $C$, and $C$ beats $A$!  Apparently,
there is no ``transitive law'' here!  This means that no matter what
die the first player chooses, the second player can choose a die that
beats it with probability $5/9$.  The player who picks first is
always at a disadvantage!

\begin{optional}

The same effect can arise with three dice numbered the ordinary way,
but ``loaded'' so that some numbers turn up more often.  For example,
suppose:

\begin{eqnarray*}
A & \mbox{rolls} & \mbox{$3$ with probability 1} \\
\\
B & \mbox{rolls} & \mbox{$2$ with probability
                                $p \eqdef (\sqrt{5} - 1)/2 = 0.618\dots$} \\
  & \mbox{rolls} & \mbox{$5$ with probability $1-p$} \\
\\
C & \mbox{rolls} & \mbox{$1$ with probability $1-p$} \\
  & \mbox{rolls} & \mbox{$4$ with probability $p$} \\
\end{eqnarray*}

It's clear that $A$ beats $B$, and $C$ beats $A$, each with probability
$p$.  But note that $1 - p^2 = p$.  Now the probability that $B$ beats $C$
is
\[
\prob{\text{B rolls to 5}} + \prob{\text{B rolls to 2 and C rolls to 1}}
= (1-p) + p(1-p) = 1 - p^2 = p.
\]
So $A$ beats $B$, $B$ beats $C$, and C beats $A$, all
with probability $p = 0.618\dots > 5/9$.

\end{optional}


\section{Set Theory and Probability}

Having gone through these examples, we should be ready to make sense of
the formal definitions of basic probability theory.

\subsection{Basic Laws of Probability}

\begin{definition}
\label{sampsp}
A \emph{sample space}, $\sspace$, is a nonempty set whose elements are
called \emph{outcomes}.  The \emph{events} are subsets of
$\sspace$.\footnote{\label{foot-nolength} \iffalse

A \emph{countable} set, $S$, is one whose elements can be listed in some
order: $s_0,s_1,\dots$; formally $\sspace$ is countable if $\sspace$ is
finite, or there is a bijection from $\naturals$ to $\sspace$.  When
$\sspace$ is countable, which is the case for nearly all examples in
6.042, we can, and indeed must, let every subset of $\sspace$ be an event.
\fi
For all the examples in 6.042, we let every subset of $\sspace$ be an event.
However, when $\sspace$ is a set such as the unit interval of real numbers,
there can be problems.  In this case, we typically want subintervals of
the unit interval to be events with probability equal to their length.
For example, we'd say that if a dart hit ``at random'' in the unit
interval, then the probability that it landed within the subinterval from
1/3 to 3/4 was equal to the length of the interval, namely 5/12.

Now it turns out to be inconsistent with the axioms of Set Theory to
insist that \emph{all} subsets of the unit interval be events.  Instead,
the class of events must be limited to rule out certain pathological
subsets which do not have a well-defined length.  An example of such a
pathological set is the real numbers between zero and one with an infinite
number of fives in the even-numbered positions of their decimal
expansions.  Fortunately, such pathological subsets are not relevant in
applications of Probability Theory.

The results of the Probability Theory hold as long as we have some set of
events with a few basic properties: every finite set of outcomes is an
event, the whole space is an event, the complement of an event is an
event, and if $A_0,A_1,\dots$ are events, so is $\lgunion_{i \in
\naturals} A_i$.  It is easy to come up with such a class of events that
includes all the events we care about and leaves out all the pathological
cases.}

\end{definition}

\begin{definition*}
A family, $\mathcal{F}$, of sets is \emph{pairwise disjoint} if the
intersection of every pair of distinct sets in the family is empty, \ie if
$A,B \in \mathcal{F}$ and $A \neq B$, then $A \intersect B =\emptyset$.
In this case, if $\sspace = \lgunion \mathcal{F}$, then $\sspace$ is said
to be the \emph{disjoint union} of the sets in $\mathcal{F}$.
\end{definition*}

\begin{definition}\label{probsp}
\hyperdef{ln10}{probsp}{A \emph{probability space}} consists of a sample
space, $\sspace$, and a \emph{probability function}, $\pr{}$, mapping the
events of $\sspace$ to real numbers between zero and one, such that:
\begin{enumerate}
\item $\pr{\sspace} =1$, and

\item if $A_0,A_1,\dots$ is a sequence of disjoint events, then
\begin{equation}\tag{Sum Rule}
\pr{\lgunion_{i\in\naturals}A_i} = \sum_{i\in\naturals} \pr{A_i}.
\end{equation}

\end{enumerate}
\end{definition}

The Sum Rule\footnote{If you think like a Mathematician, you should be
   wondering if the infinite sum is really necessary.  Namely, suppose we
   had only used finite sums in Definition~\ref{probsp} instead of sums
   over all natural numbers.  Would this imply the result for infinite
   sums?  It's hard to find counterexamples, but there are some: it is
   possible to find a pathological ``probability'' measure on a sample
   space satisfying the Sum Rule for finite unions, in which the outcomes
   $w_0,w_1,\dots$ each have probability zero, and the probability
   assigned to any event is either zero or one!  So the infinite Sum Rule
   fails dramatically, since the whole space is of measure one, but it is
   a union of the outcomes of measure zero.

   The construction of such weird examples is beyond the scope of 6.042.  You
   can learn more about this by taking a course in Set Theory and Logic that
   covers the topic of ``ultrafilters.''}
lets us analyze a complicated event by breaking it down into simpler
cases.  For example, if the probability that a randomly chosen MIT student
is native to the United States is 60\%, to Canada is 5\%, and to Mexico is
5\%, then the probability that a random MIT student is native to North
America is 70\%.

One immediate consequence of Definition~\ref{probsp} is that $\pr{A} +
\pr{\bar{A}} = 1$ because $\sspace$ is the disjoint union of $A$ and
$\bar{A}$.  This equation often comes up in the form
\begin{equation}\tag{Complement Rule}
\pr{\bar{A}}  =  1 - \pr{A}.
\end{equation}

Some further basic facts about probability parallel facts about
cardinalities of finite sets.  In particular:
\begin{align}
\pr{B-A} & =  \pr{B} - \pr{A \intersect B}\tag{Difference Rule}\\
\pr{A \union B} & =  \pr{A} + \pr{B} - \pr{A \intersect B}
                  \tag{Inclusion-Exclusion}
\end{align}
The Difference Rule follows from the Sum Rule because $B$ is the disjoint
union of $B-A$ and $A \intersect B$.  The (Inclusion-Exclusion) equation
then follows from the Sum and Difference Rules, because $A \union B$ is
the disjoint union of $A$ and $B-A$, so
\[
\pr{A \union B} = \pr{A} + \pr{B-A} = \pr{A} + (\pr{B} - \pr{A \intersect B}).
\]
This (Inclusion-Exclusion) equation is the Probability Theory version of
the
\hyperref{http://theory.lcs.mit.edu/classes/6.042/fall02/handouts/lectures/ln8.pdf}
{rule}{incl-excl}{Inclusion-Exclusion Principle} for the size of the union
of two finite sets.  It generalizes to $n$ events in a corresponding way.
An immediate consequence of (Inclusion-Exclusion) is
\begin{equation}
\pr{A \union B} \le  \pr{A} + \pr{B}. \tag{Boole's Inequality}
\end{equation}
Similarly, the Difference Rule implies that
\hyperdef{ln10}{monotonicity}{
\begin{equation}\label{subsetbound}
\text{If } A \subseteq B, \text{ then } \pr{A} \le \pr{B}.\tag{Monotonicity}
\end{equation}
}

In the examples we considered above, we used the fact that the probability
of an event was the sum of the probabilities of its outcomes.  This
follows as a trivial special case of the Sum Rule with one quibble:
according to the official definition, the probability function is defined
on \emph{events} not outcomes.  But we can always treat an outcome as the
event whose only element is that outcome, that is, define $\pr{w}$ to be
$\pr{\set{w}}$.  Then, for the record, we can say

\begin{corollary}
If $A = \set{w_0,w_1,\dots}$ is an event, then
\[
\pr{A} = \sum_{i \in \naturals} \pr{w_i}.
\]
\end{corollary}

\iffalse

\begin{proof}
Since $A$ is countable, we have $A = \set{w_0,w_1,\dots}$.
So by definition,
\begin{eqnarray}
A & = & \lgunion_{i \in \naturals} \set{w_i}, \text{ and} \label{AUi}\\
\sum_{w \in A} \pr{w} & = & \sum_{i \in \naturals} \pr{w_i}.\label{sumw}
\end{eqnarray}
Now by the Sum Rule,
\begin{equation}\label{prU}
\pr{\lgunion_{i \in \naturals} \set{w_i}} = \sum_{i \in \naturals} \pr{w_i}.
\end{equation}
So from~(\ref{AUi}) and~(\ref{prU}), we have
\begin{equation}\label{prA}
\pr{A} = \sum_{i \in \naturals} \pr{w_i}.
\end{equation}
Combining~(\ref{prA}) with~(\ref{sumw}) completes the proof.
\end{proof}

Notice that the fact that the sum above and the sum in
Definition~\ref{probsp} is over the natural numbers is important.  
For example, if our probability space was the real interval
because there is no useful way to define a
convergent sum of an uncountable number of events that each have nonzero
probability.
\fi

\subsection{Circuit Failure}\label{crct}

Suppose you are wiring up a circuit containing a total of
$n$~connections. From past experience we assume that any particular
connection is made \emph{incorrectly} with probability~$p$, for some $0
\leq p \leq 1$.  That is, for $1 \leq i \leq n$,
\begin{displaymath}
  \pr{\mbox{$i$th connection is wrong}} = p.
\end{displaymath}
What can we say about the probability that the circuit is wired
correctly, \ie that it contains no incorrect connections?
 
Let $A_i$ denote the event that connection~$i$ is made
\emph{correctly}.  Then $\bar{A_i}$ is the event that connection~$i$
is made incorrectly, so $\pr{\bar{A_i}} = p$.  Now 
\begin{displaymath}
  \pr{\mbox{all connections are OK}} = \pr{\lgintersect_{i=1}^n A_i}.
\end{displaymath}

Without any additional assumptions, we can't get an exact answer.
However, we can give reasonable upper and lower bounds. For an upper
bound, we can see that
\begin{displaymath}
  \pr{\bigcap_{i=1}^n A_i} =
  \pr{A_1 \cap (\bigcap_{i=2}^n A_i)} \leq
  \pr{A_1} = 1 - p
\end{displaymath}
by Monotonicity.  For a lower bound, we can see that
\begin{displaymath}
  \pr{\bigcap_{i=1}^n A_i}
  = 1 - \pr{\overline{\bigcap_{i=1}^n A_i}}
  = 1 - \pr{\bigcup_{i=1}^n \bar{A_i}}
  \geq 1 - \sum_{i=1}^n \pr{\bar{A_i}} = 1 - np,
\end{displaymath}
where the $\ge$-inequality follows from Boole's Law.

So for example, if $n = 10$ and $p = 0.01$, we get the following
bounds:
\begin{displaymath}
  0.9 = 1 - 10\cdot 0.01
  \leq \pr{\mbox{all connections are OK}} \leq
  1-0.01 = 0.99.
\end{displaymath}
So we have concluded that the chance that all connections are okay is
somewhere between 90\% and 99\%. Could it actually be as high as 99\%?
Yes, if the errors occur in such a way that all connection errors always
occur at the same time.

Could it be 90\%? Yes, suppose the errors are such that we never make
two wrong connections. In other words, the events $\overline{A_i}$ are
all disjoint and the probability of getting it right is
\begin{displaymath}
  \pr{\lgintersect A_i}  =  1 - \pr{\lgunion \overline{A_i}}
  = 1 - \sum_{i=1}^{10} \pr{\overline{A_i}} = 1-10\cdot 0.01 = 0.9.
\end{displaymath}

\section{Combinations of Events}

\subsection{Carnival Dice}\label{carnival}

\hyperdef{ln10}{carnival}{There is a gambling game called Carnival Dice.}
A player picks a number between 1 and 6 and then rolls three \emph{fair}
dice---``fair'' means each number is equally likely to show up on a die.
The player wins if his number comes up on at least one die.  The player
loses if his number does not appear on any of the dice.  What is the
probability that the player wins?  This problem sounds simple enough that
we might try an intuitive lunge for the solution.
\begin{falseclm}
  The player wins with probability $1/2$.
\end{falseclm}
\begin{falseproof}
  Let $A_i$ be the event that the $i$th die matches the player's guess.
  \begin{eqnarray}
    \pr{win} & = & \pr{A_1 \cup A_2 \cup A_3} \\
             & = & \pr{A_1} + \pr{A_2} + \pr{A_3}\label{bug} \\
             & = & \frac{1}{6} + \frac{1}{6} + \frac{1}{6} \\
             & = & \frac{1}{2}
  \end{eqnarray}
\end{falseproof}
The justification for the equality~(\ref{bug}) is that the union is
disjoint.  This may seem reasonable in a vague way, but in a precise way
it's not.  To see that this is a silly argument, note that it would also
imply that with six dice, our probability of getting a match is 1, \ie it
is sure to happen.  This is clearly false---there is some chance that none
of the dice match.\footnote{On the other hand, the idea of adding these
probabilities is not completely absurd.  We will see in \hyperref
{http://theory.lcs.mit.edu/classes/6.042/fall02/handouts/lectures/ln11-12.pdf}
{ln11}{linearity}{Course Notes 11} that adding would work to compute the
\emph{average} number of matching dice: 1/2 a match per game with three
dice and one match per game in the game with six dice.}

To compute the actual chance of winning at Carnival Dice, we can use
Inclusion-Exclusion for three sets.  The probability that one die matches
the player's guess is $1/6$.  The probability that two particular dice
both match the player's guess is $1/36$: there are 36 possible outcomes of
the two dice and exactly one of them has both equal to the player's guess.
The probability that all three dice match is $1/216$.  Inclusion-Exclusion
gives:
\[
\pr{\mbox{win}}  =  \frac{1}{6} + \frac{1}{6} + \frac{1}{6}
     - \frac{1}{36} - \frac{1}{36} - \frac{1}{36} 
     + \frac{1}{216}
   =  \frac{91}{216} \approx 42\%.
\]
\iffalse
\begin{eqnarray*}
  \pr{\mbox{win}} & = & \frac{1}{6} + \frac{1}{6} + \frac{1}{6} \\
  & & \mbox{}     - \frac{1}{36} - \frac{1}{36} - \frac{1}{36} \\
  & & \mbox{}     + \frac{1}{216} \\
  & = & \frac{91}{216} \approx 42\%.
\end{eqnarray*}\fi

These are terrible odds in a gambling game; it is much better to play
roulette, craps, or blackjack!

\subsection{More Intransitive Dice [Optional]}

\begin{optional}

In Section~\ref{intrans-dice}, we described three dice $A$, $B$ and $C$
such that the probabilities of $A$ beating $B$, $B$ beating $C$, $C$
beating $A$ are each $p \eqdef (\sqrt{5} - 1)/2 \approx 0.618$.  Can we
increase this probability?  For example, can we design dice so that each
of these probabilities are, say, at least 3/4?  The answer is ``No.''  In
fact, using the elementary rules of probability, it's easy to show that
these ``beating'' probabilities cannot all exceed 2/3.

In particular, we consider the experiment of rolling all three dice, and
define $[A]$ to be the event that $A$ beats $B$, $[B]$ the event that $B$
beats $C$, and $[C]$ the event that $C$ beats $A$.

\begin{claim*}
\begin{equation}\label{m23}
\min \set{\prob{[A]}, \prob{[B]}, \prob{[C]}} \leq \frac{2}{3}.
\end{equation}
\end{claim*}

\begin{proof}
Suppose dice $A,B,C$ roll numbers $a,b,c$.  Events $[A],[B],[C]$ all occur on
this roll iff $a>b,b>c,c>a$, so in fact they cannot occur simultaneously.
That is,
\begin{equation}\label{ABCemp}
[A] \intersect [B] \intersect [C] = \emptyset.
\end{equation}
Therefore,
\begin{align*}
0 = & \prob{[A] \intersect [B] \intersect [C]} & \text{(by~(\ref{ABCemp}))}\\
     = & 1 - \prob{\bar{[A]} \union \bar{[B]} \union \bar{[C]}} 
          & \mbox{(Complement Rule and DeMorgan)}\\
     \geq & 1 - (\prob{\bar{[A]}}+ \prob{\bar{[B]}} + \prob{\bar{[C]}}
                & \mbox{(Boole's Inequality)}\\
     = & \prob{[A]} + \prob{[B]} + \prob{[C]}) - 2 & \mbox{(Complement Rule)}\\
    \geq & 3 \min \set{\prob{[A]},\prob{[B]},\prob{[C]}} - 2.
               & \text{(def of $\min$)}
\end{align*}
Hence
\[
2  \geq 3 \min \set{\prob{[A]},\prob{[B]},\prob{[C]}},
\]
proving~(\ref{m23}).
\end{proof}

\iffalse
\begin{problem*}Prove there is no way to load the dice to
make $p$ greater than $(\sqrt{5} - 1)/2$.
\end{problem*}

%% This is claimed in FAll 99, H67-tut17, prob 3.  I DON'T KNOW how hard
%% it is to prove.  
\fi

\end{optional}

\subsection{Derangements [Optional]}

\begin{optional}

Suppose we line up two randomly ordered decks of $n$ cards against each
other.  What is the probability that at least one pair of cards
``matches''?  Let $A_i$ be the event that card $i$ is in the same place in
both arrangements.  We are interested in $\pr{\lgunion A_i}$.  To apply the
Inclusion-Exclusion formula, we need to compute the probabilities of
individual intersection events---namely, to determine the probability
$\pr{A_{i_1}\cap A_{i_2} \cap \cdots\cap A_{i_k}}$ that a particular set
of $k$ cards matches.  To do so we apply our standard four steps.
\begin{description}

\item[The sample space.] The sample space involves a permutation of
  the first card deck and a permutation of the second deck.  We can
  think of this as a tree diagram: first we permute the first deck
  ($n!$ ways) and then, for each first deck arrangement, we permute
  the second deck ($n!$ ways).  By the product rule for sets, we get
  $(n!)^2$ arrangements.

\item[Determine atomic event probabilities.] We assume a uniform
  sample space, so each event has probability $1/(n!)^2$.

\item[Determine the event of interest.] These are the arrangements
  where cards $i_1,\dots,i_k$ are all in the same place in both
  permutations.

\item[Find the event probability.] Since the sample space is uniform, this
is equivalent to determining the \emph{number} atomic events in our event
of interest.  Again we use a tree diagram.  There are $n!$ permutations of
the first deck.  Given the first deck permutation, how many second deck
permutations line up the specified cards?  Well, those $k$ cards must go
in specific locations, while the remaining $n-k$ cards can be permuted
arbitrarily in the remaining $n-k$ locations in $(n-k)!$ ways.  Thus, the
total number of atomic events of this type is $n!(n-k)!$, and the
probability of the event in question is
\[
\frac{n!(n-k)!}{n!n!} = \frac{(n-k)!}{n!}.
\]
\end{description}

We have found that the probability a specific set of $k$ cards matches
is $(n-k)!/n!$.  There are $\binom{n}{k}$ such sets of $k$ cards.  So
the $k^{th}$ Inclusion-Exclusion term is
\[
\binom{n}{k}\frac{(n-k)!}{n!} = 1/k!.
\]
Thus, the probability of at least one match is
\[
1-1/2!+1/3!-\cdots \pm 1/n!
\]
We can understand this expression by thinking about the Taylor
expansion of
\[
e^{-x} = 1-x+x^2/2!-x^3/3!+\cdots.
\]
In particular,
\[
e^{-1} = 1-1+1/2!-1/3!+\cdots.
\]
Our expression takes the first $n$ terms of the Taylor expansion; the
remainder is negligible---it is in fact less than $1 / (n+1)!$---so
our probability is approximately $1-1/e$.

\end{optional}

\section{Conditional Probability}

Suppose that we pick a random person in the world.  Everyone has an
equal chance of being picked.  Let $A$ be the event that the person is
an MIT student, and let $B$ be the event that the person lives in
Cambridge.  The situation is shown in Figure~\ref{fig:cond}.  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?
\begin{figure}
\centerline{\includegraphics[height=2.0in]{figures/cond}}
\caption{What is the probability that a random person in the world
is an MIT student, given that the person is a Cambridge resident?}
\label{fig:cond}
\end{figure}
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 of event $B$ are
irrelevant; these irrelevant outcomes are diagonally shaded in the
figure.  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$
(horizontally shaded) divided by the probability that the person is in
set $B$.  This leads us to

\begin{definition}\label{defcond}
\[
\prcond{A}{B} \eqdef \frac{\pr{A \cap B}}{\pr{B}}
\]
providing $\pr{B} \neq 0$.
\end{definition}

Rearranging terms gives the following
\begin{rul}[Product Rule, base case]
  Let $A$ and $B$ be events, with $\pr{B} \neq 0$.  Then
  \[
  \pr{A \cap B} = \pr{B} \cdot \prcond{A}{B}.
  \]
\end{rul}

Note that we are now using the term ``Product Rule'' for two separate
ideas.  One is the rule above, and the other is the formula for the
cardinality of a product of sets.  In the rest of this lecture, the phrase
always refers to the rule above.  We will see the connection between these
two product rules shortly, when we study independent events.

As an example, what is $\prcond{B}{B}$?  That is, what is the
probability of event $B$, given that event $B$ happens?  Intuitively,
this ought to be 1!  The Product Rule gives exactly this result if
$\pr{B} \neq 0$:
\begin{eqnarray*}
\prcond{B}{B}   & = & \frac{\pr{B \cap B}}{\pr{B}} \\
                & = & \frac{\pr{B}}{\pr{B}} \\
                & = & 1
\end{eqnarray*}

A routine induction proof based on the special case leads to The Product
Rule for $n$ events.
\begin{rul}[Product Rule, general case]
Let $A_1, A_2, \dots, A_n$ be events.
\[
\pr{A_1 \cap A_2 \cap \dots \cap A_n} =
        \pr{A_1} \prcond{A_2}{A_1} \prcond{A_3}{A_1 \cap A_2} \cdots
        \prcond{A_n}{A_1 \cap \dots \cap A_{n-1}}
\]
\end{rul}


\subsection{Conditional Probability Identities}

All our probability identities continue to hold when all probabilities are
conditioned on the same event.  For example,
\begin{equation}\tag{Conditional Inclusion-Exclusion}
\prcond{A \cup B}{C} = \prcond{A}{C} + \prcond{B}{C} - \prcond{A \cap B}{C}
\end{equation}
The identities carry over because for any event $C$, we can define a new
probability measure, $\prsub{}{C}$ on the same sample space by the rule
that
\[
\prsub{A}{C} \eqdef \prcond{A}{C}.
\]
Now the conditional-probability version of an identity is just an instance
of the original identity using the new probability measure.

\begin{problem}
Prove that for any probability space, $\sspace$, and event $C \subseteq
\sspace$, the function $\prsub{}{C}$ is a probability measure on $\sspace$.
\end{problem}

In carrying over identities to conditional versions, a common blunder is
mixing up events before and after the conditioning bar.  For example, the
following is \emph{not} a consequence of the Sum Rule:
\begin{falseclm}\label{fcnd}
\[
\prcond{A}{B \cup C} = \prcond{A}{B} + \prcond{A}{C}
        \quad \quad \quad (B \cap C = \emptyset)
\]
\end{falseclm}
A counterexample is shown in Figure~\ref{fig:cx19}.  In this case,
$\prcond{A}{B} = 1$, $\prcond{A}{C} = 1$, and $\prcond{A}{B \cup C} =
1$.  However, since $1 \neq 1 + 1$, the equation above does not hold.

\begin{figure}
  \centerline{\includegraphics[height=1.5in]{figures/cx19}}
  \caption{This figure illustrates a case where the equation
    $\prcond{A}{B \cup C} = \prcond{A}{B} + \prcond{A}{C}$ does not hold.}
  \label{fig:cx19}
\end{figure}


\subsection{Conditional Probability Examples}

This section contains as series of examples of conditional probability
problems.  Trying to solve conditional problems by intuition can be very
difficult.  On the other hand, we can chew through these problems with our
standard four-step method
\iffalse
\begin{enumerate}
\item Find the sample space.
\item Define events of interest.
\item Compute outcome probabilities.
\item Compute event probabilities.
\end{enumerate}
In all our examples, the solution requires only
\fi
along with the Product Rule.

\subsubsection{A Two-out-of-Three Series}

The MIT EECS department's famed D-league hockey team, The Halting Problem,
is playing a 2-out-of-3 series.  That is, they play games until one team
wins a total of two games.  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 energized 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?

This problem involves two types of conditioning.  First, we are told
that the probability of the team winning a game is $2/3$, \emph{given}
that they won the preceding game.  Second, we are asked the odds of
The Halting Problem winning the series, \emph{given} that they win the
first game.

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

The sample space for the hockey series is worked out with a tree
diagram in Figure~\ref{fig:hockey}.  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$).  The sample space
consists of six outcomes, since there are six leaves in the tree
diagram.
\begin{figure}
\centerline{\includegraphics[height=3.0in]{figures/hockey}}
\caption{What is the probability that The Halting Problem wins the
  2-out-of-3 series, given that they win the first game?}
\label{fig:hockey}
\end{figure}

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

The 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 Figure~\ref{fig:hockey}.
Our problem is then to determine $\prcond{A}{B}$.

\subsubsection*{Step 3:  Compute Outcome Probabilities}

Next, we must assign a probability to each outcome. \iffalse As in the
Monty Hall problem, \fi We begin by assigning probabilities to edges in
the tree diagram.  These probabilities are given explicitly 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 both
assigned probability $1/2$.  Other edges are labeled $1/3$ or $2/3$ based
on the outcome of the preceding game.  We find the probability of an
outcome by multiplying all probabilities along the corresponding
root-to-leaf path.  The results are shown in Figure~\ref{fig:hockey}.

This method of computing outcome probabilities by multiplying edge
probabilities was introduced in our discussion of \insolutions{Monty Hall
and} Carnival Dice, but was not really justified.  In fact, the
justification is actually the Product Rule!  For example, by multiplying
edge weights, we conclude that the probability of outcome $WW$ is
\[
\frac{1}{2} \cdot \frac{2}{3} = \frac{1}{3}.
\]
We can justify this rigorously with the Product Rule as
follows.
\begin{eqnarray*}
\pr{WW} & = & \pr{\mbox{win 1st game} \cap \mbox{win 2nd game}} \\
        & = & \underbrace{\pr{\mbox{win 1st game}} \cdot
                \prcond{\mbox{win 2nd game}}{\mbox{win 1st game}}}_{
\begin{array}{cc}
\mbox{product of edge weights on} \\
\mbox{root-to-leaf path}
\end{array}
} \\
        & = & \frac{1}{2} \cdot \frac{2}{3} \\
        & = & \frac{1}{3}
\end{eqnarray*}
The first equation states that $WW$ is the outcome in which we win the
first game and win the second game.  The second equation is an
application of the Product Rule.  In the third step, we substitute
probabilities from the problem statement, and the fourth step is
simplification.  The heart of this calculation is equivalent to
multiplying edge weights in the tree diagram!

Here is a second example.  By multiplying edge weights in the tree
diagram, we conclude that the probability of outcome $WLL$ is
\[
\frac{1}{2} \cdot \frac{1}{3} \cdot \frac{2}{3} = \frac{1}{9}.
\]
We can formally justify this with the Product Rule as follows:
\begin{eqnarray*}
\pr{WLL} & = & \pr{\mbox{win 1st} \cap
                   \mbox{lose 2nd} \cap
                   \mbox{lose 3rd}} \\
        & = & \underbrace{\pr{\mbox{win 1st}} \cdot
                \prcond{\mbox{lose 2nd}}{\mbox{win 1st}}
                \prcond{\mbox{lose 3nd}}{
                \mbox{win 1st } \cap \mbox{ lose 2nd}}}_{
        \begin{array}{cc}
        \mbox{product of edge weights on} \\
        \mbox{root-to-leaf path}
        \end{array}
        } \\
        & = & \frac{1}{2} \cdot \frac{1}{3} \cdot \frac{2}{3} \\
        & = & \frac{1}{9}
\end{eqnarray*}



\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}} & \text{(Product Rule)} \\
              & = \frac{1/3 + 1/18}{1/3 + 1/18 + 1/9} 
                             &\text{(Sum Rule for $\pr{B}$)}\\
              & = \frac{7}{9}.
\end{align*}

The Halting Problem has a $7/9$ chance of winning the tournament, given
that they win the first game.

\subsubsection{An \emph{a posteriori} Probability}

In the preceding example, we wanted the probability of an event $A$, given
an \emph{earlier} event $B$.  In particular, we wanted the probability
that The Halting Problem won the series, given that they won the first
game.  It can be harder to think about the probability of an event $A$,
given a \emph{later} event $B$.  For example, what is the probability that
The Halting Problem wins its first game, given that the team wins the
series?  This is called an \emph{a posteriori} probability.

An \emph{a posteriori} probability question can be interpreted in two
ways.  By one interpretation, we reason that since we are given the
series outcome, the first game is already either won or lost; we do
not know which.  The issue of who won the first game is a question of
fact, not a question of probability.  Though this interpretation may
have philosophical merit, we will never use it.

We will always prefer a second interpretation.  Namely, we suppose
that the experiment is run over and over and ask in what fraction of
the experiments did event $A$ occur when event $B$ occurred?  For
example, if we run many hockey series, in what fraction of the series
did the Halting Problem win the first game when they won the whole
series?  Under this interpretation, whether $A$ precedes $B$ in time
is irrelevant.  In fact, we will solve \emph{a posteriori} problems
exactly the same way as other conditional probability problems.  The
only trick is to avoid being confused by the wording of the problem!

We can now compute the probability that The Halting Problem wins its
first game, given that the team wins the series.  The sample space is
unchanged; see Figure~\ref{fig:hockey}.  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.  We already computed the
probability of each outcome; all that remains is to compute the
probability of event $\prcond{B}{A}$:
\begin{eqnarray*}
\prcond{B}{A}   & = & \frac{\pr{B \cap A}}{\pr{A}} \\
                & = & \frac{1/3 + 1/18}
                           {1/3 + 1/18 + 1/9} \\
                & = & \frac{7}{9}
\end{eqnarray*}
The probability of The Halting Problem winning the first game, given
that they won the series is $7/9$.

This answer is suspicious!  In the preceding section, we showed that
$\prcond{A}{B} = 7/9$.  Could it be true that $\prcond{A}{B} =
\prcond{B}{A}$ in general?  We can determine the conditions under
which this equality holds by writing $\pr{A \cap B} = \pr{B \cap A}$
in two different ways as follows:
\begin{displaymath}
  \prcond{A}{B} \pr{B} = \pr{A \cap B} =
  \pr{B \cap A} = \prcond{B}{A} \pr{A}.
\end{displaymath}
Evidently, $\prcond{A}{B} = \prcond{B}{A}$ only when $\pr{A} = \pr{B}
\neq 0$.  This is true for the hockey problem, but only by
coincidence.  In general, $\prcond{A}{B}$ and $\prcond{B}{A}$ are
\emph{not} equal!


\subsubsection{A Problem with Two Coins [Optional]}

\begin{optional}

We have two coins.  One coin is fair; that is, comes up heads with
probability $1/2$ and tails with probability $1/2$.  The other is a trick
coin; it has heads on both sides, and so \emph{always} comes up heads.
Now suppose we randomly choose one of the coins, without knowing one we're
picking and with each coin equally likely.  If we flip this coin and get
heads, then what is the probability that we flipped the fair coin?

This is one of those tricky \emph{a posteriori} problems, since we want
the probability of an event (the fair coin was chosen) given the outcome
of a later event (heads came up).  Intuition may fail us, but the standard
four-step method works perfectly well.

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

The sample space is worked out with the tree diagram in
Figure~\ref{fig:coins}.
\begin{figure}
  \centerline{\includegraphics[height=2.5in]{figures/coins}}
  \caption{What is the probability that we flipped the fair coin,
    given that the result was heads?}
  \label{fig:coins}
\end{figure}


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

Let $A$ be the event that the fair coin was chosen.  Let $B$ the event
that the result of the flip was heads.  The outcomes in each event are
marked in the figure.  We want to compute $\prcond{A}{B}$, the
probability that the fair coin was chosen, given that the result of
the flip was heads.


\subsubsection*{Step 3: Compute Outcome Probabilities}

First, we assign probabilities to edges in the tree diagram.  Each coin
is chosen with probability $1/2$.  If we choose the fair coin,
then head and tails each come up with probability $1/2$.  If
we choose the trick coin, then heads comes up with probability 1.  By
the Product Rule, the probability of an outcome is the product of the
probabilities on the corresponding root-to-leaf path.  All of these
probabilities are shown in Figure~\ref{fig:coins}.

\subsubsection*{Step 4: Compute Event Probabilities}

\begin{align*}
\prcond{A}{B} & = \frac{\pr{A \cap B}}{\pr{B}} & \text{(Product Rule)}\\
              & = \frac{1/4}{1/4 + 1/2} & \text{(Sum Rule for $\pr{B}$)} \\
              & = \frac{1}{3}
\end{align*}
So the probability that the fair coin was chosen, given that the result of
the flip was heads, is $1/3$.

\end{optional}

\subsubsection{A Variant of the Two Coins Problem [Optional]}
\begin{optional}
Here is a variant of the two coins problem.  Someone hands us either the
fair coin or the trick coin, but we do not know which.  We flip the coin
100 times and see heads every time.  What can we say about the probability
that we flipped the fair coin?  Remarkably, nothing!  That's because we
have no idea with what probability, if any, the fair coin was chosen.

In fact, maybe we were intentionally handed the fair coin.  If we try to
capture this fact with a probability model, we would have to say that the
probability that we have the fair coin is one.  Then the conditional
probability that we have the fair coin given that we flipped 100 heads
remains one, because we do have it.

A similar problem arises in polls around election time.  A pollster picks
a random American and ask his or her party affiliation.  Suppose he
repeats this experiment several hundred times and 60\% of respondents say
that they are Democrats.  What can be said about the probability that a
majority of Americans are Democrats?  Nothing!

To make the analogy clear, suppose the country contains only two
people.  There is either one Democrat and one Republican (like the
fair coin), or there are two Democrats (like the trick coin).  The
pollster picks a random citizen 100 times; this is analogous to
flipping the coin 100 times.  Even if he always picks a Democrat
(flips heads), he can not determine the probability that the country
is all Democrat!

Of course, if we have the fair coin, it is very unlikely that we would
flip 100 heads.  So in practice, if we got 100 heads, we would bet
\emph{with confidence} that we did not have the fair coin.  This
distinction between the probability of an event---which may be
undefined---and the confidence we may have in its occurrence is central to
statistical reasoning about real data.  We'll return to this important
issue in the coming weeks.
\end{optional}

\iffalse

Suppose we were given the fair coin with probability $p$.  In terms of
$p$, we can find the probability that we flipped the fair coin, given
that it comes up heads 100 times.
\begin{figure}
\centerline{\includegraphics[height=3.0in]{figures/coins2}}
\caption{We flip the coin 100 times and see heads every time.
What can we say about the probability that we flipped the fair coin?}
\label{fig:coins2}
\end{figure}
The sample space is worked out in Figure~\ref{fig:coins2}.  Let $A$ be
the event that we were handed the fair coin, and let $B$ be the event
that we flipped 100 heads.  We want to compute $\prcond{A}{B}$, the
probability that we were handed the fair coin, given that we flipped
100 heads.  The outcome probabilities are computed as shown in the
figure.  We can compute the probability of $\prcond{A}{B}$ as follows.
\begin{eqnarray*}
\prcond{A}{B}   & = & \frac{\pr{A \cap B}}{\pr{B}} \\
                & = & \frac{p 2^{-100}}{1 - p + p 2^{-100}} \\
                & = & \frac{p}{2^{100} (1 - p) + p}
\end{eqnarray*}
Because of the $2^{100}$ term in the denominator, this expression is
very small for reasonable values of $p$.  For example, if $p$ is
$1/2$, then we almost certainly have the trick coin.

The problem is that we do not know the probability $p$ with which we
were given the fair coin; someone just handed us one or the other!
For example, maybe $p = 1 - 2^{-100}$.  Then there is only about a
$1/2$ chance that we have the fair coin!

\fi


\subsubsection{Medical Testing}

There is a degenerative disease called $\disease$ that 10\% of men in a
certain population may suffer in old age.  However, if treatments are
started before symptoms appear, the degenerative effects can largely be
controlled.

Fortunately, there is a test that can detect latent $\disease$ before any
degenerative symptoms appear.  The test is not perfect, however:
\begin{itemize}

\item If a man has latent $\disease$, there is a 10\% chance that the
test will say he does not.  (These are called ``false negatives''.)

\item If a man does not have latent $\disease$, there is a 30\% chance
that the test will say he does.  (These are ``false positives''.)
\end{itemize}
A random man is tested for latent $\disease$.  If the test is positive,
then what is the probability that the man has latent $\disease$?

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

The sample space is found with a tree diagram in Figure~\ref{fig:x}.
\begin{figure}
  \centerline{\includegraphics[height=3.0in]{figures/x}}
  \caption{What is the probability that a man has $\disease$,
    given that the test is positive?}
  \label{fig:x}
\end{figure}

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

Let $A$ be the event that the man has $\disease$.  Let $B$ be the
event that the test was positive.  The outcomes in each event are
marked in Figure~\ref{fig:x}.  We want to find $\prcond{A}{B}$, the
probability that a man has $\disease$, given that the test was
positive.


\subsubsection*{Step 3: Find Outcome Probabilities}

First, we assign probabilities to edges.  These probabilities are drawn
directly from the problem statement.  By the Product Rule, the
probability of an outcome is the product of the probabilities on the
corresponding root-to-leaf path.  All probabilities are shown in the
figure.


\subsubsection*{Step 4: Compute Event Probabilities}

\begin{eqnarray*}
\prcond{A}{B}   & = & \frac{\pr{A \cap B}}{\pr{B}} \\
                & = & \frac{0.09}{0.09 + 0.27} \\
                & = & \frac{1}{4}
\end{eqnarray*}
If a man tests positive, then there is only a 25\% chance that he has
$\disease$!

This answer is initially surprising, but makes sense on reflection.  There
are two ways a man could test positive.  First, he could be sick and the
test correct.  Second, could be healthy and the test incorrect.  The
problem is that most men (90\%) are healthy; therefore, most of the
positive results arise from incorrect tests of healthy people!

We can also compute the probability that the test is correct for a random
man.  This event consists of two outcomes.  The man could be sick and the
test positive (probability $0.09$), or the man could be healthy and the
test negative (probability $0.63$).  Therefore, the test is correct with
probability $0.09 + 0.63 = 0.72$.  This is a relief; the test is correct
almost $75\%$ of the time.

But wait!  There is a simple way to make the test correct \emph{90\%} of
the time: always return a negative result!  This ``test'' gives the right
answer for all healthy people and the wrong answer only for the 10\% that
actually have the disease.  The best strategy is to completely ignore the
test result!\footnote{In real medical tests, one usually
  looks at some underlying measurement (e.g., temperature) and uses it
  to decide whether someone has the disease or not.  ``Unusual''
  measurements lead to a conclusion that the disease is present.  But
  just how unusual a measurement should lead to such a conclusion?  If
  we are conservative, and declare the disease present when things are
  even slightly unusual, we will have a lot of false positives.  If we
  are relaxed, and declare the disease present only when the
  measurement is very unusual, then we will have a lot of false
  negatives.  So by shifting the decision threshold, one can trade off
  on false positives versus false negatives.  It appears that the
  tester in our example above did not choose the right threshold for
  their test---they can probably get higher overall accuracy by
  allowing a few more false negatives to get fewer false positives.}

There is a similar paradox in weather forecasting.  During winter,
almost all days in Boston are wet and overcast.  Predicting miserable
weather every day may be more accurate than really trying to get it
right!  This phenomenon is the source of many paradoxes; we will see
more in coming weeks.

\subsection{Confusion about Monty Hall}

Using conditional probability we can examine the main argument that
confuses people about the Monty Hall example of Section~\ref{monty}.

\instatements{We'll do this after we do a \emph{Let's Make a Deal}
demonstration in class on Monday, November 4.}

\insolutions{
Let the doors be numbered $1,2,3$, and suppose the contestant chooses door
1 and then Carol opens door 2.  Now the contestant has to decide whether
to stick with door 1 or switch to door 3.  To do this, he considers the
probability that the prize is behind the remaining unopened door 3, given
that he has learned that it is not behind door 2.

To calculate this conditional probability, let $W$ be the event that the
contestant chooses door 1, and let $R_i$ be the event that the prize is
behind door $i$, for $i=1,2,3$.  The contestant knows that $\pr{W} = 1/3 =
\pr{R_i}$, and since his choice has no efffect on the location of the
prize, he can say that
\[
\pr{R_i \intersect W} = \pr{R_i} \cdot \pr{W} =
\frac{1}{3}\cdot\frac{1}{3} = \frac{1}{9}
\]
and likewise,
\[
\pr{\overline{R_i} \intersect W} = (2/3)(1/3) = 2/9,
\]
for $i=1,2,3$.

Now the probability that the prize is behind the remaining unopened door
3, given that the contestant has learned that it is not behind door 2 is
$\prcond{R_3 \intersect W}{\overline{R_2} \intersect W}$.  But
\[
\prcond{R_3 \intersect W}{\overline{R_2} \intersect W} \eqdef
\frac{\pr{R_3 \intersect \overline{R_2} \intersect W}}{\pr{\overline{R_2}
\intersect W}} = \frac{\pr{R_3} \intersect W}{\pr{\overline{R_2}
\intersect W}} = \frac{1/9}{2/9} = \frac{1}{2}.
\]
Likewise, $\prcond{R_1 \intersect W}{\overline{R_2} \intersect W} = 1/2$.
So the contestant concludes that the prize is equally likely to be behind
door 1 as behind door 3, and therefore there is no advantage to the switch
strategy over the stick strategy.  But this contradicts our earlier
analysis!

Whew, that is confusing!  Where did the contestant's reasoning go wrong?
(Maybe, like some Ph.D. mathematicians, you are convinced by the
contestant's reasoning and now think we must have made a mistake in our
earlier conclusion that switching is twice as likely to win than
sticking.)  Let's try to sort this out.

\iffalse
\item The probability that the prize is behind door 1 is $1/3$, regardless
of what door the contestant picks.  Then Carol opens door 2, and the
conditional probability that the prize is behind door 1 increases to
$1/2$.  But we always knew that the prize was not going to be behind the
door that Carol opens.  So how could the occurrence of an event that was
certain to happen increase the probability that the prize is behind door
1?
\end{enumerate}
\fi


There is a fallacy in the contestant's reasoning---a subtle one.  In fact,
his calculation that, given that the prize is not behind door 2, that it's
equally likely to be behind door 1 as door 3 is \emph{correct}.  His
mistake is in not realizing that he knows \emph{more} than that the prize
is not behind door 2.  He has confused two similar, but distinct, events,
namely,
\begin{enumerate}

\item the contestant chooses door 1 and the prize is not behind door 2,
and\label{notdoor2},

\item the contestant chooses door 1 and then Carol opens door
2.\label{carol2}.

\end{enumerate}
These are different events and indeed they have different probabilities.
The fact that Carol opens door 2 tells the contestant \emph{more} than
that the prize is not behind door 2.

We can precisely demonstrate this with our sample space of triples
$(i,j,k)$, where the prize is behind door $i$, the contestant picks door
$j$, and Carol opens door $k$.  In particular, let $C_i$ be the event that
Carol opens door $i$.  Then, event~\ref{notdoor2}.\ is $\overline{R_2}
\intersect W$, and event~\ref{carol2}.\ is $W \intersect C_2$.

We can confirm the correctness of the contestant's calculation that the
prize is behind door 1 given event~\ref{notdoor2}:
\begin{eqnarray*}
\overline{R_2} \intersect W &\eqdef& \set{(1,1,2),(3,1,2),(1,1,3)}\\
\pr{\overline{R_2} \intersect W} & = & = \frac{1}{18} +
\frac{1}{9} + \frac{1}{18} = \frac{2}{9}\\
\prcond{R_1}{\overline{R_2} \intersect W} & = &
\frac{\pr{\set{(1,1,2),(1,1,3)}}}{2/9}
   = \frac{1}{2}.
\end{eqnarray*}
But although the contestant's calculation is correct, his blunder is that
he calculated the wrong thing.  Specifically, he conditioned his
conclusion on the wrong event.  The contestant's situation when he must
decide to stick or switch is that event~\ref{carol2}.\ has occurred.  So he
should have calculated:
\begin{eqnarray*}
W \intersect C_2 & \eqdef & \set{(1,1,2),(3,1,2)}\\
\pr{W \intersect C_2} & = & \frac{1}{18} + \frac{1}{9} = \frac{1}{6}\\
\prcond{R_1}{W \intersect C_2} & = & \frac{\pr{(1,1,2)}}{1/6} =
\frac{1}{3}.
\end{eqnarray*}
In other words, the probability that the prize is behind his chosen door 1
is 1/3, so he should switch because the probability is 2/3 that the prize
is behind the other door 3, exactly as we correctly concluded in
Section~\ref{monty}.

Once again, we see that mistaken intuition gets resolved by falling back
on an examination of outcomes in the probability space.
}

\section{Case Analysis}

Combining the sum and product rules provides a natural way to
determine the probabilities of complex events via case analysis.  As a
motivating example, we consider a rather paradoxical true story.

\subsection{Discrimination Lawsuit}

Several years ago there was a sex discrimination lawsuit against Berkeley.
A female professor was denied tenure, allegedly because she was a woman.
She argued that in every one of Berkeley's 22 departments, the percentage
of male applicants accepted was greater than the percentage of female
applicants accepted.  This sounds very suspicious, if not paradoxical!

However, Berkeley's lawyers argued that across the whole university
the percentage of male applicants accepted was actually \emph{lower}
than the percentage of female applicants accepted!  This suggests that
if there was any sex discrimination, then it was against men!  Must
one party in the dispute be lying? 

\subsubsection{A false analysis}

Here is a fallacious analysis of the discrimination lawsuit.

To clarify the arguments, let's and express them in terms of conditional
probabilities.  Suppose that there are only two departments, EE and CS,
and consider the experiment where we ignore gender and pick an applicant
at random.  Define the following events:
\begin{itemize}
\item Let $A$ be the event that the applicant is accepted.
\item Let $F_{EE}$ the event that the applicant is a female applying to EE.
\item Let $F_{CS}$ the event that the applicant is a female applying to CS.
\item Let $M_{EE}$ the event that the applicant is a male applying to EE.
\item Let $M_{CS}$ the event that the applicant is a male applying to
CS.
\end{itemize}
Assume that all applicants are either male or female, and that no
applicant applied to both departments.  That is, the events $F_{EE}$,
$F_{CS}$, $M_{EE}$, and $M_{CS}$ are all disjoint.

The female plaintiff makes the following argument:
\begin{align}
  \prcond{A}{F_{EE}} & < \prcond{A}{M_{EE}} \label{AFEE}\\
  \prcond{A}{F_{CS}} & < \prcond{A}{M_{CS}}\label{AFCS}
\end{align}
That is, in both departments, the probability that a woman is accepted
is less than the probability that a man is accepted.  The university
retorts that overall a woman applicant is \emph{more} likely to be
accepted than a man:
\begin{equation}\label{univ}
  \prcond{A}{F_{EE} \cup F_{CS}} > \prcond{A}{M_{EE} \cup M_{CS}}
\end{equation}
It is easy to believe that these two positions are contradictory.

\begin{optional}
In fact, we might even try to prove this as follows:
\begin{align}\label{F+F}
\prcond{A}{F_{EE}} + \prcond{A}{F_{CS}} & < \prcond{A}{M_{EE}} + \prcond{A}{M_{CS}} 
         & \text{(by~(\ref{AFEE}) \&~(\ref{AFCS}))}.
\end{align}
Therefore
\begin{equation}\label{neguniv}
  \prcond{A}{F_{EE} \cup F_{CS}}  <  \prcond{A}{M_{EE} \cup M_{CS}},
\end{equation}
which exactly contradicts the university's position!

However, there is a problem with this argument; equation~(\ref{neguniv})
follows~(\ref{F+F}) only if we accept False Claim~\ref{fcnd} above!
Therefore, this argument is invalid.
\end{optional}

In fact, the table below shows a set of application statistics for which
the assertions of both the plaintiff and the university hold:
\[
\begin{array}{clr}
  \mbox{CS} & \mbox{0 females accepted, 1 applied} & 0\% \\
  & \mbox{50 males accepted, 100 applied} & 50\% \\
  \mbox{EE} & \mbox{70 females accepted, 100 applied} & 70\% \\
  & \mbox{1 male accepted, 1 applied} & 100\% \\
  \hline
  \mbox{Overall} & \mbox{70 females accepted, 101 applied} & \approx 70\% \\
  & \mbox{51 males accepted, 101 applied} & \approx 51\%
\end{array}
\]
In this case, a higher percentage of males were accepted in both
departments, but overall a higher percentage of females were accepted!
Bizarre!

Let's think about the reason that this example is counterintuitive.  Our
intuition tells us that we should be able to analyze an applicant's
overall chance of acceptance through case analysis.  A female's overall
chance of acceptance should be some sort of average of her chance of
acceptance within each department, and similarly for males.  Since the
female's chance in each department is smaller, her overall average chance
ought to be smaller as well.  What is going on?

A correct analysis of the Discrimination Lawsuit problem rests on a proper
rule for doing case analysis.  This rule is called the \emph{Law of Total
Probability}.

\subsection{The Law of Total Probability}

\begin{theorem}[Total Probability]\label{TotP}
If a sample space is the disjoint union of events $B_0, B_1, \dots$, then
for all events $A$,
\[
\pr{A} = \sum_{i \in \naturals} \pr{A \cap B_i}.
\]
\end{theorem}

Theorem~\ref{TotP} follows immediately from the Sum Rule, because $A$ is
the disjoint union of $A \intersect B_0$, $A \intersect B_1$, \dots.

A more traditional form of this theorem uses conditional probability.
\begin{corollary}[Total Probability]
If a sample space is the disjoint union of events $B_0, B_1, \dots$, then
for all events $A$,
\[
\pr{A} = \sum_{i \in \naturals} \prcond{A}{B_i} \pr{B_i}.
\]
\end{corollary}

\begin{example}
  The probability a student comes to class is $1/2$ in rainy weather,
  but $1/10$ in sunny weather.  If the probability that it rains is
  $1/5$, what is the probability the student comes to class?
\end{example}

We can answer this question using the law of Total Probability.  If we
let $C$ be the event that the student comes to class, and $R$ the
event that it rains, then we have
\begin{eqnarray*}
\pr{C} &= &\prcond{C}{R} \pr{R} + \prcond{C}{{\overline R}}
\pr{{\overline R}}\\
&= &(1/2)\cdot (1/5) +(1/10)\cdot(4/5)\\
&= &6/50
\end{eqnarray*}

\iffalse
\insolutions{
The theorem of total probability also connects to our rule for
evaluating probabilities using tree diagrams.  Recall for example the
Monty Hall Problem.  We analyzed this problem with a tree diagram,
where the first branching of the tree was on which box contained the
car.  Suppose we define  $B_i$ to be the event that the prize is in box
$i$.  We declared in the example that $\pr{B_i}=1/3$ for $i=1,2,3$.
Let us also define $W$ to be the event that our strategy wins the
game.  Then the law of total probability tells us that
\begin{eqnarray*}
\pr{W} &=& \sum_i \prcond{W}{B_i} \pr{B_i}\\
&=& \sum_i (1/3) \prcond{W}{B_i}.
\end{eqnarray*}
Looking back at the tree diagram, this means that we should compute
the probability of winning along each branch of the tree, multiply
each such probability by 1/3 (the probability value along each branch)
and add the results.  This is exactly what we did in the tree diagram
example.
}
\fi

\subsection{Resolving the Discrimination Lawsuit Paradox}

With the law of total probability in hand, we can perform a proper case
analysis for our discrimination lawsuit.

Let $F_A$ be the event that a female applicant is accepted.

Assume that no applicant applied to both departments.  That is, the
events, $F_{EE}$, that the female applicant is applying to EE, and
$F_{CS}$, that she is applying to CS, are disjoint (and in fact
complementary).

Since $F_{EE}$ and $F_{CS}$ partition the sample space, we can apply
the law of total probability to analyze acceptance probability:
\begin{eqnarray*}
\pr{F_A} &= & \prcond{F_A}{F_{EE}}\pr{F_{EE}}+\prcond{F_A}{
F_{CS}}\pr{F_{CS}}\\
&= &(70/100)\cdot(100/101) + (0/1)\cdot(1/101) = 70/101,
\end{eqnarray*}
which is the correct answer.  Notice that as we intuited, $\pr{F_A}$
is a \emph{weighted average} of the conditional probabilities of
$F_A$, where the weights (of 100/101 and 1/101 respectively) are
simply the probabilities of being in each condition.

In the same fashion, we can define the events $M_A$ and evaluate a male's
overall acceptance probability:
\begin{eqnarray*}
\pr{M_A} &= & \prcond{M_A}{M_{EE}}\pr{M_{EE}}+\prcond{M_A}{
M_{CS}}\pr{M_{CS}}\\
&= &(1/1)\cdot(1/101) + (50/100)\cdot(100/101) =  51/101,
\end{eqnarray*}
which is the correct answer.  As before, the overall acceptance
probability is a weighted average of the conditional acceptance
probabilities.

But here we have the source of our paradox: the weights of the
weighted averages for males and females are \emph{different}.  For the
females, the bulk of the weight (common department) falls on the
condition (department) in which females do very well (EE); thus the
weighted average for females is quite good.  For the males, the bulk
of the weight falls on the condition in which males do poorly (CS);
thus the weighted average for males is poor.

Which brings us back to the allegation in the lawsuit.  Having precisely
analyzed the arguments of the plaintiff and the defendent, you are in a
position to judge how persuasive they are.  If you were on the jury, would
you find Berkeley guilty of gender bias in its admissions?

\subsection{On-Time Airlines}
\begin{optional}

Here is a second example of the same paradox.  Newspapers publish
on-time statistics for airlines to help travelers choose the best
carrier.  The on-time rate for an airline is defined as follows:
\[
\mbox{Airline on-time rate} = \frac{\mbox{\#flights less than 15 minutes late}}
                                   {\mbox{\#flights total}}
\]
This seems reasonable, but actually can be completely misleading!
Here is some on-time data for two airlines in the late 80's.
\[
\begin{array}{lccc|ccc}
        & \mbox{Alaska Air} & & & \mbox{America West} \\
\mbox{Airport} & \mbox{\#on-time} & \mbox{\#flights} & \% & \mbox{\#on-time} & \mbox{\#flights} & \% \\
\hline
\mbox{Los Angeles}      & 500 & 560 & 89 & 700 & 800 & 87 \\
\mbox{Phoenix}          & 220 & 230 & 95 &4900 &5300 & 92 \\
\mbox{San Diego}        & 210 & 230 & 92 & 400 & 450 & 89 \\
\mbox{San Francisco}    & 500 & 600 & 83 & 320 & 450 & 71 \\
\mbox{Seattle}          &1900 &2200 & 86 & 200 & 260 & 77 \\
\hline
\mbox{OVERALL}          &3330 &3020 & 87 &6520 &7260 & 90
\end{array}
\]
This is the same paradox as in the Berkeley lawsuit; America West has
a better overall on-time percentage, but Alaska Airlines does a better
job at every single airport!  The problem is that Alaska Airlines
flies proportionally more of its flights to bad weather airports like
Seattle; whereas America West is based in fair-weather, low-traffic
Phoenix!

\end{optional}

\iffalse

\section{A Coin Tossing Game}

Here is a fun new game.  I repeatedly flip a fair coin.  If the
sequence $HTT$ comes up on three consecutive throws, then the game is
over and you win.  However, if the sequence $HHT$ comes up on three
consecutive throws, then the game is over and I win.  Find the
probability that you win the game; that is, find the probability that
the sequence $HTT$ appears before the sequence $HHT$ in a sequence of
fair coin tosses.

Our theory of probability actually breaks down a bit on this example,
since the sample space, consisting of all sequences of coin flips, is
infinite!  However, the technical problems this introduces can be
solved with appropriate definitions.  For the purpose of this example
we will ignore them.

Let $p$ be the probability that $HTT$ appears before $HHT$.  For the
first two flips, the sequences $HH$, $HT$, $TH$, and $TT$ are equally
likely.  Let $p_{xy}$ be the probability that the sequence $HTT$
appears before the sequence $HHT$, given that the two most recent
flips were $x$ and $y$.  Using the law of total probability, we have:
\begin{eqnarray*}
p       & = &   \frac{1}{4}(p_{HH} + p_{HT} + p_{TH} + p_{TT})
\end{eqnarray*}
We can interrelate the four variable on the right side of this
equation by considering the outcome of the next flip.  For example,
suppose the last two flips were $HT$.  With probability $1/2$,
the next flip is a $T$.  Conditioned on this sequence of flips, $HTT$
appears before $HHT$ with probability 1.  On the other hand, with
probability $1/2$, the next flip is $H$.  In this case, $HTT$
appears before $HHT$ with probability $p_{TH}$, since the last two
flips were $TH$.  This reasoning gives the equation
\[
p_{HT} = \frac{1}{2} + \frac{1}{2} p_{TH}.
\]
By similar arguments, and applying the law of total probability, we obtain
the following system of linear equations.
\begin{eqnarray*}
p_{HH}  & = &   \frac{1}{2} \cdot 0 + \frac{1}{2} \cdot p_{HH} \\
p_{HT}  & = &   \frac{1}{2} \cdot 1 + \frac{1}{2} \cdot p_{TH} \\
p_{TH}  & = &   \frac{1}{2} \cdot p_{HT} + \frac{1}{2} \cdot p_{HH} \\
p_{TT}  & = &   \frac{1}{2} \cdot p_{TT} + \frac{1}{2} \cdot p_{TH}
\end{eqnarray*}
The solution to this system is $p_{HH} = 0$, $p_{TH} = 2/3$,
$p_{TH} = 1/3$, and $p_{TT} = 2/3$.  Substituting
these four values into the first equation gives $p = 1/3$ for
your chance of winning the game.

There are at least two alternative approaches to this analysis.
First, one could find the set of all winning outcomes for one player
and sum the probabilites of these outcomes.  Second, one could find
the sets of winning outcomes for both players and show that one has
twice the probability of the other.

In general, if you pick a pattern, I will pick a pattern that whose last
two letters correspond to the first two of your pattern, and prefix it
with an $H$ or a $T$ such that my pattern is {\it not} a palindrome.  So
if you pick $HTH$, I will pick $HHT$, if you pick $HHT$, I will pick
$THH$.  Amazingly this gives me at least a $2/3$ probability of
winning!
\fi

\iffalse

\subsection{Extension to Conditional Probability}

All of the basic facts extend to conditional probability:
\begin{theorem}
Suppose $A$, $B$, and $C$ are events in the same probability space,
and $\pr{C} \neq 0$.
\begin{enumerate}
\item
If $A \subseteq B$ then $\prcond{A}{C} \leq \prcond{B}{C}$.
\item
$\prcond{\bar{A}}{C} = 1 - \prcond{A}{C}$.
\item
$\prcond{A \cup B}{C} = \prcond{A}{C} + \prcond{B}{C} - \prcond{A \cap B}{C}$.
\item 
$\prcond{A \cup B}{C} \leq \prcond{A}{C} + \prcond{B}{C}$.
\item
$\prcond{A \cap B}{C} = \prcond{A}{C} - \prcond{A - B}{C}$.
\item
$\prcond{A \cap B}{C} \leq \prcond{A}{C}$.
\end{enumerate}
\end{theorem}
These facts follow from the definition of conditional probability and
the previous set of facts.
For instance, to show the first part:
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXX\= \kill
Prove: If $A \subseteq B$ then $\prcond{A}{C} \leq \prcond{B}{C}$. \\
1. Assume $A \subseteq B$. \\
2. $A \cap C \subseteq B \cap C$. 
\> \> \> \> \> Set theory. \\
3. $\pr{A \cap C} \leq \pr{B \cap C}$.
\> \> \> \> \> By the previous theorem. \\
4. $\prcond{A}{C} = \frac{\pr{A \cap C}}{\pr{C}}$, 
   $\prcond{B}{C} = \frac{\pr{B \cap C}}{\pr{C}}$. \\
\> \> \> \> \> Definition. \\
5. $\prcond{A}{C} \leq \prcond{B}{C}$.
\> \> \> \> \> Algebra. \\
6. QED
\> \> \> \> \> Implication
\end{tabbing}

\fi

\section{A Dice Game with an Infinite Sample Space}\label{until1}

Suppose two players take turns rolling a fair six-sided die, and whoever
first rolls a 1 first is the winner.  It's pretty clear that the first
player has an advantage since he has the first chance to win.  How much of
an advantage?

The game is simple and so is its analysis.  The only part of the story
that turns out to require some attention is the formulation of the
probability space.

\subsection{Probability that the First Player Wins}

Let $W$ be the event that the first player wins.  We want to find the
probability $\pr{W}$.  Now the first player can win in two separate ways:
he can win on the first roll or he can win on a later roll.  Let $F$ be
the event that the first player wins on the first roll.  We assume the die
is fair; that means $\pr{F} = 1/6$.

So suppose the first player does not win on the first roll, that is, event
$\bar{F}$ occurs.  But now on the second move, the roles of the first and
second player are simply the reverse of what they were on the first move.
So the probability that the first player now wins is the same as the
probability at the start of the game that the second player would win,
namely $1-\pr{W}$.  In other words,
\begin{equation}
\prcond{W}{\bar{F}} = 1 - \pr{W}.
\end{equation}
So
\[
\pr{W} = \pr{F} + \prcond{W}{\bar{F}}\pr{\bar{F}} = \frac{1}{6} +
(1-\pr{W})\frac{5}{6}.
\]
Solving for $\pr{W}$ yields
\[
\pr{W} = \frac{6}{11} \approx 0.545.
\]
We have figured out that the first player has about a 4.5\% advantage.

\subsection{The Possibility of a Tie}

Our calculation that $\pr{W} = 6/11$ is correct, but it rests on an
important, hidden assumption.  We assumed that the second player
\emph{does} win if the first player does \emph{not} win.  In other words,
there will always be a winner.  This seems obvious until we realize that
there may be a game in which \emph{neither player wins}---the players
might roll forever without rolling a 1.  Our assumption is wrong!

But a more careful look at the reasoning above reveals that we didn't
actually assume that there always is a winner.  All we need to justify is
the assumption that the \emph{probability} that the second player wins
equals one minus the probability that the first player wins.  This is
equivalent to assuming, not that there will always be a winner, but only
that \emph{the probability is 1} that there is a winner.

How can we justify this?  Well, the probability of a winner exactly on the
$n$th roll is the probability, $(5/6)^{n-1}$, that there is no winner on
the first $n-1$ rolls, times the probability, $1/6$, that then there is a
winner on the $n$th roll.  So the probability that there is a winner is
\begin{eqnarray*}
\sum_{n =1}^\infty \left(\frac{5}{6}\right)^{n-1}\frac{1}{6}
   & = & \frac{1}{6}\sum_{n =1}^\infty \left(\frac{5}{6}\right)^{n-1}\\
   & = & \frac{1}{6}\sum_{n =0}^\infty \left(\frac{5}{6}\right)^{n}\\
   & = & \frac{1}{6}\cdot \frac{1}{1-5/6} = 1,
\end{eqnarray*}
as required.

\subsection{The Sample Space}

Again, the calculation in the previous subsection was correct: the
probability that \emph{some} player wins is indeed 1.  But we ought to
feel a little uneasy about calculating an infinite sum of probabilities
without ever having described the probability space.  Notice that in all
our previous examples this wasn't much of an issue, because all the sample
spaces were finite.  But in the dice game, there are an infinite number of
outcomes because the game can continue for any finite number of rolls.

Following our recipe for modelling experiments, we should first decide on
the sample space, namely, what is an outcome of our dice game?  Since a
game involves a series of dice rolls until a 1 appears, it's natural to
include as outcomes the sequences of rolls which determine a winner.
Namely, we include as sample points all sequences of integers between 1
and 6 that end with a first occurrence of 1.

For example, the sequences $(1)$, $(5,4,1)$, $(6, 6, 6, 6, 1)$ are sample
points describing wins by the first player---after 1, 3 and 5 rolls,
respectively.  Similarly, $(2, 1)$ and $(5,4,3,1)$ are outcomes describing
wins by the second player.  On the other hand, $(3,2,3)$ is not a sample
point because no 1 occurs, and $(3,1,2,1)$ is not a sample point because
it continues after the first 1.

Now since we assume the die is fair, each number is equally likely to
appear, so it's natural to \emph{define} the probability of any winning
sample point of length $n$ to be $(1/6)^n$.

The outcomes in the event that there is a winner on the $n$th roll are the
$5^{n-1}$ length-$n$ sequences whose first 1 occurs in the $n$th position.
Therefore this event has the probability
\[
5^{n-1}\left(\frac{1}{6}\right)^n = \left(\frac{5}{6}\right)^{n-1}\frac{1}{6}.
\]
This is the probability that we used in the previous subsection to
calculate that the probability is 1 that there is a winner.

Besides winning sequences, which are necessarily of finite length, we
should consider including sample points corresponding to games with no
winner.  Now since the winning probabilities already total to one, any
sample points we choose to reflect no-winner situations must be assigned
probability zero, and moreover the event consisting of all the no-winner
points that we include must have probability zero.

A natural choice for the no-winner outcomes would be all the
\emph{infinite} sequences of integers between 2 and 6, namely, those with
no occurrence of a 1.  This leads to a legitimate sample space.  But for
the analysis we just did of the dice game, \emph{it makes absolutely no
difference what no-win outcomes we include}.  In fact, it doesn't matter
whether we include any no-win points at all.

It does seem a little strange to model the game in a way that denies the
logical possibility of an infinite sequence of rolls.  On the other hand,
we have no need to model the details of the infinite sequences of rolls
when there is no winner.  So let's define our sample space to include a
\emph{single} additional outcome which does represent the possibility of
the game continuing forever with no winner; the probability of this ``no
winner'' point is defined to be 0.  So this choice of sample space
acknowledges the logical possibility of an infinite
game.\footnote{Representing the no-winner event by a single outcome has
the technical advantage that every set of outcomes is an event---which
would not be the case if we explicitly included all the infinite sequences
without occurrences of a 1 (\cf footnote~\ref{foot-nolength}).}

\iffalse it is countable (\cf Theorem~\ref{bits}.\ref{nat*}), which means
we don't have to think about specifying which subsets of the sample space
can be events, because with a countable sample space, we can (and must)
let all the subsets be events.  \fi

\iffalse FIX THIS

\textbf{Optional Exercise}: Now that we have defined the probability space
for the dice game, we can verify the informal argument above that if the
first roll is not a 1, then ``the second player is in exactly the same
situation as the first player.''  Let $A$ be the event that the first roll
is not a 1.  The rigorous statement is that there is a bijection $f:S \to A$
such that $s$ and $f(s)$ have opposite winners and $\pr{f(s)} = (5/6)\pr{s}$.
Describe such a bijection.
\fi

\section{Independence}

\subsection{The Definition}

\begin{definition}\label{indep1}
Suppose $A$ and $B$ are events, and $B$ has positive probability.  Then
$A$ is \emph{independent} of $B$ iff
\begin{displaymath}
  \prcond{A}{B} = \pr{A}.
\end{displaymath}
\end{definition}
In other words, that fact that event $B$ occurs does not affect the
probability that event $A$ occurs.

Figure~\ref{fig:independent} shows an arrangement of events such that
$A$ is independent of $B$.  Assume that the probability of an event is
proportional to its area in the diagram.  In this example, event $A$
occupies the same fraction of event $B$ as of event $\sspace$, namely
$1/2$.  Therefore, the probability of event $A$ is
$1/2$ and the probability of event $A$, given event $B$, is
also $1/2$.  This implies that $A$ is independent of $B$.

%%CRUMMY FIGURE; REPLACE WITH BETTER ONE:

\begin{figure}[htbp]
  \centerline{\includegraphics[height=1.5in]{figures/independent}}
  \caption{In this diagram, event $A$ is independent of event $B$.}
  \label{fig:independent}
\end{figure}

\subsection{An Example with Coins}

Suppose we flip two fair coins.  Let $A$ be the event that the first
coin is heads, and let $B$ be the event that the second coin is heads.
Since the coins are fair, we have $\pr{A} = \pr{B} = 1/2$.  In
fact, the probability that the first coin is heads is still
$1/2$, even if we are given that the second coin is heads; the
outcome of one toss does not affect the outcome of the other.  In
symbols, $\pr{A \mid B} = 1/2$.  Since $\pr{A \mid B} =
\pr{A}$, events $A$ and $B$ are independent.

% One can draw a straightforward connection between our product rule for
% independent events and the product rule from combinatorics.
% Essentially, the produce rule applies to our probability space because
% the sample space consists of the Cartesian product of the sample
% spaces for the two independent coins.

Now suppose that we glue the coins together, heads to heads.  Now each
coin still has probability $1/2$ of coming up heads; that is, $\pr{A} =
\pr{B} = 1/2$.  But if the first coin comes up heads, then the glued on
second coin must be tails!  That is, $\prcond{A}{B} = 0$.  Now, since
$\prcond{A}{B} \neq \pr{A}$, the events $A$ and $B$ are not independent.

\subsection{The Independent Product Rule}

The Definition~\ref{indep1} of independence of events $A$ and $B$ does not
apply if the probability of $B$ is zero.  It's useful to extend the
definition to the zero probability case by defining \emph{every} event to
be independent of a zero-probability event---even the event itself.
\begin{definition}\label{indep2}
If $A$ and $B$ are events and $\pr{B} = 0$, then $A$ is defined to be
independent of $B$.
\end{definition}

Now there is an elegant, alternative way to define independence that is
used in many texts:
\begin{theorem}\label{indprod}
Events $A$ and $B$ are independent iff
\begin{equation}
\pr{A \intersect B} = \pr{A} \cdot \pr{B}. \tag{Independent
Product Rule}
\end{equation}
\end{theorem}

\begin{proof}
If $\pr{B} = 0$, then Theorem~\ref{indprod} follows immediately from
Definition~\ref{indep2}, so we may assume that $\pr{B} >0$.  Then
\begin{align*}
\text{$A$ is independent of $B$} & \text{  iff  } \prcond{A}{B} = \pr{A} &
\text{(Definition~\ref{indep1})}\\
& \text{  iff  } \frac{\pr{A \intersect B}}{\pr{B}} = \pr{A} &
    \text{(Definition~\ref{defcond})}\\
& \text{  iff  } \pr{A \intersect B} = \pr{A}\pr{B} & \text{(multiplying by $\pr{B}>0$)}
\end{align*}
\end{proof}

The Independent Product Rule is fundamental and worth remembering.  In
fact, many texts use the Independent Product Rule as the definition of
independence.

Notice that because the Rule is symmetric in $A$ and $B$, it follows
immediately that independence is a symmetric relation.  For this reason,
we do not have to say, ``$A$ is independent of $B$'' or vice versa; we can
just say ``$A$ and $B$ are independent''.

\subsection{Independence of the Complement}

We think of $A$ being independent of $B$ intuitively as meaning that
``knowing'' whether \emph{or not} $B$ has occurred has no effect on the
probability of $A$.  This intuition is supported by an easy, but important
property of our formal Definition~\ref{indep1} of independence:
\begin{lemma}\label{indcomp}
If $A$ is independent of $B$, then $A$ is independent of $\bar{B}$.
\end{lemma}

\begin{proof}
If $A$ is independent of $B$, then
\begin{align*}
\pr{A}\pr{\bar{B}} & =  \pr{A}(1-\pr{B})
             & \text{(Complement Rule)}\\
  & = \pr{A} - \pr{A}\pr{B}\\
  & = \pr{A} - \pr{A \intersect B} & \text{(independence)}\\
  & = \pr{A-B} &\text{(Difference Rule)}\\
  & = \pr{A \intersect \bar{B}} &\text{(Definition of $A-B$)}.
\end{align*}
That is,
\[
\pr{A}\pr{\bar{B}} =  \pr{A \intersect \bar{B}}
\]
so $A$ and $\bar{B}$ are independent by Theorem~\ref{indprod}.
\end{proof}

\subsection{Disjoint Events vs. Independent Events}

Suppose that events $A$ and $B$ are disjoint, as shown in
Figure~\ref{fig:dependent}; that is, no outcome is in both events.  In
the diagram, we see that $\pr{A}$ is non-zero.  On the other hand:
\begin{figure}[htbp]
  \centerline{\includegraphics[height=1.5in]{figures/dependent}}
  \caption{This diagram shows two disjoint events, $A$ and $B$.  Disjoint
    events are not independent!}
  \label{fig:dependent}
\end{figure}
\begin{displaymath}
  \pr{A \mid B} = \frac{\pr{A \cap B}}{\pr{B}} = 0.
\end{displaymath}
Therefore, $\pr{A \mid B} \neq \pr{A}$, and so event $A$ is not
independent of event $B$.  In general, \emph{disjoint} events are not
\emph{independent}.

\section{Independent Coins and Dice}

\subsection{An Experiment with Two Coins}

Suppose that we flip two independent, fair coins.  Let $A$ be the event
that the coins match; that is, both are heads or both are tails.  Let $B$
the event that the first coin is heads.  Are these independent events?

At first, the answer may appear to be ``no''.  After all, whether or
not the coins match depends on how the first coin comes up; if we toss
$HH$, then they match, but if we toss $TH$, then they do not.

The preceding observation is true, but does not imply dependence.
Independence is a precise, technical concept, and may hold even if there
is a ``causal'' relationship between two events.  In this case, the two
events \emph{are} independent, as we prove by the usual procedure.
\begin{claim}
  Events $A$ and $B$ are independent.
\end{claim}

  \begin{figure}[htbp]
    \centerline{\includegraphics[height=2.5in]{figures/20coinsa}}
    \caption{This is a tree diagram for the two coins experiment.}
    \label{fig:20coinsa}
  \end{figure}

\begin{proof}
We must show that $\pr{A \mid B} = \pr{A}$.

  \emph{Step 1: Find the Sample Space.} The tree diagram in
  Figure~\ref{fig:20coinsa} shows that there are four outcomes in this
  experiment, $HH$, $TH$, $HT$, and $TT$.

  \emph{Step 2: Define Events of Interest.}  As previously defined, $A$
  is the event that the coins match, and $B$ is the event that the first
  coin is heads.  Outcomes in each event are marked in the tree diagram.
  
  \emph{Step 3: Compute Outcome Probabilities.}  Since the coins are
  independent and fair, all edge probabilities are $1/2$.  We
  find outcome probabilities by multiplying edge probabilities on each
  root-to-leaf path.  All outcomes have probability $1/4$.

  \emph{Step 4: Compute Event Probabilities.}  
  \begin{gather*}
    \pr{A \mid B} = \frac{\pr{A \cap B}}{\pr{B}}
                  = \frac{\pr{HH}}{\pr{HH} + \pr{HT}}
                  = \frac{1/4}{1/4 + 1/4}
                  = \frac{1}{2} \\
    \pr{A} = \pr{HH} + \pr{TT}
           = \frac{1}{4} + \frac{1}{4}
           = \frac{1}{2}
  \end{gather*}
  Therefore, $\pr{A \mid B} = \pr{A}$, and so $A$ and $B$ are
  independent events as claimed.
\end{proof}


\subsection{A Variation of the Two-Coin Experiment}

Now suppose that we alter the preceding experiment so that the coins are
independent, but not fair.  That is each coin is heads with
probability $p$ and tails with probability $1-p$.  Again, let $A$ be
the event that the coins match, and let $B$ the event that the first
coin is heads.  Are events $A$ and $B$ independent for all values of
$p$?

The problem is worked out with a tree diagram in
Figure~\ref{fig:20coinsb}.  The sample space and events are the same
as before, so we will not repeat steps 1 and 2 of the probability
calculation.

\begin{figure}[htbp]
  \centerline{\includegraphics[height=2.5in]{figures/20coinsb}}
  \caption{This is a tree diagram for a variant of the two coins
  experiment.  The coins are still independent, but no longer
  necessarily fair.}  \label{fig:20coinsb}
\end{figure}

\emph{Step 3: Compute Outcome Probabilities.} Since the coins are
independent, all edge probabilities are $p$ or $1-p$.  Outcome
probabilities are products of edge probabilities on root-to-leaf
paths, as shown in Figure~\ref{fig:20coinsb}. %the figure.

\emph{Step 4: Compute Event Probabilities.} We want to determine
whether $\pr{A \mid B} = \pr{A}$.
\begin{gather*}
\pr{A \mid B} = \frac{\pr{A \cap B}}{\pr{B}}
              = \frac{\pr{HH}}{\pr{HH} + \pr{HT}}
              = \frac{p^2}{p^2 + p(1-p)}
              = p \\
\pr{A} = \pr{HH} + \pr{TT} = p^2 + (1-p)^2 = 1 - 2p + 2p^2
\end{gather*}
Events $A$ and $B$ are independent only if these two probabilities are
equal:
\begin{eqnarray*}
\pr{A \mid B}   & = &   \pr{A} \\
\Leftrightarrow \quad \quad
p               & = &   1 - 2p + 2p^2 \\
\Leftrightarrow \quad \quad
0               & = &   1 - 3p + 2p^2 \\
\Leftrightarrow \quad \quad
0               & = &   (1 - 2p)(1 - p) \\
\Leftrightarrow \quad \quad
p               & = &   \frac{1}{2}, 1
\end{eqnarray*}
The two events are independent only if the coins are fair or if both
always come up heads.  Evidently, there was some dependence lurking in
the previous problem, but it was cleverly hidden by the unbiased
coins!

\iffalse
By looking more closely at the tree diagrams, however, we can
gain some intuition into why this is true. The topmost path ($HH$)
represents the case that event $A$ happens if event $B$ happens, the
bottommost path ($TT$) represents the case that $A$ happens if event
$B$ does not happen. If the probabilities on these two paths are the
same, then event $A$ happens with the same probability whether or not
$B$ happens. This implies that $p^2 = (1-p)^2$, which you can verify
gives us the same result as before.
\fi


\subsection{Independence of Dice Events [Optional]}

\begin{optional}

Suppose we throw two fair dice.  Is the event that the sum is equal to
a particular value independent of the event that the first throw
yields a particular value? More specifically, let $A$ be the event
that the first die turns up $3$ and $B$ the event that the sum is $6$.
Are the two events independent?

No, because
\[
\pr{B \mid A} = \frac{\pr{B \cap A}}{\pr{A}} =
\frac{1/36}{1/6} = \frac{1}{6},
\]
whereas $\pr{B} = 5/36$.

On the other hand, let $A$ be the event that the first die turns up
$3$ and $B$ the event that the sum is $7$.  Then
\[
\pr{B \mid A} = \frac{\pr{B \cap A}}{\pr{A}} =
\frac{1/36}{1/6} = \frac{1}{6},
\]
whereas $\pr{B} = 6/36$.  So in this case, the two events are
independent.

Can you explain the difference between these two results?

\end{optional}

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

\subsection{Example: Blood Evidence}

During the O.\,J. Simpson trial a few years ago, a probability problem
involving independence came up.  A prosecution witness claimed that
only one in 200 Americans has the blood type found at the crime scene.
The witness then presented facts something like the following:
\begin{itemize}
\item $\cfrac{1}{10}$ of people have type $O$ blood.
\item $\cfrac{1}{5}$ of people have a positive Rh factor.
\item $\cfrac{1}{4}$ of people have another special marker.
\end{itemize}
The one in~200 figure came from multiplying these three fractions.
Was the witness reasoning correctly?

The answer depends on whether or not the three blood characteristics
are independent. This might not be true; maybe most people with $O^+$
blood have the special marker. When the math-competent defense lawyer
asked the witness whether these characteristics were independent, he
could not say. He could not justify his claim.

\subsection{Definition of Mutual Independence}

What sort of independence is needed to justify multiplying probabilities
of more than two events?  The notion we need is called \emph{mutual
independence}.
\begin{definition}
  Events $A_1, A_2, \dots, A_n$ are \emph{mutually independent} if for
  all $i$ such that $1 \leq i \leq n$ and for all $J \subseteq \set{1,\dots, n} -
  \set{ i }$, we have:
  \[
  \pr{A_i \biggm| \bigcap_{j \in J} A_j} = \pr{A_i}.
  \]
\end{definition}

In other words, a collection of events is mutually independent if each
event is independent of the intersection of every subset of the others.
An equivalent way to formulate mutual independence is give in the next
Lemma, though we will skip the proof.  Some texts use this formulation as
the definition.

\begin{lemma}\label{Lmut}
  Events $A_1, A_2, \dots, A_n$ are \emph{mutually independent} iff for
  all $J \subseteq \set{1,\dots,n}$, we have:
  \[
  \pr{\bigcap_{j \in J} A_j} = \prod_{j \in J} \pr{A_j}.
  \]
\end{lemma}

For example, for $n=3$, Lemma~\ref{Lmut} says that
\begin{corollary*}
Events $A_1$, $A_2$, $A_3$ are mutually independent iff all of the
following hold:
\begin{eqnarray}
\pr{A_1 \cap A_2} & = & \pr{A_1} \cdot \pr{A_2} \notag\\
\pr{A_1 \cap A_3} & = & \pr{A_1} \cdot \pr{A_3} \notag\\
\pr{A_2 \cap A_3} & = & \pr{A_2} \cdot \pr{A_3} \notag\\
\pr{A_1 \cap A_2 \cap A_3} & = & \pr{A_1} \cdot \pr{A_2} \cdot \pr{A_3}\label{all-three}
\end{eqnarray}
\end{corollary*}

Note that $A$ is independent of $B$ \emph{iff} it is independent of
$\bar{B}$. This follows immediately from Lemma~\ref{indcomp} and the fact
that $\bar{\bar{B}} = B$.  This result also generalizes to many events and
provides yet a third equivalent formulation of mutual independence.
Again, we skip the proof:
\begin{theorem}\label{indncomp}
For any event, $A$, let $A^{(1)} \eqdef A$ and $A^{(-1)} \eqdef \bar{A}$.
Then events $A_1, A_2, \dots, A_n$ are mutually independent iff
\begin{equation}
\prod_{i=1}^n \pr{A_i^{(x_i)}} = \pr{\lgintersect_{i=1}^n A_i^{(x_i)}}
\end{equation}
for all $x_i \in \set{1,-1}$ where $1 \le i \le n$.
\end{theorem}

\subsection{Carnival Dice Revisited}

We have already considered the gambling game of Carnival Dice in
Section~\ref{carnival}.  Now, using independence we can more easily work
out the probability that the player wins by calculating the probability of
its \emph{complement}.

Namely, let $A_i$ be the event that the $i$th die matches the player's
guess.  So $A_1 \cup A_2 \cup A_3$ is the event that the player wins.  But
\begin{displaymath}
  \pr{A_1 \cup A_2 \cup A_3} =
  1 - \pr{\overline{A_1 \cup A_2 \cup A_3}} =
  1 - \pr{\overline{A_1} \cap \overline{A_2} \cap \overline{A_3}}.
\end{displaymath}
Now, since the dice are independent, Theorem~\ref{indncomp} implies
\begin{displaymath}
  \pr{\overline{A_1} \cap \overline{A_2} \cap \overline{A_3}} =
  \pr{\overline{A_1}} \pr{\overline{A_2}} \pr{\overline{A_3}} =
  \bigl(5/6)^3.
\end{displaymath}
Therefore
\begin{displaymath}
  \pr{A_1 \cup A_2 \cup A_3} = 1 - \bigl(5/6)^3 = \frac{91}{216}.
\end{displaymath}
This is the same value we computed previously using Inclusion-Exclusion.
But with independent events, the approach of calculating the complement is
often easier than using Inclusion-Exclusion.  Note that this example
generalizes nicely to a larger number of dice---with 6~dice the
probability of a match is $1 - \bigl(5/6)^6 \approx 67\%$, with 12~dice it
is $1 - \bigl(5/6)^{12} \approx 89\%$.  Using Inclusion-Exclusion in these
cases would have been messy.

\subsection{Circuit Failure Revisited}

Let's reconsider the circuit problem from section~\ref{crct}, where a
circuit containing $n$ connections is to be wired up and $A_i$ is the
event that the $i$th connection is made correctly.  Again, we want
to know the probability that the entire circuit is wired correctly, but
this time when we know that all the events $A_i$ are \emph{mutually independent}.

If $p \eqdef \pr{\bar{A_i}}$ is the probability that the $i$th connection
is made \emph{incorrectly}, then because the event are independent, we can
conclude that the probability that the circuit is correct is $\prod_1^n
\pr{A_i} = (1-p)^n$.  For $n = 10$, and $p = 0.01$ as in
section~\ref{crct}, this comes out to around 90.4\%---very close to the
lower bound.  That's because the lower bound is achieved when at most one
error occurs at a time, which is nearly true in this case of independent
errors, because the chance of more than one error is relatively small
(less than 1\%).

% I get 1 - 90.4 - 10 (.99)^9 (.01), = ...

\subsection{A Red Sox Streak [Optional]}

\begin{optional}

The Boston Red Sox baseball team has lost 14 consecutive playoff
games.  What are the odds of such a miserable streak?

Suppose that we assume that the Sox have a $1/2$ chance of
winning each game and that the game results are mutually independent.
Then we can compute the probability of losing 14 straight games as
follows.  Let $L_i$ be the event that the Sox lose the $i$th game.
This gives:

\begin{eqnarray*}
\pr{L_1 \cap L_2 \cap \dots \cap L_{14}}
        & = & \pr{L_1} \pr{L_2} \cdots \pr{L_{14}} \\
        & = & \left( \frac{1}{2} \right)^{14} \\
        & = & \frac{1}{16,384}
\end{eqnarray*}

The first equation follows from the second definition of mutual
independence.  The remaining steps use only substitution and
simplification.

These are pretty long odds; of course, the probability that the Red
Sox lose a playoff game may be greater than $1/2$.  Maybe
they're cursed.

\end{optional}


\subsection{An Experiment with Three Coins}

This is a tricky problem that always confuses people!  Suppose that we
flip three fair coins and that the results are mutually independent.
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 these three events mutually independent?

The sample space 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$.  We are interested
in events $A_1$, $A_2$, and $A_3$, defined as above.  Each outcome has
probability $1/8$.

To see if the three events are mutually independent, we must prove
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{TTT} + \pr{TTH} \\
         & = & \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!  When proving a set
of events independent, remember to check all pairs of events,
\emph{and} all sets of three events, four events, etc.

\subsection{Pairwise Independence}\label{pairwise}

It's a common situation to have all pairs of events in some collection are
independent, but not to know whether three or more of the events are going
to be independent.  It also turns out to be important enough that a
special term has been defined for this situation:
\begin{definition*}
  Events $A_1, A_2, \dots A_n, \dots$ are \emph{pairwise independent} if
  $A_i$ and $A_j$ are independent events for all $i \neq j$.
\end{definition*}
Note that mutual independence is stronger than pairwise independence.
That is, if a set of events is mutually independent, then it must be
pairwise independent, but the reverse is not true.  For example, the
events in the three coin experiment of the preceding subsection were
pairwise independent, but not mutually independent.

In the blood example, suppose initially that we know nothing about
independence.  Then we can only say that the probability that a person
has all three blood factors is no greater than the probability that a
person has blood type $O$, which is $1/10$.

If we know that the three blood factors in the O.\,J. case appear
pairwise independently, then we can conclude:
\begin{eqnarray*}
\pr{\mbox{person has all 3 factors}}
        & \leq & \pr{\mbox{person is type $O$ and Rh positive}} \\
        & = & \pr{\mbox{person is type $O$}}
              \pr{\mbox{person is Rh positive}} \\
        & = & \frac{1}{10} \cdot \frac{1}{5} \\
        & = & \frac{1}{50}
\end{eqnarray*}

Knowing that a set of events is pairwise independent is useful!  However,
if all three factors are mutually independent, then the witness is right;
the probability a person has all three factors is $1/200$.  Knowing that
the three blood characteristics are mutually independent is what justifies
the witness's in multiplying the probabilities as in
equation~(\ref{all-three}).  The point is that we get progressively
tighter upper bounds as we strengthen our assumption about independence.

This example also illustrates an 
\begin{quote}
\textbf{Important Technicality:} To prove a set of three or more events
mutually independent, it is \emph{not} sufficient to prove every pair of
events independent!  In particular, for three events we must also prove
that equality~(\ref{all-three}) also holds.
\end{quote}

\section{The Birthday Problem}

\iffalse
Most people expect that, if the same experiment is repeated over and
over again, independently, the results are likely to be very varied.
However, some patterns are actually pretty likely.
\fi

\subsection{The Problem}

What is the probability that two students among a group of 100 have the
same birthday?  There are 365 birthdays (month, date) and 100 is less than
a third of 365, so an offhand guess might be that the probability is
somewhere between 1/3 and 2/3.  Another approach might be to think of the
setup as having 100 chances of winning a 365-to-1 bet; there is roughly
only a 25\% chance of winning such a bet.  But in fact, the probability
that some two among the 100 students have the same birthday is
overwhelming: there is less than one chance in thirty million that all 100
students have different birthdays!

As a matter of fact, by the time we have around two dozen students, the
chances that two have the same birthday is close to 50\%.  This seems odd!
There are 12 months in the year, yet at a point when we've only collected
about two birthdays per month, we have usually already found two students
with exactly the same birthday!

There are two assumptions underlying these assertions.  First, we assume
that all birth dates are equally likely.  Second, we assume that birthdays
are mutually independent.  Neither of these assumptions are really true.
Birthdays follow seasonal patterns, so they are not uniformly distributed.
\iffalse (Try counting back nine months from your birthday!)\fi Also,
birthdays are often related to major events.  For example, nine months
after a blackout in the 70's there was a sudden increase in the number of
births in New England.  Since students in the same class are generally the
same age, their birthdays are more likely to be dependent on the same
major event than the population at large, so they won't be mutually
independent.  But when there wasn't some unusual event 18 to 22 years ago,
student birthdays are close enough to being uniform that we won't be too
far off assuming uniformity and independence, so we will stick with these
assumptions in the rest of our analysis.

\subsection{Solution}

There is an intuitive reason why the probability of matching birthdays is
so high.  The probability that a given pair of students have the same
birthday is only $1/365$.  This is very small.  But with around two dozen
students, we have around 365 \emph{pairs} of students, and the probability
one of these 365 attempts will result in an event with probability 1/365
gets to be about 50-50.  With 100 students there are about 5000 pairs, and
it is nearly certain that an event with probability $1/365$ will occur at
least once in 5000 tries.

In general, suppose there are $m$ students and $N$ days in the year.
We want to determine the probability that at least two students have
the same birthday.  Let's try applying our usual method.

\subsubsection*{Step 1.  Find the Sample Space}
\iffalse
Finding the sample space with a tree diagram is difficult.  Each
internal node will have $N$ children, and the tree will have depth
$m$.  For the values of $N$ and $m$ of interest, this tree will be huge!

We have to find the sample space a different way.  There are $N$ possible
birthdays for the first student, $N$ birthdays for the second student, and
so on for all $m$ students.
\fi

We can regard an outcome as an $m$-vector whose components are the
birthdays of the $m$ students in order.  That is, the sample space is the
set of all such vectors:
\[
\sspace \eqdef \set{ \ang{b_1, b_2, \dots, b_m} \suchthat b_i \in
\set{1,2,\dots, N}
\mbox{ for } 1 \le i \le m}.
\]
There are $N^m$ such vectors.

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

Let $A$ be the event that two or more students have the same birthday.
That is,
\[
A \eqdef \set{ \ang{b_1, b_2, \dots, b_m} \suchthat b_i = b_j
                \mbox{ for some } 1 \le i \neq j \le m}.
\]

\subsubsection*{Step 3:  Compute Outcome Probabilities}

The probability of outcome $\ang{b_1, b_2, \dots, b_m}$ is the probability
that the first student has birthday $b_1$, the second student has birthday
$b_2$, \etc.  The $i$th person has birthday $b_i$ with probability $1/N$.
Assuming birth dates are independent, we can multiply probabilities to get
the probability of a particular outcome:
\[
\pr{\ang{b_1, b_2, \dots, b_m}} = \frac{1}{N^m}.
\]
So we have a uniform probability space---the probabilities of
all the outcomes are the same.

\iffalse

In principle, we could obtain the same result from a tree diagram.
Since each students is equally likely to have any one of $N$
birthdays, independent of all other students, we would label every
edge in the tree with probability $1/N$.  Then we would
compute the probability of an outcome by multiplying probabilities on
the corresponding root-to-leaf path.  Since the tree has depth $m$, we
would find that every outcome has probability $1/N^m$, exactly
as above.
\fi

\subsubsection*{Step 4:  Compute Event Probabilities}

The remaining task in the birthday problem is to compute the probability
of the event that two or more students have the same birthday.  Since the
sample space is uniform, we need only count the number of outcomes in the
event $A$.  This can be done with Inclusion-Exclusion, but the
calculation is involved.

A simpler method is to use the trick of ``counting the complement.''  Let
$\bar{A}$ be the complementary event; that is, let $\bar{A} \eqdef \sspace
- A$.  Then, since $\pr{A} = 1 - \pr{\bar{A}}$, we need only determine the
probability of event $\bar{A}$.

In the event $\bar{A}$, all students have different birthdays.  The
event consists of the following outcomes:
\[
\set{ \ang{b_1, b_2, \dots, b_m} \suchthat \text{ all the $b_i$'s are distinct}}
\]
In other words, the set $\bar{A}$ consists of all \emph{$m$-permutations}
of the set of $N$ possible birthdays!  So now we can compute the probability
of $\bar{A}$:
\[
\pr{\bar{A}} = \frac{\card{\bar{A}}}{\card{\sspace}} =
\frac{\card{\bar{A}}}{N^m} = \frac{P(N, m)}{N^m} = \frac{N!}{(N-m)!\ N^m},
\]
\iffalse

Because we have a uniform sample space, we can reduce the probability
problem to a counting problem in the first step.  In the second step, we
substitute in the size of the sample space $\sspace$.  In the third step,
we use the observation that $\bar{A}$ is the set of all $m$-permutations
of an $N$ element set.  In the last step, we substitute the value of $P(N,
m)$ that we worked out a few weeks ago.
\fi
and so
\[
\pr{A} = 1 - \frac{N!}{(N-m)! \ N^m},
\]
which is a simple formula for the probability that at least two
students among a group of $m$ have the same birthday in a year with $N$
days.

Letting $m = 22$ students and $N = 365$ days, we conclude that at least
one pair of students have the same birthday with probability $\approx
0.476$.  If we have $m = 23$ students, then the probability rises to $
\approx 0.507$.  So in a room with 23 students, the odds are in fact
better than even that at least two have the same birthday.

\subsection{Approximating the Answer to the Birthday Problem}

We now know that $\pr{A} = 1 - N!/((N-m)! \, N^m)$, but this formula is
hard to work with because it is not a closed form.  Evaluating the
expression for, say, $N = 365$ and $m = 100$ is a lot of work.  It's even
harder to determine how big $N$ must be for the probability of a birthday
match among $m=100$ students to equal, say, 90\%.  We'd also like to
understand the growth rate of the probability as a function of $m$ and
$N$.

\iffalse

There is another reason to want a closed form.  We might want to know
how many students are needed so that at least two have the same
birthday with probability $1/2$.  We computed this for a year
with $N = 365$ days, but what is the answer as a function
of $N$?

Unfortunately, there is no closed form for $\pr{A}$.  There is a nice
approximation for $\pr{\bar{A}}$ using Stirling's formula, but some
ugly math is required to find it!  Hold on tight!
\begin{eqnarray*}
\frac{N!}{(N-m)! \ N^m}
        & = &   \frac{  \sqrt{2 \pi N}
                        \left( \frac{N}{e} \right)^N
                        e^{a_N}         }
                     {  \sqrt{2 \pi (N-m)}
                        \left( \frac{N-m}{e} \right)^{N-m}
                        e^{a_{N-m}}
                        N^m             } \\
        & = &   \sqrt{\frac{N}{N-m}} \ 
                \frac{  N^N
                        e^{N-m}
                        e^{a_N - a_{N-m}}               }
                     {  (N-m)^{N-m}
                        e^N
                        N^m             } \\
        & = &   \sqrt{\frac{N}{N-m}} \ 
                \frac{  e^{a_N - a_{N-m}}               }
                     {  e^m
                        \left( 1 - \frac{m}{N} \right)^{N-m}
                                        }
\end{eqnarray*}
In the expressions above, the symbol $a_i$ denotes some value between
$\cfrac{1}{12i+1}$ and $\cfrac{1}{12i}$.  In effect, $a_i$ captures the
error in Stirling's approximation.

The last expression is useful for approximating $\pr{\bar{A}}$.
For example, substituting $N=365$ and $m=23$ gives approximately:
\begin{displaymath}
  \pr{\bar{A}}  = 1.033 \ \frac{0.99998}{2.097} = 0.492\dots
\end{displaymath}
Substituting $N=365$ and $m = 100$ gives:
\begin{displaymath}
  \pr{\bar{A}} = 1.174 \ \frac{0.99991}{3.82 \cdot 10^6} = 3.073 \cdot 10^{-7}
%  \pr{\bar{A}} = 1.221 \ \frac{0.99999}{5.00 \cdot 10^9} = 2.442 \cdot 10^{-10}
\end{displaymath}
The main difference between these two cases is the denominator of the
fraction.  For $m = 23$, the denominator is about 2.  For $m = 100$,
it is almost 4 million!

Since the denominator is the main term, let's try to simplify it some
more.  The first step looks arbitrary; we apply the identity $x =
e^{\ln x}$, seemingly at random:
\begin{eqnarray*}
e^m \left( 1 - \frac{m}{N} \right)^{N-m}
        & = & e^m \left( e^{\ln(1 - \frac{m}{N})} \right)^{N-m} \\
\end{eqnarray*}
The motivation for the preceding step is that there is a nice Taylor
series expansion for $\ln(1-x)$:
\[
\ln(1-x) = - x - \frac{x^2}{2} - \frac{x^3}{3} - \dots
\]
We can now continue by replacing $\ln(1 - \cfrac{m}{N})$ with the
Taylor series:
\begin{eqnarray*}
e^m \left( e^{\ln(1 - \frac{m}{N})} \right)^{N-m}
        & = & e^m e^{(- \frac{m}{N} - \frac{m^2}{2N^2}
                        - \frac{m^3}{3N^3} - \dots)(N-m)} \\
        & = & e^m e^{
                (-m - \frac{m^2}{2N} - \frac{m^3}{3N^2} - \dots) +
                (\frac{m^2}{N} + \frac{m^3}{2N^2} + \frac{m^4}{3N^3} + \dots)
                    } \\
        & = & e^{\frac{m^2}{2N}+\frac{m^3}{6N^2}+\frac{m^4}{12N^3}+\dots} \\
        & \geq & e^{\frac{m^2}{2N}}
\end{eqnarray*}
Now we have simplified the denominator in our expression for
$\pr{\bar{A}}$.  Substituting the simplified denominator back into
this expression gives:
\[
\pr{\bar{A}} \leq \sqrt{\frac{N}{N-m}} \ e^{-\frac{m^2}{2N}}
\]

This is the pretty approximation we were aiming for!
\fi

It turns out that there is a nice asymptotic formula for the probability,
namely,
\begin{equation}\label{birthapprox}
\pr{\bar{A}}  \sim  e^{-\frac{m^2}{2N}}.
\end{equation}
as long as $m = o(N^{2/3})$.

\iffalse
, then our approximation
is really very good.  The reason is that the major source of error was
truncating the Taylor series for a logarithm.  The terms we threw out
were:
\[
\frac{m^3}{6N^2}+\frac{m^4}{12N^3}+\dots
\]
Under the assumption that $m = o(N^{2/3})$, these terms all go
to zero as $N$ becomes large.  Furthermore, under this same assumption
the term
\[
\sqrt{\frac{N}{N-m}} = \sqrt{\frac{1}{1-m/N}}
\]
in our formula tends to 1 as $N$ grows
large. 
\fi

This formula actually has an intuitive explanation.  The number of ways to
pair $m$ students is $\binom{m}{2} \approx m^2/2$.  The event that a pair
of students has the same birthday has probability $1/N$.  Now if these
events were mutually independent, then using the approximation $1-x
\approx e^{-x}$, we could essentially arrive at~(\ref{birthapprox}) by
calculating
\begin{eqnarray*}
\pr{\bar{A}}
        & \approx & \left( 1 - \frac{1}{N} \right)^{\frac{m^2}{2}} \\
        & \approx & e^{-\frac{1}{N} \cdot \frac{m^2}{2}} \\
        & = & e^{-\frac{m^2}{2N}}.
\end{eqnarray*}

The problem is that the events that pairs of students have distinct
birthdays are \emph{not} mutually independent.  For example,
\[
\prcond{b_1=b_3}{b_1=b_2,b_2=b_3} = 1 \neq 1/N = \pr{b_1=b_3}.
\]
But notice that if we have a set of \emph{nonoverlapping} pairs of
students, then the event that a given pair in the set have the same
birthday really is independent of whether the other pairs have the same
birthday.  That is, we do have mutual independence for any set of
nonoverlapping pairs.  But if $m$ is small compared to $N$, then the
likelihood will be low that among the pairs with the same birthday, there
are two overlapping pairs.  In other words, we could expect that for small
enough $m$, the events that pairs have the same birthday are likely to be
distributed in the same way as if they were mutually independent,
justifying the independence assumption in our simple calculation.

Of course this intuitive argument requires more careful justification.
The asymptotic equality~(\ref{birthapprox}) can in fact be proved by an
algebraic calculation using Stirling's Formula and the Taylor series for
$\ln(1-x)$, but we will skip it.

This asymptotic equality also shows why the probability that all students
have distinct birthdays drops off rapidly as the number of students grows
beyond $\sqrt{N}$ toward $N^{2/3}$.  The reason is that the
probability~(\ref{birthapprox}) decreases in inverse proportion to a
quantity obtained by \emph{squaring and then exponentiating} the number of
students.

\subsection{The Birthday Principle}

\iffalse
\subsubsection{Making the Probability of a Match 1/2}
\fi

As a final illustration of the usefulness of the asymptotic
equality~(\ref{birthapprox}), we determine as a function of $N$ the number
of students for which the probability that two have the same birthday is
(approximately) $1 / 2$.

\iffalse
First, notice that if $m = o(N^{2/3})$, then our approximation
is really very good.  The reason is that the major source of error was
truncating the Taylor series for a logarithm.  The terms we threw out
were:
\[
\frac{m^3}{6N^2}+\frac{m^4}{12N^3}+\dots
\]
Under the assumption that $m = o(N^{2/3})$, these terms all go
to zero as $N$ becomes large.  Furthermore, under this same assumption
the term
\[
\sqrt{\frac{N}{N-m}} = \sqrt{\frac{1}{1-m/N}}
\]
in our formula tends to 1 as $N$ grows
large.  Therefore, with this assumption we can conclude:
\[
\pr{\bar{A}}  \sim  e^{-\frac{m^2}{2N}}
\]
\fi

All we need do is set the probability that all birthdays are distinct to
$1/2$ and solve for the number of students.
\begin{eqnarray*}
e^{-\frac{m^2}{2N}}     & \sim &  \frac{1}{2} \\
e^{\frac{m^2}{2N}}      & \sim &  2 \\
\frac{m^2}{2N}          & \sim &  \ln 2 \\
m                       & \sim &  \sqrt{2 N \ln 2} \approx 1.177 \sqrt{N}.
\end{eqnarray*}
Since the values of $m$ here are $\Theta(\sqrt{N}) = o(N^{2/3})$, the
conditions for our asymptotic equality are met and we can expect our
approximation to be good.

For example, if $N = 365$, then $1.177 \sqrt{N} = 22.49$.  This is
consistent with out earlier calculation; we found that the probability
that at least two students have the same birthday is $1/2$ in a room with
around 22 or 23 students.  Of course, one has to be careful with the
$\sim$ notation; we may end up with an approximation that is only good for
very large values.  In this case, though, our approximation works well for
reasonable values.

The preceding result is called the Birthday Principle.  It can be
interpreted this way: if you throw about $\sqrt{N}$ balls into $N$
boxes, then there is about a 50\% chance that some box gets two balls.

For example, in 27 years there are about 10,000 days.  If we put about
$1.177 \sqrt{10,000} \approx 118$ people under the age of 28 in a room,
then there is a 50\% chance that at least two were born on exactly the
same day of the same year!  As another example, suppose we have a roomful
of people, and each person writes a random number between 1 and a million
on a piece of paper.  Even if there are only about $1.177 \sqrt{1,000,000}
= 1177$ people in the room, there is a 50\% chance that two wrote exactly
the same number!

\end{document}


%%%===========================================================

\iffalse

\subsection{Countable Sets}

A key concept in probability theory---and in many other parts of
Mathematics--- is the notion of a \emph{countable} set.  Intuitively, a
set, $C$, is countable if there is a way to count its elements $c_0, c_1,
\dots$ in some order.  For finite sets, we've already seen this idea
formalized by saying there is a bijection from $\set{1,\dots,n}$ to the
set, $C$, for some $n \ge 0$.  When $C$ is infinite, we just keep
counting:

\begin{definition}
A set, $C$, is \emph{countable} iff it is finite or there is a bijection
from $\naturals$ to $C$.
\end{definition}

\iffalse

% if bijection was replaced by surjection, we'd need:

\begin{lemma*}
Every finite set is countable.
\end{lemma*}
\begin{proof}
A set $C$ is finite iff it is of size $n$ for some $n \in \naturals$.  The
empty set is countable by definition, so let $C$ be a finite set and $c$
be an element of $C$.  We need to define a surjection from $\naturals$ to $C$.

Since $C$ is a nonempty finite set, by definition there is a bijection
$f:\set{1,\dots,n} \to C$ for some $n\ge 1$.  But then bijection, $g:
\naturals \to C$ is simply defined by the rule:
\[
g(k) \eqdef \begin{cases}
             f(k+1) & \text{if $k < n$,}\\
             c & \text{otherwise}.
            \end{cases}
\]
\end{proof}
\fi

The simplest example of an infinite countable set is the set of natural
numbers---the required bijection is simply the identity function.  A
slightly more interesting example is the set $\ints$ of \emph{all}
integers.  We can ``count'' them in the order $0, -1, 1, 2, 2, \dots$.
Formally the function
\[
f(n) \eqdef \begin{cases}
             \frac{n}{2} & \text{if $n$ is even,}\\
             -\frac{n + 1}{2} & \text{otherwise}
            \end{cases}
\]
defines the required bijection from $\naturals$ to $\ints$.

Most of the sets we deal with in Computer Science turn out to be
countable.  The reason for this is that any set whose elements can be
\emph{coded into \textbf{finite} bit-strings} will be a countable set.

\begin{theorem}\label{bits}
A nonempty set is countable iff there is a \emph{sur}jection from the set
of finite-length binary strings onto the set.
\end{theorem}

The idea here is to think of a bit string as the code of an element in a
given countable set.  The element the bit string codes is what it maps to
under the surjection.  Since the mapping is a surjection, every element of
the set has at least one code; it may have more than one.

Theorem~\ref{bits} has some easy consequences that may seem surprising:
for example, the rational numbers, $\rationals$, are countable.  In fact,
all the following sets are countable:
\begin{enumerate}

\item \label{natsq} the set $\naturals^2$ of \emph{pairs} of natural numbers:
letting a bitstring, $s$, code the pair
\[
(\# \text{\texttt{0}'s in }s, \# \text{\texttt{1}'s in }s)
\]
is an example of a surjection from bitstrings to $\naturals^2$.

\item the set of rational numbers, $\rationals$: let $s$ code the rational
$am/(n+1)$ where $(m,n) \in \naturals^2$ is the pair of natural numbers coded
by $s$ as in~\ref{natsq}, and $a = \pm 1$ depending on whether $s$ starts
with \texttt{1} or \texttt{0}.

\item\label{bincount} the set of finite-length binary strings: duh \dots.

\item\label{subcount} any subset, $D$, of a countable set, $C$: fix some
element $d$ in $D$ (if there is none, $D$ is countable because it's
empty).  Since $C$ is countable, any binary string, $s$, codes some
element $c_s \in C$.  So we can use $s$ as the code of an element of $D$
by letting $s$ code the same element, $c_s$, if it happens to be in $D$,
and letting $s$ code $d$ when $c_s \notin D$.

\item \label{nat*} the set, $\naturals^*$, of all \emph{finite-length}
sequences of natural numbers: let $s$ code the sequence consisting of the
lengths of its successive blocks of zeros.  For example,
\texttt{001000010111000} codes the sequence (2,4,1,0,0,3).

\item \label{tern} the set of finite length \emph{ternary} (digits 0, 1,
2) strings: let $\sigma \in \naturals^*$ be the sequence of natural numbers
coded by $s$ as in~\ref{nat*}., and replace each element, $n$, in $\sigma$
by $\max(n,2)$.

\item\label{binsq} the set of \emph{pairs} of finite-length binary
strings: let $t$ be the ternary string that $s$ codes according
to~\ref{tern}.  If $t$ does not have exactly one occurrence of the digit
\texttt{2}, let $s$ code the pair (\texttt{0},\texttt{0}); otherwise let
$s$ code the pair $(x,y)$ where $t=x3y$.

\item \label{countunion} a countable union of countable sets.

This means that if we have a countable set, $C$, and for each $c \in C$,
there is a countable set $A_c$, then
\[
U \eqdef \lgunion_{c \in C} A_c
\]
is countable.

\iffalse So we are given that every element of $C$ has at least one binary
code, and for each $c \in C$, every element of $A_c$ has a binary code.
\fi

Let $s$ code a member of $U$ as follows: let $(x,y)$ be the pair of binary
strings coded by $s$ as in~\ref{binsq}, and let $c$ be the element of $C$
that $x$ codes.  Then let $s$ code the same element of $A_c$ that $y$
codes.

\end{enumerate}

At this point you might wonder if there are any sets that are \emph{not}
countable.  The answer is ``lots''.  For example, the set of
\emph{infinite} binary sequences and the set of infinite sequences of
natural numbers are not countable sets.  Also, the set of \emph{real}
numbers is not countable.  More generally, the powerset of \emph{any}
infinite set is not countable.  The proof of this last claim closely
resembles Russell's paradox described in the Notes for the first week of
class.

These results surprised the Mathematics community when they were first
announced at the turn of the twentieth century.  Their proofs are easy and
fun, but use methods that don't play a role elsewhere in Probability
Theory, so we'll postpone them till we look again at the theory of
countability and uncountability at the end of the term.
\fi
