# Random numbers generator and collision probability

[I don’t know how to properly write the notation, so any help is appreciated.]

There is a device that generates random integer numbers. The number of possible values that it can generate is x. For ex., if a device can generate any number between 4221 and 5220, inclusive, we say that x=1000.

If the device generates a number that it already generated in the past, we have a “collision”.

Given x, what is the probability for a collision after generating n numbers?

• This is essentially the birthday probnlem, only with $x$ days instead of $365$ en.wikipedia.org/wiki/Birthday_problem As written in the article, the probability is approximately $1 - \exp(-n^2/(2x))$, if $n$ is small compared to $x$. – Dominik Jan 26 '17 at 17:54
• @Dominik: Thanks for your answer. I try to calculate where x=32^11, and n=1000. I pasted the text 1 - e(-(32^11)^2 ÷ 2000) to google scientific calculator, and it gives me a very big number, with a lowercase e. It also have EXP, E and e, so I'm confused. Can you explain to me which text should I paste to the calculator? – Bohoo Feb 12 '17 at 11:19
• You've changed $x$ and $n$ in your calculations. The correct value is very small. See Here. – Dominik Feb 12 '17 at 12:01
• @Dominik: Thanks a lot! – Bohoo Feb 12 '17 at 13:39