M random numbers from 1,2, ,N

[jostpuur]

Suppose we have a random number generator which gives a random numbers from a set {1,2,3,...,N}, and any single number of these comes out with probability 1/N.

Then fix some number M > N, and take M random numbers out from the generator. What is the probability, that these M numbers include each one of the numbers 1,2,3,...,N at least once?

---

I know one person who buys some kind of candy where a small toy always comes with the candy. There is some number of different kind of toys out there, and this person became interested to know how many candy he/she should buy before getting them all. I found myself unable to answer it.

 

[Mensanator]

I know one person who buys some kind of candy where a small toy always comes with the candy. There is some number of different kind of toys out there, and this person became interested to know how many candy he/she should buy before getting them all. I found myself unable to answer it.

You would need to know the distribution of the toys. Are there more toy cars than toy boats? Obviously, if it's not uniform, you would have to buy a lot more to get one of each.

 

[jostpuur]

I told the background about toys and candy for sake of motivation, but in the end I'm interested in the mathematical problem which I outlined.

If a simple mathematical model for a real world problem is too difficult, then it doesn't make sense to seek for more complicated models either. It's better to solve models one step at a time.

 

[Mensanator]

Well, I can model how many numbers I would have to draw from a set of 10 to get at least 1 of each (a mean of 29.5).

 

[jostpuur]

Well, I can model how many numbers I would have to draw from a set of 10 to get at least 1 of each (a mean of 29.5).

How did you get this number 29.5?

 

[Hurkyl]

Your first question is easy to turn into balls and boxes:

We have M balls and N boxes, with M > N. We want to know

• How many ways are there to put the balls into the boxes
• How many ways are there to put the balls into the boxes such that each box has at least one ball

I claim the first one is easy. I think the second one can be transformed into an easy problem, but I'm having a mental block on the details.




Your second question is a famous problem -- the coupon collector's problem.

 

[jostpuur]

I see. So the collector's problem can be solved without solving the problem I described, although my problem would give one way of approaching the collector's problem.

 

[Mensanator]

How did you get this number 29.5?

By randomly selecting numbers in the range (0-9) and storing them in a dictionary. When the length of the dictionary reaches 10, there must be a least 1 of every value. At that point, the sum of the dictionary is the number of draws. On some runs, it might take only 17 draws to get all 10, other runs might take 45. I do 1000 such runs and take the average: 29.5.

 

[Mensanator]

Your first question is easy to turn into balls and boxes:

We have M balls and N boxes, with M > N. We want to know

• How many ways are there to put the balls into the boxes
• How many ways are there to put the balls into the boxes such that each box has at least one ball

I claim the first one is easy. I think the second one can be transformed into an easy problem, but I'm having a mental block on the details.




Your second question is a famous problem -- the coupon collector's problem.

The first one is simply M choose N.

The second one is simply (M-1) choose (N-1).

(This turns up in the Collatz Conjecture.)

 

[jostpuur]

By randomly selecting numbers in the range (0-9) and storing them in a dictionary. When the length of the dictionary reaches 10, there must be a least 1 of every value. At that point, the sum of the dictionary is the number of draws. On some runs, it might take only 17 draws to get all 10, other runs might take 45. I do 1000 such runs and take the average: 29.5.

After reading Hurkyl's link to the Wikipedia page, I would prefer a following calculation

$$10\cdot\Big(1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{10}\Big) \approx 29.29$$

 

[Mensanator]

After reading Hurkyl's link to the Wikipedia page, I would prefer a following calculation

$$10\cdot\Big(1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{10}\Big) \approx 29.29$$

You DO realize you can't get a fraction of a draw from a random number generator?

 

[CRGreathouse]

You DO realize you can't get a fraction of a draw from a random number generator?

Why would that preclude a fractional answer?

 

[Mensanator]

Why would that preclude a fractional answer?

I didn't say it would. But IF I don't have the formula at hand AND Wikipedia is not available, THEN I prefer my answer as there's nothing stopping me from obtaining it and it's good enough. The difference between 29.29 and 29.5 is just splitting hairs.

 

[robert Ihnot]

I would not see it as exactly splitting hairs.

Euler has a formula for the harmonic series http://en.wikipedia.org/wiki/Harmonic_number: [Broken]

$$In(n) +\gamma +1/2n -1/(12n^2)+ 1/(12n^4)- +-$$

Letting gamma be .5772 and dropping terms past the square factor gives about 29.29 after multiplication by 10.

It is rather useful to get a handle on the degree of error. I prefer such a calculation to a computer devised answer that does not tell us about the error involved.

 

[Mensanator]

I would not see it as exactly splitting hairs.

Euler has a formula for the harmonic series http://en.wikipedia.org/wiki/Harmonic_number: [Broken]

$$In(n) +\gamma +1/2n -1/(12n^2)+ 1/(12n^4)- +-$$

Letting gamma be .5772 and dropping terms past the square factor gives about 29.29 after multiplication by 10.

It is rather useful to get a handle on the degree of error. I prefer such a calculation to a computer devised answer that does not tell us about the error involved.

Like I said, that's fine IF you know Euler's formula. A computer devised answer is preferable to no answer.

 

[robert Ihnot]

My gosh! I must add that my TI-86 can sum up the 50 case IN FOUR SECONDS! giving 224.96.

As far as this 10 case, why plain arithmetic will do here: 1+.5+.3333+.2500 + .2000+.1667+.1429+.1250 +.1111+.1000 = 2.9290.

2.929x10 = 29.290. This can be summed in about 30 seconds. If very careful probably around 45 seconds.