Number of draws required for ensuring 90% of different colors in the urn with large populations My problem is:
An urn contains $10000000$ ($10^7$) different colored balls, namely $K_1, K_2,\dots,K_n  (n=10^7)$ with $K_1=1000, K_2=1000,\dots,K_n=1000$. My question is:
How many balls do I need to extract to ensure to obtain $90\%$ ($1000000$ or $10^6$) of all the colors?
Many thanks in advance.
 A: The number of draws is a small fraction of the universe, so the usual coupon-collector solution will be quite accurate.  Note that obtaining $90\%$ of the colors requires $9 \cdot 10^6$, not $10^6$.  On average you need $1$ draw for the first color, $\frac {10^7}{10^7-1}$ for the second, $\frac {10^7}{10^7-2}$ and so on, but you cut off at $9 \cdot 10^6$.  Add these up:
$$\sum_{i=0}^{9\cdot 10^6-1}\frac{10^7}{10^7-i}=10^7\sum_{i=0}^{9\cdot 10^6-1}\frac 1{10^6+i}=10^7(H_{10^7}-H_{10^6})\approx 10^7(\log 10^7-\log 10^6)\approx 2.30\cdot 10^7$$
A: Let $C$ be the number of colors and $B$ the number of balls per color and let $P(t,k)$ denote the probability that in $t$ turns we have picked exactly $k$ colors. Then
\begin{align}
P(0,0) &= 1,\\
P(0,k) &= 0,\\
P(t,0) &= 0,\\
P(t,k) = \left(1-\frac{B(C-k)}{BC-t+1}\right)P(t-1, k) &+ \left(\frac{B(C-k+1)}{BC-t+1}\right)P(t-1,k-1).
\end{align}
Using the above recurrence I've calculated some numbers ($T$ being the time required to collect 90% of colors). 
\begin{array}{|c|c|c|c|} \hline
B & C & \quad\quad\mathbb{E}T\quad\quad & \text{coupon collector estimate} \\\hline
10^3 & 10^3 & 2295.45 & 2308 \\\hline
10^3 & 10^4 & 22994.9 & 23031 \\\hline
10^3 & 10^5 & 229989 & 230264 \\\hline
\end{array}
A series of simulations for different $C$-s suggest that the ratio $\frac{\mathbb{E}T}{C}$ is increasing in $C$ (which is not surprising) and tends to somewhere around $2.3$ (hard to tell, as the sequence converges slower and slower), given that and the fact that the coupon collector estimate is the upper bound, the error cannot be very big (i.e. I would accept Ross Millikan answer).
I hope this helps ;-)
