\documentclass[12pt]{article}
\input{macros-course}

\askaboutsolutions

\begin{document}

%% TUTORIAL 10: Basic Probability, Monty Hall, Conditional Probability,
%% Baye's rule

\ifshowsolutions
  \tutsol{10}{November 8, 2001}{\stamp}
\else
  \tutprobn{10}{November 8, 2001}{\stamp}
\fi

\begin{problems}
%Spring 99 Tutorial 10, Problem 1

\problem Suppose the game {\em Let's Make A Deal} is changed
slightly. Instead of having 3 doors with 1 grand prize, in the new game
there are 4 doors with 2 grand prizes. The rule of the game remains the
same. Therefore the game now becomes:

\begin{quote}
At one stage of the game, a contestant is shown 4 doors. The contestant
knows that there are 2 grand prizes behind 2 of the doors and that there
are goats behind the 2 other doors. At the beginning, the contestant picks
a door. To build suspense, the assistant of the game then opens a {\em
different} door, revealing a goat. The contestant can then stick with his
original door or switch to another unopened door. He wins a prize only if
he now picks the door with the prize.
\end{quote}

In the new game, what is the probability of winning with the ``stick''
strategy? How about the ``switch'' strategy? Can you explain why the two
probabilities do not sum up to 1?

\solnospace{The player wins with a ``stick'' strategy iff he chooses the
``correct door'' in the first place. Therefore the probability of winning
with the ``stick'' strategy is $1/2$.

Our method for analyzing the ``switch'' strategy is based on (careful,
correct use of) conditional probabilities.  Since we have seen how faulty
conditional reasoning can seem OK in this kind of problem, let's first
illustrate and justify our method to calculate the probability of winning
with the ``switch'' strategy in the \textbf{original game} with 3 doors
and 1 prize.

\begin{figure}[htbp]
\centerline{\includegraphics[height=3.5in]{figures/monty2}}
\caption{This is a tree diagram for the \textbf{original} 3-door Monty
Hall problem.  Each of the 12 leaves of the tree represents an outcome.}
\label{fig:monty}
\end{figure}

Figure~\ref{fig:monty} shows the probability tree we developed for this
game.  We examine the branch in which the prize is located behind door 1.
The winning nodes in this part of the probability tree are $(1,2,3)$ and
$(1,3,2)$ with probabilities that sum up to
\[
\frac{1}{9} +
\frac{1}{9}=\frac{2}{9}.
\]
By symmetry, the same probability applies to the other two branches, and
so the total probability of winning is $3\cdot(2/9)=2/3$.

However we can find a shortcut to calculate these probabilities.
Notice that in the second level of the tree, we can distinguish
between two cases:

(a) The player picks the door that has the prize, \eg $(1,1),(2,2),
(3,3)$.

(b) The player picks the door that does not have the prize, \eg
$(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)$.

These are two disjoint events, and furthermore their union covers the
whole sample space.  Suppose we let $E_1$ be the event in (a).  The event
in (b) is then $\overline{E_1}$.  From the law of total probability
\[
\prob{E}=\prob{E|E_1}+\prob{E|\overline{E_1}},
\]
for every event $E$ in our game.

Let $E_2$ be the event that the player wins---in other words that the door
to which he switches has the prize behind it.  \iffalse Note that it
doesn't matter anymore whether the prize is in door 1,2 or 3.  That
information is not important anymore.\fi
Examining the leaves of the probability tree, we see
\begin{eqnarray*}
\pr{E_2}&=&\prcond{E_2}{E_1}\pr{E_1} + 
    \prcond{E_2}{\overline{E_1}}\pr{\overline{E_1}}\\
   &=& 0\cdot\frac{1}{3}+1\cdot\frac{2}{3} = \frac{2}{3}.
\end{eqnarray*}

So, instead of adding all the $W$ probabilities one by one,  we
group them according to whether $E_1$ occurs or not, and of course
our results match.

\iffalse
So, the fact that we condition on $E_1$ and $\overline{E_1}$ comes
after our observation that we can group all possible outcomes in the
probability tree in just these two cases. 
\fi

Returning to our original problem, for the case with 4 doors and 2
prizes we have:
\iffalse
%To calculate the probability of winning with a ``switch'' strategy, let
%$E_1$ be the event that ``the player chooses the correct door at his first
%chance''. Let $E_2$ be the event that ``the player switches to the correct
%door at his second chance''.
\fi
\begin{eqnarray*}
\pr{\text{winning with ``switch''
strategy}}&=&\prcond{E_2}{E_1}\pr{E_1}+\prcond{E_2}{\overline{E_1}}\pr{\overline{E_1}}\\
&=&\frac{1}{2}\cdot\frac{1}{2}+1\cdot\frac{1}{2} =\frac{3}{4}.
\end{eqnarray*}

This time the two probabilities do not need to sum up to 1 because they
are no longer disjoint events.  It is possible for both the ``switch'' and
the ``stick'' strategy to pick doors that both have a prize behind them,
because there are two prizes.  So the same outcome can be a win for both
strategies.}

%Spring 2000 Miniquiz 12
\problem
Suppose a game involves tossing a fair coin until a head first arises.
\bparts
\ppart
What is the probability that a head first arises on an
even-numbered throw?

\solnospace{
The probability that a head first arises on an even-numbered throw can be
easily broken into two cases based on the first flip.  Half the time, a
head comes up on the first flip and thus the first head does not appear on
an even toss.  The other half of the time, the first head will be on an
even toss only if it is on a odd toss in the remaining sequence of tosses.
Thus:
\begin{eqnarray*}
p & = & \frac{1}{2}(1 - p) \\
p & = & \frac{1}{2} - \frac{1}{2}p \\
\frac{3}{2}p & = & \frac{1}{2} \\
p & = & \frac{1}{3} 
\end{eqnarray*}
}

\ppart What is a probability space for this experiment?

\solnospace{One reasonable probability space has as outcomes the strings
of the form $\mathtt{T}^k\mathtt{H}$, where $\mathtt{T}^k$ is a string of
$k$ \texttt{T}'s.  We define
\[
\pr{\mathtt{T}^k\mathtt{H}} \eqdef (\frac{1}{2})^{k+1}.
\]

To verify that this is a probability space, we must check that the sum of
the outcome probabilities is 1, namely,
\[
\sum_{k = 0}^{\infty} (\frac{1}{2})^{k+1} = 1.
\]
This follows straightforwardly from our formula for the sum of an infinite
geometric series.}

\ppart Does your probability space model the possibility of flipping an
infinite sequence of Tails?  If so, what is the probability of this event,
and what would happen if you removed this event?  If not, how do you
justify leaving it out?

\solnospace{ The probability space above does not have an event
corresponding to flipping Tails forever.  Nevertheless, it is a legitimate
probability space according to the formal definitions.  We could also add
an outcome or outcomes corresponding to flipping forever, but since the
probabilities of the events that end when the first Head is flipped
already total 1, the total probability of any flip-forever outcomes must
be zero.

How do we select the ``right'' probability space in this case?  In fact,
could it be that both of these spaces or wrong?  There is no mathematical
way to settle this question.  The spaces described here are mathematically
well-formed probability spaces, and ``rightness'' or ``wrongness'' is not
meant in a mathematical sense but in an empirical (experimental) sense.
Namely, can we use it to predict the results of actual coin flipping?

This is actually a subtle, and philosophically controversial, question,
since there is no experimental observation that could prove the model was
wrong.  For example, if in some experiment we flipped 1000 Tails before
flipping a Head, we still can't say that this \emph{proves} we have chosen
the wrong probability space, because the observation of 1000 tails is
\emph{possible} in our model, just very unlikely.  In practice, if we saw
1000 Tails in row, we would reject the model.  }

\iffalse

\ppart Does our probabilistic model make sense because of the
algebra, or the algebra makes sense because of our model?

\solnospace{ The algebra makes sense because of our model: Probability
is a tool to model real experiments. If two people were sitting on a
table flipping a coin forever we never know whether they would keep
bringing tails forever in reality, but we can model their game using a
probability space.  Within this probability space we assign
probabilities that make sense to us. Instead of claiming (falsely)
that TTH has probability 1/2, we are more rational and say ``Since my
coin is fair for each throw then I better assign $(1/2)^3$. Therefore
the algebra makes sense after we define a probability space.  }
\fi

\eparts


%Spring 99 Tutorial 11, Problem 2
\problem

\bparts

\ppart Suppose you repeatedly flip a fair coin until you see the sequence
\texttt{HHT} or the sequence \texttt{TTH}.  What is the probability you
will see \texttt{HHT} first?

\hint Symmetry between Heads and Tails.

\solnospace{In this case the answer is $1/2$.  The proof is by a bijection
argument on the sample space.  Let $A$ denote the event that you see
\texttt{HHT} before \texttt{TTH}, and $B$ denote the event that you see
\texttt{TTH} before \texttt{HHT}.

We will define a bijection, $g$, between $A$ and $B$ so that the
probability of $g(w)$ is equal to the probability of $w$.  The bijection
is quite simple.  Given a sample point $w \in A$, define $g(w) = \bar{w}$,
where $\bar{w}$ is the outcome where every \texttt{H} is replaced by a
\texttt{T} and vice versa.  For example $g(\mathtt{HHT}) =
\overline{\mathtt{HHT}} = \mathtt{TTH}$.

To show that $g$ is a bijection, we first observe that $g:A \rightarrow
B$.  This follows from the fact that \texttt{HHT} precedes \texttt{TTH} in
$w$ iff $\overline{\mathtt{HHT}} = \mathtt{TTH}$ precedes
$\overline{\mathtt{TTH}} = \mathtt{HHT}$ in $\bar{w}$.  And $g$ is onto by
the same reasoning.  Since $g$ is clearly an injection, we can conclude
that it is a bijection.

Then we observe that $\prob{w} = \prob{g(w)}$ for any $w$.  This is because
$\prob{\mathtt{H}} = \prob{\mathtt{T}}$ and $g(w)$ has the same length as
$w$.  Hence,
\[
\prob{A} = \sum_{w \in A} \prob{w} = \sum_{w\in A} \prob{g(w)}
= \sum_{w' \in B} \prob{w'}  =  \prob{B}.
\]
The second equality is valid because $g$ preserves the probability, and
the third by the bijection property with $w' = g(w)$.  Note that the fact
that \texttt{H} and \texttt{T} are equally likely is critical in these
calculations; this analysis would fail for a biased coin.

Finally we have to show that $\prob{A \cup B} = 1$.  This follows from the
fact that the only way never to throw either pattern is to throw all
\texttt{H}'s or all \texttt{T}'s after the first toss, and we know that
the probability of there being an unbounded number of tosses of only H or
only T is zero.  That is, $\prob{\overline{A \cup B}} = 0$ and so $\prob{A
\cup B} = 1$.  Since $A$ and $B$ are disjoint, this means that $\prob{A} +
\prob{B} = 1$ and hence
\[
\prob{A} = \frac{1}{2}.
\]
}

\ppart What is the probability you see the sequence \texttt{HTT} before
you see the sequence \texttt{HHT}?
 
\hint Try to find the probability that \texttt{HHT} comes before
\texttt{HTT} conditioning on whether you first toss an \texttt{H} or a
\texttt{T}.  The answer is not $1/2$.

\solnospace{

\iffalse  Nikos, I can't make sense of this paragraph.

First, we intuitively see that HHT is more likely than HTT,
because the sequence HHTT has HHT right one toss before HTT
so the appearance of HTT depends in a way in the appearance
of HHT before it. The inverse does not hold, since throwing
HHT is independent of HTT coming before it.
\fi

Let $A$ be the event that \texttt{HTT} appears before \texttt{HHT}, and let
$p \eqdef \prob{A}$.

Suppose our first toss is \texttt{T}.  Since neither of our patterns
starts with \texttt{T}, the probability that $A$ will occur from this
point on is still $p$.  That is, $\prcond{A}{\mathtt{T}} = p$.

Suppose our first toss is \texttt{H}.  To find the probability that $A$
will now occur, that is, to find $q \eqdef \prcond{A}{\mathtt{H}}$, we
consider different cases based on the subsequent throws.

Suppose the next toss is \texttt{H}, that is, the first two tosses are
\texttt{HH}.  Then neither pattern appears if we continue flipping
\texttt{H}, and when we eventually toss a \texttt{T}, the pattern
\texttt{HHT} will then have appeared first.  So in this case, event $A$
will never occur.  That is $\prcond{A}{\mathtt{HH}} = 0$.

Suppose the first two tosses are \texttt{HT}.  If we toss a \texttt{T}
again, then we have tossed \texttt{HTT}, so event $A$ has occurred.
If we next toss an \texttt{H}, then we have tossed \texttt{HTH}.  But this
puts us in the same situation we were in after rolling an \texttt{H} on
the first toss.  That is, $\prcond{A}{\mathtt{HTH}} = q$.

Summarizing this we have:
\begin{align}
\pr{A} &=
\prcond{A}{\mathtt{T}}\pr{\mathtt{T}}+\prcond{A}{\mathtt{H}}\pr{\mathtt{H}}
& \text{(Law of Total Probability)}\\
p & = p\frac{1}{2} + q\frac{1}{2} & \text{so}\\
p & = q.\label{peq}
\end{align}

Continuing, we have
\begin{align}
\prcond{A}{\mathtt{H}} &=
\prcond{A}{\mathtt{HT}}\pr{\mathtt{T}}+\prcond{A}{\mathtt{HH}}\pr{\mathtt{H}} &
\text{(Law of Total Probability)}\\
q &= \prcond{A}{\mathtt{HT}}\frac{1}{2} + 0\cdot\frac{1}{2}\label{here}\\
\prcond{A}{\mathtt{HT}} & =
\prcond{A}{\mathtt{HTT}}\pr{\mathtt{T}}+\prcond{A}{\mathtt{HTH}}\pr{\mathtt{H}}
& \text{Law of Total Probability}\\
\prcond{A}{\mathtt{HT}} & = 1\cdot\frac{1}{2} + q\frac{1}{2} \label{there}\\
q & = (\frac{1}{2} + \frac{q}{2})\frac{1}{2} & \text{by~(\ref{here}) \&~(\ref{there})}\\
q & = \frac{1}{3}.
\end{align}

So \texttt{HTT} comes before \texttt{HHT} with probability $p=q =\cfrac{1}{3}$.

It is an amazing fact that these kind of events are another example of
\emph{intransitivity} of the kind we saw with some
\hyperref{http://theory.lcs.mit.edu/classes/6.042/fall01/lectures/l10.pdf}
{l10}{intrans-dice}{special dice in Notes 10}.  Namely, if you may pick
\emph{any} pattern of three tosses such as \texttt{HTT}, then I can pick a
pattern of three tosses such as \texttt{HHT}.  If we then bet on which
pattern will appear first in a series of tosses, the odds will be in my
favor.  In particular, even if you instead picked the ``better'' pattern
\texttt{HHT}, there is another pattern I can pick that has a more than
even chance of appearing before \texttt{HHT}.  So this intransitivity
phenomenon comes up for real---you could make money on it betting in a
bar---and not just for some contrived dice.}

\eparts


\end{problems}

\end{document}
