variant of coupon collector's problem - how many draws to cover p fraction of coupons

Question

I have a urn with balls of "M" distinct colors. I draw "N" times (with replacement) from the urn. Probability of encountering each ball in a draw = $\frac{1}{M}$. How many expected draws (and the corresponding distribution of draws) do I need to be I have drawn "p" fraction of the M colors ?

Answer 1

When $k$ colours have been drawn, the expected number of draws required to draw the next undrawn colour is $\frac M{M-k}$. You want the sum of these expectations from $k=0$ to $k=\lceil pM\rceil-1$, which is

\begin{eqnarray} \sum_{k=0}^{\lceil pM\rceil-1}\frac M{M-k} &=& M\left(\sum_{k=0}^{M-1}\frac1{M-k}-\sum_{\lceil pM\rceil}^{M-1}\frac1{M-k}\right) \\ &=& M\left(\sum_{j=1}^M\frac1j-\sum_{j=1}^{M-\lceil pM\rceil}\frac1j\right) \\ &=& M\left(H_M-H_{M-\lceil pM\rceil}\right) \\ &\approx& M\left(\gamma+\log M-\left(\gamma+\log\left(M-\lceil pM\rceil\right)\right)\right) \\ &=& M(\log M-\log(M-\lceil pM\rceil)) \\ &=& -M\log\left(1-\frac{\lceil pM\rceil}M\right) \\ &\approx& -M\log\left(1-p\right)\;. \end{eqnarray}

The approximations are not valid if $p$ is near $1$.