\iffalse
\problemdata       % Takes 5 *mandatory* arguments
  {walds-2}                 % latex-friendly label for the prob.
  {Wald's Theorem}  % The topic(s) of the problem content.
  {}                       % Source (if known)
  {S99 Fin, F00 ps11-8}    % Usage (list ones you are aware of).
  {Nick Matsakis, S02}     % Last revision info (author, date).
\fi

\begin{problem}[15]
Suppose successive digits from zero to nine are generated independently
until the four digit sequence \textbf{9999} appears.  What is the expected
number of digits generated?  Briefly explain your answer.

\hint Parse the sequence into consecutive ``tries to get 9999'', where
a ``try'' is either a single digit other than 9, or a 9 followed by a
single digit other than 9, etc.  For example, the sequence
92349982999769999 parses into eight tries:
\[
/92/3/4/998/2/9997/6/9999/.
\]

\solution{11110.

By Wald's Theorem, the expected number is the mean time to a
successful try, namely $10^4$, times the expected length of a try.
Notice that a try is of length four iff it begins with three nines, so
the probability of a length four try is $1/10^3$.  That means the
expected length of a try is
\[
1 \cdot \frac{9}{10} + 2 \cdot \frac{1}{10}\frac{9}{10} + 3 \cdot
(\frac{1}{10})^2\frac{9}{10} + 4 \cdot (\frac{1}{10})^3
 =  (900 + 180 + 27 + 4)/1000 = 1111/1000
\]
Thus on average, we will have to read 11110 digits in order to see
``9999''.}
\end{problem}
