\documentclass[12pt,twoside]{article}
\usepackage{light}

\newcommand{\mfigure}[3]{\bigskip\centerline{\resizebox{#1}{#2}{\includegraphics{#3}}}\bigskip}

\begin{document}

\lecture{Introduction to Probability}{April 14, 2005}

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

So probability is good stuff.

\section{Monty Hall}

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

%  FUTURE:
%  Include the other problem that Marilyn addressed in the same issue.

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

\vspace{1ex}

\hspace{3in} Craig. F. Whitaker

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

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

Yet this is is an elementary problem with an elementary solution.  Why
was there so much dispute?  Apparently, most people \textit{believe}
they have an intuitive grasp of probability.  (This is in stark
contrast to other branches of mathematics; few people believe they
have an intuitive ability to compute integrals or factor large
integers!)  Unfortunately, approximately 100\% of those people are
\textit{wrong}.  In fact, everyone who has studied probability at
length can name a half-dozen problems in which their intuition led
them astray--- often embarassingly so.

The way to avoid errors is to distrust informal arguments and rely
instead on a rigorous, systematic approach.  In short: intuition
\textit{bad}, formalism \textit{good}.  If you insist on relying on
intuition, then there are lots of compelling financial deals we'd love
to offer you!

\subsection{The Four-Step Method}

Every probability problem involves some sort of randomized experiment,
process, or game.  And each such problem involves two distinct
challenges:
%
\begin{enumerate}
\item How do we model the situation mathematically?
\item How do we solve the resulting mathematical problem?
\end{enumerate}
%
In this section, we introduce a four-step approach to questions of the
form, ``What is the probability that ----- ?''  In this approach, we
build a probabilistic model step-by-step, formalizing the original
question in terms of that model.  Remarkably, the structured thinking
that this approach imposes reduces many famously-confusing problems to
near triviality.  For example, as you'll see, the four-step method
cuts through the confusion surrounding the Monty Hall problem like a
Ginsu knife.  However, more complex probability questions may spin off
challenging counting, summing, and approximation problems--- which,
fortunately, you've already spent weeks learning how to solve!

\subsection{Clarifying the Problem}

Craig's original letter to Marilyn vos Savant is a bit vague, so we
must make some assumptions in order to have any hope of modeling the
game formally:
%
\begin{enumerate}

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

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

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

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

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

\subsection{Step 1:  Find the Sample Space}

Our first objective is to identify all the possible outcomes of the
experiment.  A typical experiment involves several randomly-determined
quantities.  For example, the Monty Hall game involves three such
quantities:
%
\begin{enumerate}
\item The door concealing the car.
\item The door initially chosen by the player.
\item The door that the host opens to reveal a goat.
\end{enumerate}
%
Every possible combination of these randomly-determined quantities is
called an \term{outcome}.  The set of all possible outcomes is called
the \term{sample space} for the experiment.

A \term{tree diagram} is a graphical tool that can help us work
through the four-step approach when the number of outcomes is not too
large or the problem is nicely structured.  In particular, we can use
a tree diagram to help understand the sample space of an experiment.
The first randomly-determined quantity in our experiment is the door
concealing the prize.  We represent this as a tree with three
branches:
%
\begin{center}
\mfigure{!}{3.5in}{monty1}
\end{center}
%
In this diagram, the doors are called $A$, $B$, and $C$ instead of 1,
2, and 3 because we'll be adding a lot of other numbers to the picture
later.  Now, for each possible location of the prize, the player could
initially chose any of the three doors.  We represent this by adding a
second layer to the tree:
%
\begin{center}
\mfigure{!}{3.5in}{monty2}
\end{center}
%
Finally, the host opens a door to reveal a goat.  The host
has either one choice or two, depending on the position of the car and
the door initially selected by the player.  For example, if the prize
is behind door A and the player picks door B, then the host must open
door C.  However, if the prize is behind door A and the player picks
door A, then the host could open either door B or door C.  All of
these possibilities are worked out in a third layer of the tree:
%
\begin{center}
\mfigure{!}{3.5in}{monty3}
\end{center}
%
Now let's relate this picture to the terms we introduced earlier: the
leaves of the tree represent \textit{outcomes} of the experiment, and
the set of all leaves represents the \textit{sample space}.  Thus, for
this experiment, the sample space consists of 12 outcomes.  For
reference, we've labeled each outcome with a triple of doors
indicating:
%
\[
(\text{door concealing prize}, \ \text{door initially chosen}, \ \text{door opened to reveal a goat})
\]
%
In these terms, the sample space is the set:
%
\[
S = \set{
\begin{array}{cccccc}
(A, A, B), & (A, A, C), & (A, B, C), & (A, C, B), & (B, A, C), & (B, B, A), \\
(B, B, C), & (B, C, A), & (C, A, B), & (C, B, A), & (C, C, A), & (C, C, B)
\end{array}}
\]
%
The tree diagram has a broader interpretation as well: we can regard
the whole experiment as ``walk'' from the root down to a leaf, where
the branch taken at each stage is randomly determined.  Keep this
interpretation in mind; we'll use it again later.

\subsection{Step 2: Define Events of Interest}

Our objective is to answer questions of the form ``What is the
probability that ----- ?'', where the horizontal line stands for some
phrase such as ``the player wins by switching'', ``the player
initially picked the door concealing the prize'', or ``the prize is
behind door C''.  Almost any such phrase can be modeled mathematically
as an \term{event}, which is defined to be a subset of the sample
space.

For example, the event that the prize is behind door $C$ is the set of
outcomes:
%
\[
\set{(C, A, B), (C, B, A), (C, C, A), (C, C, B)}
\]
%
The event that the player initially picked the door concealing the
prize is the set of outcomes:
%
\[
\set{(A, A, B), (A, A, C), (B, B, A), (B, B, C), (C, C, A), (C, C, B)}
\]
%
And what we're really after, the event that the player wins by
switching, is the set of outcomes:
%
\[
\set{(A, B, C), (A, C, B), (B, A, C), (B, C, A), (C, A, B), (C, B, A)}
\]
%
Let's annonate our tree diagram to indicate the outcomes in this
event.
%
\begin{center}
\mfigure{!}{3.5in}{monty4}
\end{center}
%
Notice that exactly half of the outcomes are marked, meaning that the
player wins by switching in half of all outcomes.  You might be
tempted to conclude that a player who switches wins with probability
$\frac{1}{2}$.  \textit{This is wrong.}  The reason is that these
outcomes are not all equally likely, as we'll see shortly.

\subsection{Step 3: Determine Outcome Probabilities}

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

Ultimately, outcome probabilities are determined by the phenomenon
we're modeling and thus are not quantities that we can derive
mathematically.  However, mathematics can help us compute the
probability of every outcome \textit{based on fewer and more
elementary modeling decisions.}  In particular, we'll break the task
of determining outcome probabilities into two stages.

\subsubsection{Step 3a: Assign Edge Probabilities}

First, we record a probability on each \textit{edge} of the tree
diagram.  These edge-probabilities are determined by the assumptions
we made at the outset: that the prize is equally likely to be behind
each door, that the player is equally likely to pick each door, and
that the host is equally likely to reveal each goat, if he has a
choice.  Notice that when the host has no choice regarding which door
to open, the single branch is assigned probability 1.
%
\begin{center}
\mfigure{!}{3.5in}{monty5}
\end{center}

\subsubsection{Step 3b: Compute Outcome Probabilities}

Our next job is to convert edge probabilities into outcome
probabilities.  This is a purely mechanical process: \textit{the
probability of an outcome is equal to the product of the
edge-probabilities on the path from the root to that outcome}.  For
example, the probability of the topmost outcome, $(A, A, B)$ is
$\frac{1}{3} \cdot \frac{1}{3} \cdot \frac{1}{2} = \frac{1}{18}$.

We'll justify this process formally next time.  In the meanwhile, here
is a nice informal justification to tide you over.  Remember that the
whole experiment can be regarded as a walk from the root of the tree
diagram down to a leaf, where the branch taken at each step is
randomly determined.  In particular, the probabilities on the edges
indicate how likely the walk is to proceed along each path.  For
example, a walk starting at the root in our example is equally likely
to go down each of the three top-level branches.

Now, how likely is such a walk to arrive at the topmost outcome, $(A,
A, B)$?  Well, there is a 1-in-3 chance that a walk would follow the
$A$-branch at the top level, a 1-in-3 chance it would continue along
the $A$-branch at the second level, and 1-in-2 chance it would follow
the $B$-branch at the third level.  Thus, it seems that about 1 walk
in 18 should arrive at the $(A, A, B)$ leaf, which is precisely the
probability we assign it.

Anyway, let's record all the outcome probabilities in our tree
diagram.
%
\begin{center}

\mfigure{!}{3.5in}{monty6}
\end{center}

Specifying the probability of each outcome amounts to defining a
function that maps each outcome to a probability.  This function is
usually called \textbf{Pr}.  In these terms, we've just determined
that:
%
\begin{align*}
\pr{A, A, B} & = \frac{1}{18} \\
\pr{A, A, C} & = \frac{1}{18} \\
\pr{A, B, C} & = \frac{1}{9} \\
               & \text{etc.}
\end{align*}
%
Earlier, we noted that the sum of all outcome probabilties must be 1
since exactly one outcome must occur.  We can now express this
symbolically:
%
\[
\sum_{x \in S} \pr{x} = 1
\]
%
In this equation, $S$ denotes the sample space.

Though $\Pr$ is an ordinary function, just like your old friends $f$
and $g$ from calculus, we will subject it to all sorts of horrible
notational abuses that $f$ and $g$ were mercifully spared.  Just for
starters, all of the following are common notations for the
probability of an outcome $x$:
%
\[
\begin{array}{ccccccccc}
& \pr{x} & \quad & \Pr(x) & \quad \Pr[x] & \quad & \Pr x & \quad & p(x)
\end{array}
\]
%
A sample space $S$ and a probability function $\Pr : S \to [0,1]$
together form a \term{probability space}.  Thus, a probability space
describes all possible outcomes of an experiment \textit{and} the
probability of each outcome.  A probability space is a complete
mathematical model of an experiment.

\subsection{Step 4: Compute Event Probabilities}

We now have a probability for each \textit{outcome}, but we want to
determine the probability of an \textit{event}.  We can bridge this
gap with a definition: \textit{the probability of an event is the sum
of the probabilities of the outcomes it contains}.  As a notational
matter, the probability of an event $E \subseteq S$ is written
$\pr{E}$.  Thus, our definition of the probability of an event can be
written:
%
\[
\pr{E} = \sum_{x \in E} \pr{x}
\]
%
For example, the probability of the event that the player wins by
switching is:
%
\begin{align*}
\pr{\text{switching wins}}
    & = \pr{A, B, C} + \pr{A, C, B} + \pr{B, A, C} + \\
    & \qquad \pr{B, C, A} + \pr{C, A, B} + \pr{C, B, A} \\
    & = \frac{1}{9} + \frac{1}{9} + \frac{1}{9} + 
        \frac{1}{9} + \frac{1}{9} + \frac{1}{9} \\
    & = \frac{2}{3}
\end{align*}
%
It seems Marilyn's answer is correct; a player who switches doors wins
the car with probability $2/3$!  In contrast, a player who stays with
his or her original door wins with probability $1/3$, since staying
wins if and only if switching loses.

We're done with the problem!  We didn't need any appeals to intuition
or ingenious analogies.  In fact, no mathematics more difficult than
adding and multiplying fractions was required.  The only hard part was
resisting the temptation to leap to an ``intuitively obvious'' answer.

\subsection{An Alternative Interpretation of the Monty Hall Problem}

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

\section{Strange Dice}

Let's play \textit{Strange Dice}!  The rules are simple.  There are
three dice, $A$, $B$, and $C$.  Not surprisingly, the dice are
numbered \textit{strangely}, as shown below:
%
\begin{center}
%\mfigure{!}{3.5in}{lec2-dice}
\mfigure{!}{2in}{dice}
\end{center}
%
The number on each concealed face is the same as the number on the
opposite, exposed face.  The rules are simple.  You pick one of the
three dice, and then I pick one of the two remainders.  We both roll
and the player with the higher number wins.

Which of the dice should you choose to maximize your chances of
winning?  Die $B$ is appealling, because it has a 9, the highest
number overall.  Then again, die $A$ has two relatively large numbers,
6 and 7.  But die $C$ has an 8 and no very small numbers at all.
Intuition gives no clear answer!

\subsection{Analysis of Strange Dice}

We can analyze Strange Dice using our standard, four-step method for
solving probability problems.  To fully understand the game, we need
to consider three different experiments, corresponding to the three
pairs of dice that could be pitted against one another.

\subsubsection{Die \emph{A} versus Die \emph{B}}

First, let's determine what happens when die $A$ is played against die
$B$.

\noindent \textit{Step 1: Find the sample space. } The sample space
for this experiment is worked out in the tree diagram show below.
(Actually, the whole probability space is worked out in this one
picture.  But pretend that each component sort of fades in---
nyyyrrroom!--- as you read about the corresponding step below.)
%
\begin{center}
%\mfigure{!}{4in}{lec2-diceAB}
\mfigure{!}{3in}{diceAB}
\end{center}
%
For this experiment, the sample space is a set of nine outcomes:
\[
S = \set{\ (2,1),\ (2,5),\ (2,9),\ (6,1),\ (6,5),\ (6,9),\ (7,1),\ (7,5),\ (7,9)\ }
\]

\noindent \textit{Step 2: Define events of interest. } We are
interested in the event that the number on die $A$ is greater than the
number on die $B$.  This event is a set of five outcomes:
%
\[
\set{\ (2,1),\ (6,1),\ (6,5),\ (7,1),\ (7,5)\ }
\]
%
These outcomes are marked $A$ in the tree diagram above.

\noindent \textit{Step 3: Determine outcome probabilities. } To find
outcome probabilities, we first assign probabilities to edges in the
tree diagram.  Each number on each die 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, which
means that every outcome has probability $1/9$.  These probabilities
are recorded on the right side of the tree diagram.

\noindent \textit{Step 4: Compute event probabilities. } The
probability of an event is the sum of the probabilities of the
outcomes in that event.  Therefore, the probability that die $A$ comes
up greater than die $B$ is:
%
\begin{align*}
\pr{A > B}
	& = \pr{2,1} + \pr{6,1} + \pr{6,5} + \pr{7,1} + \pr{7,5} \\
	& = \frac{1}{9} + \frac{1}{9} + \frac{1}{9} +
		\frac{1}{9} + \frac{1}{9} \\
	& = \frac{5}{9}
\end{align*}
%
Therefore, die $A$ beats die $B$ more than half of the time.  You had
better not choose die $B$ or else I'll pick die $A$ and have a
better-than-even chance of winning the game!

\subsubsection{Die \emph{B} versus Die \emph{C}}

Now suppose that die $B$ is played against die $C$.  The tree diagram
for this experiment is shown below.
%
\begin{center}
%\mfigure{!}{4in}{lec2-diceBC}
\mfigure{!}{3in}{diceBC}
\end{center}
%
The analysis is the same as before and leads to the conclusion that
die $B$ beats die $C$ with probability $5/9$ as well.  Therefore, you
had beter not choose die $C$; if you do, I'll pick die $B$ and most
likely win!

\subsubsection{Die \emph{C} versus Die \emph{A}}

We've seen that $A$ beats $B$ and $B$ beats $C$.  Apparently, die $A$
is the best and die $C$ is the worst.  The result of a confrontation
between $A$ and $C$ seems a forgone conclusion.  A tree diagram for
this final experiment is worked out below.
%
\begin{center}
%\mfigure{!}{4in}{lec2-diceCA}
\mfigure{!}{3in}{diceCA}
\end{center}
%
Surprisingly, die $C$ beats die $A$ with probability $5/9$!

In summary, die $A$ beats $B$, $B$ beats $C$, and $C$ beats $A$!
Evidently, there is a relation between the dice that is \textit{not
transitive}!  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!

\noindent \textbf{Challenge:} The dice can be renumbered so that $A$
beats $B$ and $B$ beats $C$, each with probability $2 / 3$, and $C$
still beats $A$ with probability $5 / 9$.  Can you find such a
numbering?
\end{document}
