%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (20 points)} 6.042 TA Alex Duran is teaching Theory Pig
a fun new game.  Theory Pig is very excited because he finally has a
friend who will ``play nice''.  Here is how the game works.  Alex
repeatedly flips a fair coin.  If the sequence $HTT$ comes up on three
consecutive throws, then the game is over and Theory Pig wins.
However, if the sequence $HHT$ comes up on three consecutive throws,
then the game is over and Alex wins.  Though the game seems completely
fair, Theory Pig is still a slightly suspicious of Alex because of an
earlier duct tape incident.

Find the probability that Theory Pig wins the game; that is, find the
probability that the sequence $HTT$ appears before the sequence $HHT$
in a sequence of fair coin tosses.

\solution{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$.  Therefore, 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, 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
Theory Pig's chance of winning the game.

There are at least two alternative approaches.  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.
}