Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.