Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|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|cite|improve this answer

Your Answer


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.