6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

Figure

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:

Figure

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – terrigenus Dec 24 '17 at 20:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.