

\problemdata     
{S01-PS10-8}           
{expectation, MTTF}              
{} 		
{S01-PS10}
{S01 Karger}



\begin{problem}


 %{\bf (15 points)} 
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{ We can view this as a mean time to failure problem
  where ``failure'' is the same thing as getting a kind of sticker
  that is not already in the bag. Using the standard approach from the
  lecture notes,
  \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{only old kinds in first $i$ bags}} \\
    & = &   \sum_{i=0}^{\infty} \left(\frac{k}{n} \right)^i \\
    & = &   \frac{n}{n-k}
\end{eqnarray*}
}

\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.
  (This is possible because expectation is a linear operator.)
  \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}
