\problemdata      
        {?} % latex-friendly label for the prob.
        {Probability-Expectation} % The topic(s) of the problem content.
        {?} % Source (if known)
        {F01, TU11-5} % Usage (list ones you are aware of).
        {Christos Kapoutsis, S02} % Last revision info (author, date).

\begin{problem}
\bparts

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

\ppart 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$.
}

\ppart 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$.
}

\eparts
\end{problem}