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

\begin{document}

\onlystudents

\lecture{conditional probability}{Combining Event Probabilities}{24 April 2001}

In this lecture we discuss ways to deal with more complex events.
First we consider the probability of unions of events.  Then we talk
about determining the probability of one event, given that some other
event happens. This is called a \emph{conditional probability}.

Probability is just a kind of counting; unsurprisingly, many of the
rules for counting have analogues in probability. The main features
today are two formulas, \emph{the product rule} and \emph{the sum
  rule} with its generalization, \emph{inclusion\slash exclusion}.

\section{Combinations of Events}

There is a gambling game called Carnival Dice.  A player picks a
number between 1 and 6 and then rolls three fair dice.  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 $\frac{1}{2}$.
\end{falseclm}
\begin{proof}[Incorrect proof]
  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) \\
             & = & \frac{1}{6} + \frac{1}{6} + \frac{1}{6} \\
             & = & \frac{1}{2}
  \end{eqnarray*}
\end{proof}
The only justification for the second equality is that it looks
vaguely reasonable; in fact, equality does not hold.  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.

Let's examine the expression $\Pr(A_1 \cup A_2 \cup A_3)$ to see
exactly what is happening.  Recall that the probability of an event is
the sum of the probabilities of the outcomes it contains.  Therefore,
we could argue as follows:
\begin{eqnarray*}
  \Pr(A_1 \cup A_2 \cup A_3) & = &
  \sum_{w \in A_1 \cup A_2 \cup A_3} \Pr(w) \\
  & = &   \sum_{w \in A_1} \Pr(w) +
  \sum_{w \in A_2} \Pr(w) +
  \sum_{w \in A_3} \Pr(w) \qquad\mbox{(*)}\\
  & = &   \Pr(A_1) + \Pr(A_2) + \Pr(A_3)
\end{eqnarray*}

Where did we get into trouble?  In the step labelled (*).  That step
assumes that the events $A_1$, $A_2$, and $A_3$ are \emph{disjoint;}
that is, there is no outcome in more than one event.  If this were not
true for some outcome, then a term would be duplicated when we split
the one sum into three.

\subsection{The Sum Rule}

The disjointness assumptions arises frequently enough to make a
special case for it.  The argument above proves the following theorem:
\begin{theorem}[Sum Rule]
  Let $A_1, A_2, \ldots A_n$ be disjoint events.
  \[
  \Pr(A_1 \cup A_2 \cup \ldots \cup A_n)
  = \Pr(A_1) + \Pr(A_2) + \ldots + \Pr(A_n)
  \]
\end{theorem}

The sum rule lets you 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\%.


\subsection{Inclusion Exclusion}

We can evaluate the probability of a union of events that are not
necessarily disjoint using a theorem analogous to Inclusion-Exclusion
for counting.  Here is the special case for a union of three events.
\begin{theorem}
  \label{th:inclexcl}
  Let $A_1$, $A_2$, and $A_3$ be events, not necessarily disjoint.
  \begin{eqnarray*}
    \Pr(A_1 \cup A_2 \cup A_3) & = &
    \Pr(A_1) + \Pr(A_2) + \Pr(A_3) \\
    & & \mbox{}- \Pr(A_1 \cap A_2) - \Pr(A_1 \cap A_3) - \Pr(A_2 \cap A_3) \\
    & & \mbox{}+ \Pr(A_1 \cap A_2 \cap A_3)
  \end{eqnarray*}
\end{theorem}
The proof is much the same as for Inclusion-Exclusion; details are
omitted.

We can use this theorem to compute the chance of winning at Carnival
Dice.  The probability that one die matches the player's guess is
$\frac{1}{6}$. The probability that two particular dice both match
the player's guess is $\frac{1}{36}$ (there are 36 possible outcomes
of the two dice; exactly one of them has both equal to the player's
guess).  The probability that all three dice match is $\frac{1}{216}$.
Plugging these numbers into the preceding theorem gives:
\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} \\
  & \approx & 42\%
\end{eqnarray*}
These are terrible odds in a gambling game; it is much better to play
roulette, craps, or blackjack!

What happened to our intuition of a 1/2 chance of winning?  Well, we
will see in a few lectures that the \emph{average} number of matching
dice in a game is 1/2.  However, in some cases we end up with more
than one matching die, and in balance there are
more-than-one-might-expect occurrences of zero matching dice.


