I'm working on a PHP script which randomly determines a set of variables which would be 37 chose 10. What I'm attempting to determine is how many random tests would I need to do before I randomly selected all of the possible combinations.
So, for example. Let's say I wanted it to be 37 chose 2. The order is not important, but variables can't repeat. There should be 666 possible combinations. How many random times would my PHP script need to run before I could reasonably guarantee that I had tested each combination? What if this was 37 chose 10?
Not homework, I promise. It's for a personal project.
37 choose 10 is n = 37!/(27!.10!) or 348,330,136 ways, which is the absolute minimum number of trials required. The probability p of choosing one of these outcomes at random is 1/n or approximately 2.871x10^-9.
The probability of selecting any given outcome x times in N trials is P(x) = (N!/(x!.(N-x)!)).(p^x).((1-p)^(N-x)).
For N=n=1/p=348,330,136:
P(0) = (1-p)^N = 0.368 (missed selection; that is, the miss probability)
P(1+) = 1-P(0) = 0.632 (selection, including repeated selection; that is, the hit probability)
So the probability of misses and hits are 0.368 (about 1 in 3) and 0.632 (about 2 in 3) respectively for 348,330,136 trials. (Note that all probabilities herein are stated to 3 decimal places unless stated otherwise). This would probably be too low a hit rate for your requirements.
However, increasing N to one billion samples yields a P(0) miss probability of 0.057 (about 1 in 17) and a P(1) hit probability of 0.943. Further increasing N to ten billion samples yields a miss probability of 3.399x10^-13 (about 1 in 3 trillion) and a hit probability of 0.9999999999996601 to 16 decimal places, which is equal to 1 when expressed as 12 or fewer decimal places.
I'll let you work out the probabilities for N greater than n to achieve your desired miss probability P(0) = (1-p)^N. It makes things easier if you know that P(0; X billion samples) = P(0; 1 billion samples)^X although you should use values of p and P(0; 10^9) that haven't been truncated to 3 decimal places. (Proportional errors (deltaQ/Q) due to truncation scale as approximately X when raising a value to the power X. Truncation at 3 decimal places yields a proportional error of e=5.582x10^-5 in both p and 1-p. Raising to the power X increases the proportional error to X.e: that is, X times 5.582x10^-5.)
The value of p is the same for any N unless you change the value of n. Only N needs to be changed in the formula.
Someone please feel free to correct any errors that I've made.
ETA: So after that effort, all I get is tumbleweed? Ah well...
