6

Suppose there is a bag with 100 marbles. And I can draw 5 marbles in one attempt. But after that draw I have to put the marbles back. In how many attempts do I have a 75% chance that I have drawn each marble at least once?

I wrote a brute force program that calculated this: 

Marbles = 100. DRAW 5 at a time. Performing 100000 runs.
Runs completed = 10000
Runs completed = 20000
Runs completed = 30000
Runs completed = 40000
Runs completed = 50000
Runs completed = 60000
Runs completed = 70000
Runs completed = 80000
Runs completed = 90000
Runs completed = 100000
For 75% confidence you need 115 draws.

But how can we mathematically arrive at the same answer?

peter.petrov
  • 12,568
Wes
  • 197

1 Answers1

1

I am not sure if the following argument does not have a flaw (dependence/independence worries mainly at the last step) but here is the idea:

  1. When you perform a single draw of 5 marbles the probability that a fixed marble A shows up is: $ p = {99 \choose 4} / {100 \choose 5} = 5/100$. Why? Well, we have $100 \choose 5$ 5-element subsets in total. Marble A is a member of $99 \choose 4$ of these subsets. Hence this probability value.

  2. So when you perform a single draw of 5 marbles the probability that marble A does not show up is: $ 1-p = 95 / 100$

  3. Different draws are independent obviously. So the after N draws the probability that marble A does not show up is: $(1-p)^N$

  4. $\Rightarrow$ After N draws the probability that marble A shows up is: $1 - (1-p)^N$

  5. This last step I am not quite sure about... because I am not sure if I can multiply these probabilities (not sure if these events here are independent, my intuition tells me they are but somehow I am not fully convinced)... Anyway, the argument here goes like this. So now since we have 100 marbles (not just marble A) the probability that after N draws all of them show up is simply the product: $p_N = (1 - (1-p)^N)^{100}$

I put this formula into a computer program and I see that:
$p_N \ge 0.75$ when $N \ge 115$.

How do we find the value $115$ mathematically? Well, by solving this inequality

$(1 - (1-p)^N)^{100} \ge 0.75$ for $N$.

We solve it and we get:

$N \ge log_{\frac{95}{100}}(1 - 0.75^{0.01}) \approx 114.1 $

Since N is an integer, we get $N \ge 115 $

I was able to empirically confirm this numeric result.
So now I am slightly more convinced that my argument in the last step is OK.

peter.petrov
  • 12,568
  • I would be glad if someone confirms or rejects this. – peter.petrov Apr 07 '20 at 19:15
  • When you draw M marbles from a bag of N, the probability that you get a specific marble is simply M/N - unclear where you got that probability in step 1. – Nuclear Hoagie Apr 07 '20 at 19:54
  • @NuclearWang Thanks, you helped me to find a small mistake here. It is $99 \choose 4$, not $100 \choose 4$ – peter.petrov Apr 07 '20 at 20:14
  • The events in the last step are not independent though: the fact that a marble shows up reduces the probability that other ones did. – Raoul Apr 07 '20 at 20:43
  • @Raoul But why? In each single draw, when we draw the 5 marbles don't we draw them at once/simultaneously? See also this question which I asked here: https://math.stackexchange.com/questions/3614613/lottery-scenario-independent-events-or-not – peter.petrov Apr 07 '20 at 20:46
  • (coming from the other question) Your steps are not "actually correct". However, because you require an integer number of trials $N \geq 114.1$, that rounding effect could be sufficient to "make the numerical answer correct". There could be cases, say you calculate that $N \geq 114.99$, then $N=115$ isn't the actual answer, but $N=116$ instead. – Calvin Lin Apr 07 '20 at 21:19
  • @CalvinLin Yeah, I realized all that, thanks. Even here - I am not sure what my exact error value is... If the actual answer is 113.8 and not 114.1, then the integer answer would be 114 and not 115. So how do I know :) ? Thanks anyways, it was a nice try from my side. I just had that intuition that in 5. something is not quite right, but also that these events are "almost independent". – peter.petrov Apr 07 '20 at 21:25
  • Thanks @peter.petrov! I tested your formula with the results of my brute force simulation program and the results always match with a small margin of error. So your logic appears to be very sound to me!

    Brute force results - Marbles 1000, draw 40, N=200 Marbles 2000, draw 70 , N=249 Marbles 3000, draw 20, N=1383 (your formula gives 1384) Marbles 4000, draw 137, N=276 (your formula gives 274)

    Note: I only used 10,000 runs in the above simulations, so the results are likely to be slightly inaccurate.

     – Wes Apr 07 '20 at 21:43