# Finding the probability of getting a complete set from N classes of objects in M draws [duplicate]

Let's say we have 5 kinds of marbles, 1000 of each, mixed up in a giant tub. I want to know how many I have to draw out (without replacement) before I can be 50/70/90% sure I have at least 1 of each type of marble.

I can write a script to compute every possibility in M draws for M=5 to 4001, and get the probability from that, but (my point is) I figure there must be a statistical distribution that handles this more directly. Is there a name for such a distribution?

Also, if the counts are not equal (i.e. 100 of type 1, 300 of type 2, ...), is there a distribution that handles that?

An asympotic approximation - considering that the number of balls is quite large.

We have $l$ types of balls, $n_i$ of each them for a total of $n_1 + \cdots +n_l=n$ (in the example, $l=5$, $n_i=1000$, $n=5000$). Let's call $x_i$ the number of balls of type $i$ that result selected in $k$ extractions. For large $n$, the $x_i$ can be approximated as independent Poisson variables with mean $\lambda_i = k \frac{ni}{n}$

We are interested in the probability that all them are greater than zero, say $P(k)$. In this approximation:

$$P(k) \approx \prod_{i=1}^l \left( 1- e^{-\lambda_i}\right) = \prod_{i=1}^l \left( 1- \exp\left(- k \frac{n_i}{n}\right)\right)$$

and if $n_i = n_1$ we have $$P(k)=\left( 1- \exp\left(- k \frac{n_1}{n}\right)\right)^l$$

or $$k = - \frac{n}{n_1} \log\left(1-P(k)^{1/l}\right)$$

In our example, this gives, for $P(k) =$ 0.5, 0.7, 0.9, the values $k \approx$ 10, 13, 19

• This is wonderful. I could not make the leap to Poisson random variables. How can you say the variables are independent, though? – drfloob Apr 19 '12 at 21:53
• @drfloob search for "poissonization", a useful device in urns-balls models. Basically, if you throw N balls into M urns, you have a multinomial distribution, with $\sum n_i = N$ and $E(n_i)=N/M$. It can be shown that if you consider instead the (different) distribution of $M$ iid Poisson with $\lambda =N/M$, this distribution conditioned on the event $\sum n_i = N$ is exactly equivalent to the previous multinomial. And, asymtotically, that event gets more probable (informally speaking), and hence both distributions are asymtotically equivalent. This have several generalizations. – leonbloy Apr 19 '12 at 22:58

I am unaware of a name for this distribution, but the probabilities are straightforward to work out. Not by computing all possible draws, though! (There are far too many.)

The technique is quite general, so let's broaden the problem statement. Suppose we have $n_i \gt 0$ marbles of color $j$, $j=1,2,\ldots,l$, for a total of $n=n_1+\cdots +n_l$ marbles. For any subset of these colors $J = \{j_1,\ldots,j_s\}$, what fraction of all simple random samples of size $k$ contain exactly these colors? The answer is immediate: it's the number of all simple random samples of size $k$ from a bag containing only marbles whose colors are in $J$, divided by the number of all simple random samples of size $k$ from the original bag:

$$f(J, k) = \binom{n_{j_1}+n_{j_2}+\cdots+n_{j_s}}{k} / \binom{n}{k}$$

By the Principle of Inclusion-Exclusion, the fraction of simple random samples of size $k$ without all $l$ colors equals

$$\sum_{\varnothing \ne J \subset \{1,\ldots,l\}}(-1)^{l-\vert J\vert}f(J,k).$$

The computational effort, properly coded, is $O(2^l)$--fine for small numbers of distinct colors--and just $O(l)$ when all the $n_i$ are equal, because all terms for $J$ of a given size will be equal and only sizes $1$ through $l$ need be considered. A Mathematica program that directly expresses the general formula is

h[x_, k_Integer] /; Total[x] >= k > 0 :=
With[{n = Total[x], l = Length[x]},
Sum[(-1)^(l - j) Binomial[m, k]/Binomial[n, k], {j, 1, l}, {m, Total /@ Subsets[x, {j}]}]
]


Using it, it takes 0.015 seconds (on one core) to find h[{1000,1000,1000,1000,1000}, k] for k from 5 through 34. Rounded, the values are

0.038, 0.115, 0.215, 0.323, 0.428,     0.523, 0.607, 0.679, 0.739, 0.789,
0.83,  0.863, 0.89,  0.912, 0.929,     0.943, 0.955, 0.964, 0.971, 0.977,
0.981, 0.985, 0.988, 0.991, 0.992,     0.994, 0.995, 0.996, 0.997, 0.998


Here is a plot of these values:

For instance, the chance that all five colors are obtained in the first five draws is $.038 = 3.8\%$ (more precisely, it's $0.038476...$). As a check, if the sampling were with replacement this chance wouldn't change much and it would be computed as $1 \times \frac{4}{5} \times \frac{3}{5} \times \frac{2}{5} \times \frac{1}{5} = 0.0384$.

By inspection, the answer to the question (concerning the 50%/70%/90% points) is $10, 13, 18$. For instance, $k=17$ draws have less than a 90% chance of exhibiting all five colors (the chance is $0.89$) while $k=18$ draws have at least a 90% chance (it's actually $0.912$).

• your work is very good, and does solve the underlying problem quite well. I appreciate your help immensely. leonboy gets the check because his answer is more appropriate for the question I asked. – drfloob Apr 19 '12 at 21:50
• OK, but please note that the answer is not "Poisson distribution"--that's merely an ingredient in the approximate calculation. – whuber Apr 19 '12 at 22:38
• sorry, I don't understand enough about how the approximation works yet. thank you for the clarification. – drfloob Apr 20 '12 at 3:25