        \problemdata       % Takes 5 *mandatory* arguments
        {doritos}             % latex-friendly label for the prob.
        {expectation}  % The topic(s) of the problem content.
        {}               % Source (if known)
        {S02 cp11m-4} % Usage (list ones you are aware of).
        {Ashish, S02}        % Last revision info (author, date).



\begin{problem}
Each bag of Doritos contains a cool sticker.  There are $n$ different
kinds of sticker, and I want to collect at least one sticker of each
kind.  (Assume that sticker kinds in Dorito bags are uniformly random
and mutually independent.)

\begin{problemparts}
\problempart Suppose that I have already collected $k$ kinds of
sticker.  What is the expected number of additional bags of Doritos
that I must eat to collect one additional kind of sticker?

\solution{
The probability that I must eat $i$ or more bags is:
\begin{eqnarray*}
\lefteqn{\expect{\text{number of bags to get new kind}}}\\
        & = &   \sum_{i=0}^{\infty} \prob{\text{number of bags to get new kind} > i} \\
        & = &   \sum_{i=0}^{\infty} \prob{\text{number of old kinds in first $i$ bags}} \\
        & = &   \sum_{i=0}^{\infty} \left(\frac{k}{n} \right)^i \\
        & = &   \frac{n}{n-k}
\end{eqnarray*}

Another way of thinking is that the probability of getting a new
sticker in a bag is $(n-k)/n$, so what you want is the time until the
first bag is opened that contains a new sticker which is just mean
time to failure i.e. $1/p = n/(n-k)$.
}

\problempart What is the expected number of bags of Doritos that I
must eat to collect at least one sticker of each kind?

\solution{
We sum the expected number of bags to get the first kind,
the expected number to get the second kind, and so forth.
\begin{eqnarray*}
\lefteqn{\expect{\text{number of bags to get all kinds}}}\\
        & = &   \sum_{k=0}^{n-1} \frac{n}{n-k} \ = \   n \cdot
        \sum_{k=0}^{n-1} \frac{1}{n-k} \\
        & = &  n \cdot \sum_{j=1}^{n} \frac{1}{j} 
        \ = \   n H_n.
\end{eqnarray*}
}
\end{problemparts}
\end{problem}
