# Hard probability problem: How to calculate the the probability of having selected only < 70% of all marbles in a bag, given the following draw rules?

Imagine I have 100 marbles in a bag. Each marble is uniquely labeled. I want to draw 9 marbles out of that bag all at once. I call this a selection. Once I have draw 9 marbles, I put them back. I make 50 such selections (in other words I draw 9 marbles and put them back 50 times).

I need to know the probability of selecting no more than 70% of all marbles during this process. In my mind, this probability as a percentage should be 100% - the probability of selecting 70% or more of the marbles.

Let's solve this generalized Coupon Collector's problem generally, drawing $m=9$ out of $n=100$ balls for $r=50$ times.

If $E(i;r)$ is the event that exactly $i$ distinct balls have been seen after $r$ draws, then--conditional on this--the chance in the next draw of obtaining $k$ balls that haven't yet been seen is found by counting what proportion of the $\binom{n}{m}$ possible samples consist of $m-k$ balls that have been seen and $k$ balls that have yet to be seen. Any such sample is comprised of an $m-k$-subset of the $i$ balls that have been seen together with a $k$-subset of the $n-i$ unseen balls, whence

$$\Pr(k\mid E(i;r)) = \frac{\binom{i}{m-k}\binom{n-i}{k}}{\binom{n}{m}}.$$

By summing over the possible values $i=0, 1, \ldots, n$, each multiplied by $\Pr(E(i;r))$, we obtain the chance of having seen exactly $k$ distinct balls in $r+1$ draws.

This update rule, which begins by observing that $m$ distinct balls will be obtained in the first draw, is a simple calculation requiring at most $(m+1)(n+1)$ fast calculations for each successive draw, and thereby requires at most $O((r-1)(m+1)(n+1))$ effort and only $O(n)$ storage.

Here are the probability distributions for $r=50$ draws along with some milestones along the way.

We can track the chance of observing $70$ or fewer distinct balls along the way. It rapidly drops from $1$ down to almost $0$, so it's best to plot its logarithm:

After $50$ draws this chance is only $3.162808\times 10^{-51}$, in accord with your intuition.

• Sometimes when I see you guys explain these probability problems, it seems like magic. Thank you very much for both the explanation and the reference. – terrigenus Dec 24 '17 at 20:30