
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%From Fall 1998 Final exam
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{problem}[15]A box initially contains $n$ balls, all
colored black.  A ball is drawn from the box at random.
\begin{itemize}
\item If the drawn ball is black, then a biased 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.

\item If the drawn ball is white, then it is returned to the box.
\end{itemize}
This process is repeated until the box contains $n$ white balls.

\iffalse
\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 biased 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.
\fi

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-1)$st white ball is put into the box until the $i$th white ball is
put into the box.  Let $D \eqdef \sum_{i=1}^{n} D_i$ be the number of
balls drawn until the process ends with the box full of white balls.
Write a \textbf{closed form formula} in terms of the $n$th Harmonic
number, $H_n$, for $\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 $p \cdot
(n-k)/n$.  Taking the placement of a white ball into the box as a
``failure,'' we know the mean time to failure is $1/(p(n-k)/n) =
n/p(n-k)$.  That is, the expected number of draws to introduce one more
white ball is $n/p(n-k)$.  By linearity of expectation, the expected
number of draws required to fill the box with white balls is:
\begin{align*}
\sum_{k=0}^{n-1} \dfrac{n}{p(n-k)}
    & =    \dfrac{n}{p} \cdot \sum_{k=0}^{n-1} \dfrac{1}{n-k} \\
    & =    \dfrac{n}{p} \cdot \sum_{j=1}^n \dfrac{1}{j} & (j = n - k)\\
    & =    \dfrac{nH_n}{p}.
\end{align*}
}

\end{problem}








