3

Will ask this as a practical example for one situation.

  • Let's say I have a range of numbers 1-100
  • I need 10 unique random numbers in that range
  • How many times do I need to generate a random number to be 99+% certain that I have generated 10 unique numbers.

The range and unique number count is arbitrary. The range could have been 1-1000 and the unique numbers required 27. I am looking for a way to calculate how many extra numbers more than the required minimum unique numbers I need to generate to be 99% certain. Obviously the greater the range and the smaller the unique count required, the less extra numbers required. An extreme case would be 10 random numbers out of an exillion. Am 99+% certain that I only need to generate 10. But if I was to generate 10 random numbers in the range 1-11, then I would probably need to generate over a hundred+ random numbers to be 99+% certain I have 10 unique values in a random order.

I already know how to get the probability of 10 unique numbers after generating N numbers with replacement. Solution is here: How do I calculate the probability of getting 10 unique members of a set given random selection with replacement?

edit (tried to clarify what I am searching for). Ideally I am looking for a formula with the following inputs: N (the number of unique numbers required), R (the range of numbers to choose from), P (the percentage of certainty) and the output, X, being the number of numbers to be generated to achieve the required degree of certainty.

Community
  • 1
NoCelery
  • 33
  • Do I understand the question correctly, that you just want to draw from a uniform distribution on your numbers and you keep drawing until you obtain 10 different numbers? If it is, then it sounds like a Coupon Collector's Problem. – Raskolnikov Aug 27 '16 at 09:02
  • The answer to your initial question is $13$, which gives a probability of about $99.737%$ while $12$ gives about $98.338%$ – Henry Aug 27 '16 at 09:58
  • Hi Raskolnikov and @Henry, thank you for the responses. I do not think I am smart enough to properly understand the Coupon Collector's problem but am not sure it is exactly the same as I am only looking for a subset of the range and to an arbitrary amount of certainty. Ideally I am looking for a formula with the following inputs: N (the number of unique numbers required), R (the range of numbers to choose from), P (the percentage of certainty) and the output, X, being the number of numbers to be generated to achieve the required degree of certainty. – NoCelery Aug 27 '16 at 10:55
  • Hi @Henry, may I ask what formula you used for your calculations ? – NoCelery Aug 27 '16 at 11:15
  • It looks like the birthday problem: https://en.m.wikipedia.org/wiki/Birthday_problem – N74 Aug 27 '16 at 12:38
  • Thanks @N74. While there are some interesting elements in the "Birthday Problem" I am not sure how to apply it to my problem and am not sure it is exactly the same. If you think the Birthday Problem applies, may you please show me how to apply it with my inputs to get "X" (see above). – NoCelery Aug 27 '16 at 12:48

1 Answers1

2

You can calculate probabilities with a recurrence where $$f(x,n,R)=\dfrac{(R-n+1)f(x-1,n-1,R)+nf(x-1,n,R) }{R}$$ starting at $f(0,0,R)=1$ and $f(x,0,R)=0$ and $f(0,n,R)=0$ for positive $x$ and $n$.

You could write $$f(x,n,R)=\dfrac{R!\left\{{x\atop n}\right\} }{(R-n)!\,R^x}$$ where $\left\{{x\atop n}\right\}$ is a Stirling number of the second kind.

You then want $X$ to be the minimum $x$ for which $$\sum_{n=0}^{N-1} f(x,n,R) \le 1-P.$$

For your examples with $P=0.99$, I believe the answers are:

  • $N=10, R=100$ give a minimum $X$ of $13$
  • $N=10, R=11$ give a minimum $X$ of $43$
  • $N=27, R=1000$ give a minimum $X$ of $29$

The general term for this problem as well as the birthday problem and the coupon collector's problem, is occupancy problems

Henry
  • 157,058
  • Wow! Thank you very much for the high level of detail @Henry. I do not fully understand all parts of the answer ... yet but am 99% :) certain it is appropriate for my needs. I have not done proper maths in over 20 years ... so it will take me bit of time to digest this. – NoCelery Aug 27 '16 at 13:28
  • An update @Henry. I managed to get it to work, but it turns out it is computationally very intensive (and slow) for large numbers so I can not apply it practically to determine x where the range is 1 million or more. Nonetheless, it was very interesting maths (and programming). – NoCelery Aug 29 '16 at 07:03