# Basic Probability Question

• Nov 13th 2009, 10:11 AM
angel.white
Basic Probability Question
Hi, I'm analyzing how valid a solution is to a problem, and I've realized that it's correctness can't be guaranteed. I've translated it into a math problem to try and figure out how correct of a solution it is. But it's been a while since I've done any math, I was hoping someone could help me out.

MATH VERSION:
If there are a pool of 24 unique numbers
and I pull one at random and write it down if I haven't seen it before
then place it back in
and I do this 1000 times in total
how likely is it that I will have written down 24 numbers?

REAL VERSION:
A one line permutation generator receives an array with 4 functions, sorts them into a random order 1000 times, then keeps the unique sortings. I've ran it probably 10_000 times and always gotten the same results, and am debating whether I should keep trying to get it to fail.
• Nov 13th 2009, 11:12 AM
angel.white
Thanks, galactus, I don't think I was very clear, though. There are 24 numbers, they are drawn from 1000 times. How likely is it that all 24 will have been selected at some point during the 1000 drawings.
• Nov 13th 2009, 02:11 PM
awkward
Quote:

Originally Posted by angel.white
Hi, I'm analyzing how valid a solution is to a problem, and I've realized that it's correctness can't be guaranteed. I've translated it into a math problem to try and figure out how correct of a solution it is. But it's been a while since I've done any math, I was hoping someone could help me out.

MATH VERSION:
If there are a pool of 24 unique numbers
and I pull one at random and write it down if I haven't seen it before
then place it back in
and I do this 1000 times in total
how likely is it that I will have written down 24 numbers?

REAL VERSION:
A one line permutation generator receives an array with 4 functions, sorts them into a random order 1000 times, then keeps the unique sortings. I've ran it probably 10_000 times and always gotten the same results, and am debating whether I should keep trying to get it to fail.

This is equivalent to the "Coupon Collector's Problem". The general statement of the problem is that there are N distinct types of coupons and each time we obtain a coupon it is equally likely to be any one of the N, independent of prior selections. We would like to know the probability that we will have to collect more than n coupons to get a complete set.

The answer, taken from Ross, "A First Course in Probability, 7th edition", is

$\Pr(\text{more than n trials are needed}) = \sum_{i=1}^{N-1} \binom{N}{i} \left( \frac{N-i}{N} \right) ^n (-1)^{i+1}$

With your values (N=24, n=1000), this works out to be about $8 \times 10^{-18}$, or to put it another way, you will need about $10^{17}$ trials, on average, before you see an incomplete set.