\problemdata                                                             
        {Flipping coins} % latex-friendly label for the prob.
        {Expectation} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S01 Tutorial 12, 3} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
\begin{problemparts}

\problempart Suppose we flip a fair coin until two heads in a row come up.  What
is the expected number, $F$, of flips we perform?  \hint Let
$F_{\text{T}}$ be the expected number of further flips until two heads
comes up, given that the previous flip was T, and likewise let
$F_{\text{H}}$ be the expected number of further flips until two heads
comes up given that the previous flip was H.  Argue that $F_{\text{T}}$
will equal 1 plus the average of $F_{\text{T}}$ and $F_{\text{H}}$.

\solution{
$F=F_{\text{T}}$, since the initial condition has no chance
of achieving two heads on the first flip and is thus the same as if the
previous flip had been tails. 

To calculate the expected number of flips, we take $1$ for the first 
flip and then consider the two equally-likely outcomes: the first flip
is tails, or the first flip is heads. The remaining flips we can expect
are simply $F_{\text{T}}$ and $F_{\text{H}}$, respectively.
This gives us a total expectation of:
\[
F_{\text{T}} = 1 + \frac{1}{2}F_{\text{T}} + \frac{1}{2}F_{\text{H}}
\]
If the previous flip was heads, we get a similar calculation. The biggest
difference is that if the first flip is heads, we have no more flips
beyond the current one (we are done).
\[
F_{\text{H}} = 1 + \frac{1}{2}F_{\text{T}}+ \frac{1}{2}(0)
\]
Solving for $F_{\text{T}}$ (by substitution) yields $F=6$.

This can also be solved using a single equation formed by examining
that cases for the first and second flips, but it is not as clean.

%Clearly $F=F_{\text{T}}$.  Assuming the hint
%\[
%F_{\text{T}} = 1 + \frac{F_{\text{T}}+ F_{\text{H}}}{2}.
%\]
%Similarly,
%\[
%F_{\text{H}} = 1 + \frac{F_{\text{T}}+ 0}{2}.
%\]
%Solving for $F_{\text{T}}$ yields $F=6$.

}

\problempart Suppose we flip a fair coin until a head followed by a tail come
up.  What is the expected number, $G$, of flips we perform?

\solution{
Clearly $G=G_{\text{T}}$.  As above
\begin{eqnarray*}
G_{\text{T}} &=& 1 + \frac{G_{\text{T}}+ G_{\text{H}}}{2},\\
G_{\text{H}} &=& 1 + \frac{0+G_{\text{H}}}{2}.
\end{eqnarray*}
So $G=G_{\text{T}}=4$.
}

\problempart Suppose we now play a game: flip a fair coin until either HH or HT
first occurs.  You win if HT comes up first, lose if HH comes up first.
What odds should you offer an opponent to make this a fair game?

\solution{
Even money odds.  Although the expected time for HH is larger
than for HT, the game of waiting for one or the other to come up first is
fair!

To prove this, let W be the probability of winning.  Clearly,
\[
W = (1/2)\prob{W \mid \text{first roll is }T} + (1/2)\prob{W \mid \text{first
roll is }
H} = (1/2)W + (1/2)(1/2)
\]
so $W = 1/2$.
}
\end{problemparts}
\end{problem}
                                 