\problemdata      
        {probability-intro-7} % latex-friendly label for the prob.
        {total probability theorem} % The topic(s) of the problem content.
        {?} % Source (if known)
        {S02 cp9W} % Usage (list ones you are aware of).
        {Albert Meyer, S02} % Last revision info (author, date).

\begin{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.

\solution{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$.

\solution{
\iffalse

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/spring02/handouts/lectures/ln9.pdf}
{ln9}{intrans-dice}{special dice in Notes 9}.  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{problem}

