1

My problem is:

An urn contains $10000000$ ($10^7$) different colored balls, namely $K_1, K_2,\dots,K_n (n=10^7)$ with $K_1=1000, K_2=1000,\dots,K_n=1000$. My question is:

How many balls do I need to extract to ensure to obtain $90\%$ ($1000000$ or $10^6$) of all the colors?

Many thanks in advance.

Danny Bennett
  • 31
  • Same as his other question? – Calvin Lin Jul 18 '13 at 15:17
  • As my comment on the other question, I think they are different in the sense that one question asks the probability of getting 90% of all colors once a fixed number of balls have been drawn, whereas in this case I would like to know what is the number of draws required to exactly/approximately (not sure which one is possible/easier to calculate) obtain 90% of all the colrs – Danny Bennett Jul 18 '13 at 15:29
  • Please do not post a question more than once. – robjohn Jul 18 '13 at 22:24
  • @robjohn, in which way they are identical? – Danny Bennett Jul 19 '13 at 11:40
  • This is not a duplicate of the other question: that one asks about the probability of drawing $90%$ of the colours after a given number of trials, this is about the number of trials needed until we've seen $90%$ of the colours. – ShreevatsaR Jul 19 '13 at 12:48
  • @ShreevatsaR: they both ask for the relation between the number of draws and the chance of getting 90% of all the colors. – robjohn Jul 19 '13 at 13:47
  • @robjohn:‌ They are related questions surely, but the answers and even the techniques required to answer them may be (and probably are) substantially different. In particular I don't see how to use an answer to that question to answer this question, do you? If a question is closed as a duplicate of the other, I'd imagine that it means an answer can be found in the other — that doesn't seem to be the case here. – ShreevatsaR Jul 19 '13 at 18:03

2 Answers2

2

The number of draws is a small fraction of the universe, so the usual coupon-collector solution will be quite accurate. Note that obtaining $90\%$ of the colors requires $9 \cdot 10^6$, not $10^6$. On average you need $1$ draw for the first color, $\frac {10^7}{10^7-1}$ for the second, $\frac {10^7}{10^7-2}$ and so on, but you cut off at $9 \cdot 10^6$. Add these up: $$\sum_{i=0}^{9\cdot 10^6-1}\frac{10^7}{10^7-i}=10^7\sum_{i=0}^{9\cdot 10^6-1}\frac 1{10^6+i}=10^7(H_{10^7}-H_{10^6})\approx 10^7(\log 10^7-\log 10^6)\approx 2.30\cdot 10^7$$

Ross Millikan
  • 374,822
  • Ross, your answer seems to me far too generous. Basically you are saying that if I have 10 to the 7th different colored balls, each represented 1000 times, all I have to do is to pick 2.3 balls of each color on average to get 90% of all the colors? I really cant see that happen at all. Is it because of the large approximation you used? Any chance to use a different method to get some more sensible result? – Danny Bennett Jul 19 '13 at 10:52
  • I believe this result-what do you think is wrong with it? Assuming the colors act independently, the distribution of the number of a color is Poisson. The chance of getting zero in a Poisson distribution of mean $2.3$ is $\exp(-2.3) \approx 0.100$, which confirms the calculation. – Ross Millikan Jul 19 '13 at 13:01
  • Hi Ross, I think that I could believe this number maybe if I had 1 ball of each color rather than 1000 of each, in which case the coupon's collector approach will work. Do you see my point? – Danny Bennett Jul 22 '13 at 08:59
  • I would like to rephrase my last comment. Does your answer takes into account the fact the there are 1000 balls for each color rather than one. If so, where is this reflected in your equation (which appears to be the coupon collector case, comparable to large number of balls, but all unique colors rather than 1000 of each). If not, is there a way to take in account the fact that each color is represented 1000 times to get a more accurate answer? Many thanks in advance – Danny Bennett Jul 22 '13 at 09:10
  • My calculation assumes there are lots of balls of each color. If there were just one, you couldn't draw 2.3 times the number of colors, as you would run out of balls after 1 time and be guaranteed to have all the colors. It ignores that once you have drawn one ball of a given color, that color is less likely (by $\frac {999}{1000}$). This is a very small correction and would reduce the number of balls to likely have $90%$ of the colors. – Ross Millikan Jul 22 '13 at 14:00
  • I thought that you can draw 2.3 times each balls as you are approximating to a multinomial using "with replacement"? Sorry for the insistance but I really need to be sure the numbers are correct for my experiments. Does it not seems strange to you that drawing only 2.3 balls of each color, where there are 1000 of each color, could give about 90% of all colors? Many thanks in advance – Danny Bennett Jul 23 '13 at 08:18
  • No, it doesn't seem strange to me at all. I find the check in my first comment convincing. I am simulating with replacement, but with 1000 of each color it doesn't matter much. Try a simulation with 1000 each of 100 colors drawing 230. See how often you get at least 90 colors. That should run very quickly. – Ross Millikan Jul 23 '13 at 13:23
  • Hi Ross, simulation sounds like the best idea, that should definetly convince me (I guess you meant 2300 rather than 230?). Do you have an R script for the simulation by any chance (I dont know how to write it unfortunately). If so my email is [email protected]. Many thanks for all your help and patience! – Danny Bennett Jul 23 '13 at 14:21
  • Yes, I meant 2300. I don't know anything about R. My language of choice is Python these days. – Ross Millikan Jul 23 '13 at 14:39
1

Let $C$ be the number of colors and $B$ the number of balls per color and let $P(t,k)$ denote the probability that in $t$ turns we have picked exactly $k$ colors. Then

\begin{align} P(0,0) &= 1,\\ P(0,k) &= 0,\\ P(t,0) &= 0,\\ P(t,k) = \left(1-\frac{B(C-k)}{BC-t+1}\right)P(t-1, k) &+ \left(\frac{B(C-k+1)}{BC-t+1}\right)P(t-1,k-1). \end{align}

Using the above recurrence I've calculated some numbers ($T$ being the time required to collect 90% of colors).

\begin{array}{|c|c|c|c|} \hline B & C & \quad\quad\mathbb{E}T\quad\quad & \text{coupon collector estimate} \\\hline 10^3 & 10^3 & 2295.45 & 2308 \\\hline 10^3 & 10^4 & 22994.9 & 23031 \\\hline 10^3 & 10^5 & 229989 & 230264 \\\hline \end{array}

A series of simulations for different $C$-s suggest that the ratio $\frac{\mathbb{E}T}{C}$ is increasing in $C$ (which is not surprising) and tends to somewhere around $2.3$ (hard to tell, as the sequence converges slower and slower), given that and the fact that the coupon collector estimate is the upper bound, the error cannot be very big (i.e. I would accept Ross Millikan answer).

I hope this helps ;-)

dtldarek
  • 37,381