5
$\begingroup$

In the situation of having a high entropy random number generator, that generates numbers in the range of 0 and 2,147,000,000.

If i have a list of 1,000,000 integer values, what are the chances that a random number will already be on my list?

2 Answers 2

5

One minus the probability that they are all different: $$1 - \left( 1- \frac{1}{n} \right) \left( 1- \frac{2}{n} \right) \cdots \left( 1- \frac{k-1}{n} \right),$$ where $n=2,147,000,001$ (since you include $0$) and $k=1,000,000.$

See the birthday problem for more information.

0

If the list is drawn with replacement, the chance that a given number (the new draw) is not in it is $$(1-\frac{1}{2147000001})^{1000000}$$ The birthday problem only comes up if you ask for the chance of a collision anywhere in the 1000001 numbers.