5

Say I have a bag of 100 unique marbles. With replacement, I pick 10 marbles at a time, at random. How many times will I have to pick the marbles (10 marbles a pick) in order to have a 95% chance of having seen every unique marble at least once.

David
  • 51
  • The $10$ you pick each time are all distinct, I presume? That is, "with replacement" only refers to replacing the marbles after each pick of $10$, rather than after each individual marble? – ShreevatsaR Jul 19 '13 at 12:41

1 Answers1

4

Simulations show that you need 73 or 72 picks (probably this, $10^7$ turns give $p = 0.950612$) and I don't know any efficient method to calculate that exactly (of course, that doesn't mean there isn't one). 

irb(main):021:0> average(1000000) do g(100,10,73)? 1:0 end
=> 0.955118
irb(main):022:0> average(1000000) do g(100,10,72)? 1:0 end
=> 0.950215
irb(main):023:0> average(1000000) do g(100,10,71)? 1:0 end
=> 0.945348

If you want some formulas, then very rough estimate using Markov's inequality gives you $\frac{49.9}{1-0.95} \simeq 998$ times. With such a difference, you could as well assume that you replace each marble after picking it (that is you pick a marble and then replace it, and again a marble, and again replace it), and then this is called the coupon collector's problem.

The expected time to see all unique marbles is $n\mathcal{H}_n$, where $n$ is the number of marbles and $\mathcal{H}_n = \sum_{k=1}^{n} \frac{1}{k}$ is the $n$-th harmonic number. Using this estimate you can use the Markov's inequality

$$P(X \geq t) \leq \frac{\mathbb{E}X}{t}$$

to bound the necessary number of picks. With $n = 100$ we get

$$P(X \geq t) \leq \frac{100\mathcal{H}_{100}}{t}\leq5\%$$

that is, $0.05t \geq 100 \mathcal{H}_{100} \approx 518.737$, so $t \geq 10375$. Picking 10 at a time, you will have to pick 1038 times.

I hope this helps ;-)

dtldarek
  • 37,381
  • Strictly speaking, if you want to collect only $0.95n$ coupons instead of all $n$ of them, then the expected time to see them, rather than $nH_n = n(\frac1n +‌ \frac1{n-1} + \dots + \frac11)$, is $n(\frac1n + \frac1{n-1} +‌ \dots + \frac1{n-0.95n+1})$, which is $n(H_n - H_{0.05n})$. This is like $n(\log n - \log 0.05n) = n\log 20$, rather than $n \log n$. So while it's asymptotically very different ($\Theta(n)$ rather than $\Theta(n \log n)$), it probably doesn't matter for $n = 100$. – ShreevatsaR Jul 19 '13 at 18:30
  • @ShreevatsaR No, it's not like you are collecting 95% of coupons, you are collecting all of them, and moreover you want to be 95% sure you have all of them (therefore you need to wait a lot more than just the expected time of collecting all of them). – dtldarek Jul 19 '13 at 19:37
  • Oh sorry, I misread the question. You're right. (‌I was thinking of this similar question: http://math.stackexchange.com/questions/446631/number-of-draws-required-for-ensuring-90-of-different-colors-in-the-urn-with-la – ShreevatsaR Jul 20 '13 at 05:07
  • Could @dtldarek pls explain what does the random variable X represent in the markov inequality? – broccoli Jul 21 '13 at 17:07
  • @broccoli In this context it denotes the time required for collecting all the coupons. – dtldarek Jul 21 '13 at 18:33