\forstudents{%
\subsection{Derangements}

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[\cup 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 $i_1,\ldots,i_k$ are all the 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)!$.

  Thus, the \emph{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$.  }

\subsection{Counting Rules and Probability Rules}

There is a close relationship between computing the cardinality of a
set and computing the probability of an event.
Theorem~\ref{th:inclexcl} is an example; the probability of a union of
events and the cardinality of a union of sets are computed in very
similar ways.

In fact, all of the methods we developed for computing cardinalities
carry over to computing probabilities.  This is because a probability
space is just a weighted set; the sample space is the set and the
probability function assigns a weight to each element.  Earlier, we
were counting the number of items in a set.  Now, when we compute the
probability of an event, we are just summing the weights of items in a
set.  We will see many examples of the relationship between
probability and counting over the next few weeks.


\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, $\Pr(A \mid B)$ denotes
the probability of event $A$, given event $B$.  In this example,
$\Pr(A \mid B)$ is the probability that the person is an MIT student,
given that he or she is a Cambridge resident.

How do we compute $\Pr(A \mid 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, $\Pr(A \mid 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 gives:
\[
\Pr(A \mid B) = \frac{\Pr(A \cap B)}{\Pr(B)}
\]
Rearranging terms gives the following rule, which we will regard as
the definition of $\Pr(A \mid B)$.
\begin{rul}[Product Rule, special case]
  Let $A$ and $B$ be events.
  \[
  \Pr(A \cap B) = \Pr(B) \cdot \Pr(A \mid B)
  \]
\end{rul}
(We are now using the term ``Product Rule'' for two separate ideas.
One is the definition of $\Pr(A \mid B)$ given above, and the other is
the formula for the cardinality of a product of sets.  In the rest of
this lecture, the term 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 $\Pr(B \mid 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*}
\Pr(B \mid B)   & = & \frac{\Pr(B \cap B)}{\Pr(B)} \\
                & = & \frac{\Pr(B)}{\Pr(B)} \\
                & = & 1
\end{eqnarray*}
The Product Rule can be generalized to many events.
\begin{rul}[Product Rule, general case]
Let $A_1, A_2, \ldots, A_n$ be events.
\[
\Pr(A_1 \cap A_2 \cap \ldots \cap A_n) =
        \Pr(A_1) \Pr(A_2 \mid A_1) \Pr(A_3 \mid A_1 \cap A_2) \ldots
        \Pr(A_n \mid A_1 \cap \ldots \cap A_{n-1})
\]
\end{rul}
This generalization of the Product Rule can be proven from the special
case by induction on $n$, the number of events. We will not give a
proof here, however.



\section{Conditional Probability Examples}

This section contains five 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 the same four-step method that we used for the Monty Hall
problem:
\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 the Product Rule and
the four-step method that we applied to the Monty Hall problem.



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

The MIT computer science 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 $\frac{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 $\frac{2}{3}$ chance of winning the next game.  On the
other hand, if the team loses, then they have only a $\frac{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 $\Pr(A \mid B)$.



\subsubsection*{Step 3:  Compute Outcome Probabilities}

Next, we must assign a probability to each outcome.  As in the Monty
Hall problem, we initially assign probabilities to edges in the tree
diagram.  These probabilities are given explicitly in the problem
statement.  Specifically, The Halting Problem has a $\frac{1}{2}$
chance of winning the first game, so the two edges leaving the root
are both assigned probability $\frac{1}{2}$.  Other edges are labeled
$\frac{1}{3}$ or $\frac{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 the figure.

This method of computing outcome probabilities by multiplying edge
probabilities was introduced last lecture, but not 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
                \Pr(\mbox{win 2nd game} \mid \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
                \Pr(\mbox{lose 2nd} \mid \mbox{win 1st})
                \Pr(\mbox{lose 3nd} \mid
                \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{eqnarray*}
\Pr(A \mid B)   & = & \frac{\Pr(A \cap B)}{\Pr(B)} \\
                & = & \frac{\frac{1}{3} + \frac{1}{18}}
                           {\frac{1}{3} + \frac{1}{18} + \frac{1}{9}} \\
                & = & \frac{7}{9}
\end{eqnarray*}
The first line uses the Product Rule.  In the second line, we use the
fact that the probability of an event is the sum of the probabilities
of the outcomes it contains.  The last line is simplification.

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



\subsection{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.  Harder to think about is 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 $\Pr(B \mid A)$:
\begin{eqnarray*}
\Pr(B \mid A)   & = & \frac{\Pr(B \cap A)}{\Pr(A)} \\
                & = & \frac{\frac{1}{3} + \frac{1}{18}}
                           {\frac{1}{3} + \frac{1}{18} + \frac{1}{9}} \\
                & = & \frac{7}{9}
\end{eqnarray*}
The probability of The Halting Problem winning the first game, given
that they won the series is $\frac{7}{9}$.

This answer is suspicious!  In the preceding section, we showed that
$\Pr(A \mid B) = \frac{7}{9}$.  Could it be true that $\Pr(A \mid B) =
\Pr(B \mid 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}
  \Pr(A \given B) \Pr(B) = \Pr(A \cap B) =
  \Pr(B \cap A) = \Pr(B \given A) \Pr(A).
\end{displaymath}
Evidently, $\Pr(A \mid B) = \Pr(B \mid A)$ only when $\Pr(A) = \Pr(B)
\neq 0$.  This is true for the hockey problem, but only by
coincidence.  In general, $\Pr(A \mid B)$ and $\Pr(B \mid A)$ are
\emph{not} equal!



\subsection{A Problem with Two Coins}

We have two coins.  One coin is fair; that is, comes up heads with
probability $\frac{1}{2}$ and tails with probability $\frac{1}{2}$.
The other is a trick coin; it has heads on both sides, and so always
comes up heads.

Consider the following experiment.  We choose a coin at random; in
particular, we choose the fair coin with probability $\frac{1}{2}$.
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 a 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 $\Pr(A \mid 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 $\frac{1}{2}$.  If we choose the fair coin,
then head and tails each come up with probability $\frac{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{eqnarray*}
\Pr(A \mid B)   & = & \frac{\Pr(A \cap B)}{\Pr(B)} \\
                & = & \frac{\frac{1}{4}}{\frac{1}{4} + \frac{1}{2}} \\
                & = & \frac{1}{3}
\end{eqnarray*}
The first equation uses the Product Rule.  In the second line, we use
the fact that the probability of an event is the sum of the
probabilities of the outcomes it contains.  The final line is
simplification.  The probability that the fair coin was chosen, given
that the result of the flip was heads, is $\frac{1}{3}$.



\subsection{A Variant of the Two Coins Problem}

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!
We don't have enough information.

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 $\Pr(A \mid 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 $\Pr(A \mid B)$ as follows.
\begin{eqnarray*}
\Pr(A \mid 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
$\frac{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
$\frac{1}{2}$ chance that we have the fair coin!

In fact, maybe we were handed the fair coin with probability $p = 1$.
Then the above expression gives probability 1 that we have the fair
coin!  This makes sense; if we are given the fair coin with
probability 1, then the fact that we flipped 100 heads is irrelevant!

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
population as a whole?  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 Democratic!

Later we will see exactly what can be concluded from a poll.



\subsection{Medical Testing}

There is a deadly disease called $X$ that has infected 10\% of the
population.  There are no symptoms; victims just drop dead one day.
Fortunately, there is a test for the disease.  The test is not
perfect, however:
\begin{itemize}
\item If you have the disease, there is a 10\% chance
that the test will say you do not.  (These are called ``false negatives''.)
\item If you do not have disease, there is a 30\% chance that the test
will say you do.  (These are ``false positives''.)
\end{itemize}
A random person is tested for the disease.  If the test is positive,
then what is the probability that the person has the 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 person has disease $X$,
    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 person has the 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 $\Pr(A \mid B)$, the
probability that a person has disease $X$, 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*}
\Pr(A \mid B)   & = & \frac{\Pr(A \cap B)}{\Pr(B)} \\
                & = & \frac{0.09}{0.09 + 0.27} \\
                & = & \frac{1}{4}
\end{eqnarray*}
If you test positive, then there is only a 25\% chance that you have
the disease!

This answer is initially surprising, but makes sense on reflection.
There are two ways you could test positive.  First, you could be sick
and the test correct.  Second, you could be healthy and the test
incorrect.  The problem is that almost everyone is 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 person.  This event consists of two outcomes.  The person could
be sick and the test positive (probability $0.09$), or the person
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 $\frac{3}{4}$ of the
time.

But wait!  There is a simple way to make the test correct 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 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.




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

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?  No!  
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}{ccr}
  \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?

\subsection{The Law of Total Probability}

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

\begin{theorem}[Theorem of Total Probability]
Let $B_1, B_2, \ldots$ be disjoint events such that the union is the
entire sample space $S$.  Then for all events $A \subseteq S$,

\[
\Pr(A) = \sum_i \Pr(A \cap B_i)
\]
\end{theorem}

A more traditional form of this theorem uses conditional probability.

\begin{corollary}[Theorem of Total Probability]
Let $B_1, B_2, \ldots$ be disjoint events such that the union is the
entire sample space $S$.  Then for all events $A \subseteq S$,

\[
\Pr(A) = \sum_i \Pr(A \mid  B_i) \Pr(B_i)
\]
\end{corollary}

The theorem of total probability is easily proved, using the
definition of probability as a sum over point probabilities in the
sample space.

\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) &= &\Pr(C \mid R) \Pr(R) + \Pr(C \mid {\overline R})
\Pr({\overline R})\\
&= &(1/2)\cdot (1/5) +(1/10)\cdot(4/5)\\
&= &6/50
\end{eqnarray*}

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 car 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 \Pr[W \mid B_i] \Pr[B_i]\\
&=& \sum_i (1/3) \Pr[W \mid 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.

\subsubsection{Resolving the Paradox}

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

Suppose that there are only two departments, EE and CS, and consider
the experiment where we pick a random applicant.  Define the following
events:
\begin{itemize}
\item Let $F_A$ be the event that a female applicant is accepted.
\item Let $F_{EE}$ the event that the female applicant is applying to EE.
\item Let $F_{CS}$ the event that the female applicant is applying to CS.
\end{itemize}
Assume that no applicant applied to both departments.  That is, the
events $F_{EE}$ and $F_{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) &= & \Pr(F_A \mid F_{EE})\Pr(F_{EE})+\Pr(F_A \mid
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 events $M_A$, $M_{CS}$, and
$M_{EE}$ for the male applicants, and evaluate their overall
acceptance probability:
\begin{eqnarray*}
\Pr(M_A) &= & \Pr(M_A \mid M_{EE})\Pr(M_{EE})+\Pr(M_A \mid
M_{CS})\Pr(M_{CS})\\
&= &(1/1)\cdot(1/101) + (50/100)\cdot(100/101)\\
&= 51/101,
\end{eqnarray*}
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.


\subsection{On-Time Airlines}

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!


\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 $\frac{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 $\frac{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} = \frac{2}{3}$,
$p_{TH} = \frac{1}{3}$, and $p_{TT} = \frac{2}{3}$.  Substituting
these four values into the first equation gives $p = \frac{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 $\frac{2}{3}$
probability of winning!

\forstudents{

\section{Inclusion/Exclusion and Conditional Probability}

Our probability identities carry over to conditional probabilities; that
is, any law still holds if all probabilities are conditioned on the
same event.  This is because the conditional-probability version of
the identity is just the original applied to the new, restricted
probability space.  For example, the following identity is analogous
to the Inclusion-Exclusion formula for two sets, but all probabilities
are conditioned on event~$C$.
\[
\Pr(A \cup B \mid C) = \Pr(A \mid C) + \Pr(B \mid C) - \Pr(A \cap B \mid C)
\]


Be careful not to mix up events before and after the conditioning bar!
For example, the following is \emph{not} a consequence of the Sum Rule:
\[
\Pr(A \mid B \cup C) = \Pr(A \mid B) + \Pr(A \mid C)
        \quad \quad \quad (B \cap C = \emptyset)
\]
A counterexample is shown in Figure~\ref{fig:cx19}.  In this case,
$\Pr(A \mid B) = 1$, $\Pr(A \mid C) = 1$, and $\Pr(A \mid B \cup C) =
1$.  However, since $1 \neq 1 + 1$, the equation above does not hold.
This is a ``false identity''.  This seems clear now, but a following
example will test our resolve!
\begin{figure}
  \centerline{\includegraphics[height=1.5in]{figures/cx19}}
  \caption{This figure illustrates a case where the equation
    $\Pr(A \mid B \cup C) = \Pr(A \mid B) + \Pr(A \mid C)$ does not hold.}
  \label{fig:cx19}
\end{figure}

\subsection{A false analysis}

Here is a fallacious analysis of the discrimination lawsuit.  As
before, let's simplify the problem and express both arguments in terms
of conditional probabilities.  Suppose that there are only two
departments, EE and CS, and consider the experiment where we pick a
random male \emph{or female} applicant.  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{eqnarray*}
  \Pr(A \mid F_{EE}) & < & \Pr(A \mid M_{EE}) \\
  \Pr(A \mid F_{CS}) & < & \Pr(A \mid M_{CS})
\end{eqnarray*}
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{eqnarray*}
  \Pr(A \mid F_{EE} \cup F_{CS}) & > & \Pr(A \mid M_{EE} \cup M_{CS})
\end{eqnarray*}
It is easy to believe that these two positions are contradictory.  In
fact, we might even try to prove this by adding the plaintiff's two
inequalities and then arguing as follows:
\begin{eqnarray*}
  \Pr(A \mid F_{EE}) + \Pr(A \mid F_{CS}) & < &
  \Pr(A \mid M_{EE}) + \Pr(A \mid M_{CS}) \\
  \Rightarrow \quad \quad
  \Pr(A \mid F_{EE} \cup F_{CS}) & < &
  \Pr(A \mid M_{EE} \cup M_{CS}) \\
\end{eqnarray*}
The second line exactly contradicts the university's position!
However, there is a problem with this argument; the second inequality
follows from the first only if we accept the ``false identity'' from
the preceding section!  Therefore, this argument is invalid.

}

\end{document}









