[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?

  • 3
    $\begingroup$ 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$. $\endgroup$ – Dominik Jan 26 '17 at 17:54
  • $\begingroup$ @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? $\endgroup$ – Bohoo Feb 12 '17 at 11:19
  • 1
    $\begingroup$ You've changed $x$ and $n$ in your calculations. The correct value is very small. See Here. $\endgroup$ – Dominik Feb 12 '17 at 12:01
  • $\begingroup$ @Dominik: Thanks a lot! $\endgroup$ – Bohoo Feb 12 '17 at 13:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.