
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%From Fall 1998 Final exam
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}[20] A box initially contains $n$ balls, all
colored black.  A ball is drawn from the box at random.  If the ball is
black, then a coin with probability, $p$, of coming up heads is flipped.
If the coin comes up heads, a white ball is put into the box; otherwise
the black ball is returned to the box.  If the drawn ball is white, then
it is returned to the box.  This process is repeated until the box
contains $n$ white balls.

Let $D_1$ be the number of balls drawn until the first white ball
is put into the box, and for $i>1$, let $D_i$ be the number of balls drawn
after the $i$th ball is put into the box until the $i+1$st ball is put
into the box.  Let $D \eqdef \sum_{i=1}^{k} D_i$ be the number of balls
drawn until the process ends with the box full of white balls.
What $\expect{D}$?

\solution{Suppose that the box contains $k$ white balls.  The
probability that a black ball is drawn and replaced by a white ball is
$\frac{n-k}{n} \cdot p$.  Therefore, the expected number of draws to
introduce one more white ball is $\frac{n}{p(n-k)}$.  By linearity
of expectation, the expected number of draws required to fill the box
with white balls is:

\begin{eqnarray*}
\sum_{k=0}^{n-1} \frac{n}{p(n-k)}
    & = &   \frac{n}{p} \cdot \sum_{k=0}^{n-1} \frac{1}{n-k} \\
    & = &   \frac{n}{p} \cdot \sum_{j=1}^n \frac{1}{j} \\
    & = &   \frac{nH_n}{p}
\end{eqnarray*}

The second step uses the substitution $j = n - k$.
}

\end{problem}








