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

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

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

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

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

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

[tex]
10\cdot\Big(1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{10}\Big) \approx 29.29
[/tex]

Mensanator

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

CRGreathouse

Why would that preclude a fractional answer?

Mensanator

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:

[tex] In(n) +\gamma +1/2n -1/(12n^2)+ 1/(12n^4)- +-[/tex]

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

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.