5

I am building a website where an alphanumeric ID will be generated.

As of now, I have it randomly grabbing a number or letter from this data set:

ABCDEFGHIJKLMNOPQRSTUVWXYZ 0123456789

So there are 36 possibilities.

If my math is right, if I make the ID 4 digits/characters long, the odds of a duplicate would be:

1/36 * 1/36 * 1/36 * 1/36 which equals 1/1,679,616.

In a nutshell, I want to eliminate (within reason) the possibility of a duplicate ID being created, but the shorter the ID the better.

If I went with 4 digits and ended up creating 15,000 IDs (like 4T6H, GF29, etc.), what are the chances that two of them will be the exact same?

If I generated ONE, it's obviously 1 in 1,679,616 (i think). But wondering how the odds are affected if I generate 15,000 of them.

Any insight/corrections on my math would be greatly appreciated.

user3304303
  • 153
  • 2
    This is essentially the Birthday Problem, and the probability of at least one duplicate is $\approx 1 - e^{-(15000)^2 / 2 \cdot 36^4} > 1 - 10^{-29}$, so extremely likely. With $6$-character IDs and again choosing $15,000$, the odds improve to $< 0.06$, and with $7$-character IDs to $< 0.002$. https://en.wikipedia.org/wiki/Birthday_problem#Approximations – Travis Willse Apr 13 '17 at 16:03
  • The only thing that you can do is to store the IDs in a DB and discard duplicates. You will have duplicates for every length of your ID. – N74 Apr 13 '17 at 18:17

1 Answers1

3

If there are $n$ possible strings (in our case, $n = 36^4$) and we randomly choose a random string $m$ (in our case, $m = 15\,000$), then the probability that the random strings we choose are all distinct is

$$1 \cdot \left(1 - \frac{1}{n}\right) \left(1 - \frac{2}{n}\right) \cdots \left(1 - \frac{m - 1}{n}\right) = \frac{n!}{n^m (n - m)!} .$$ Because of the magnitude of $n$ and $m$, this is perhaps nontrivial to estimate directly, so we briefly describe an approximation method good enough for order-of-magnitude estimates in our case: For $k \ll n$ the Taylor expansion of $\exp x$ gives $$\exp \left(-\frac{k}{n}\right) \approx 1 - \frac{k}{n},$$ and we can approximate the left-hand side of the first display equation as $$\prod_{k = 0}^{m - 1} \exp\left(-\frac{k}{n}\right) = \exp \left(-\frac{1}{n}\sum_{k = 0}^{m - 1} k \right) = \exp \left[-\frac{(m - 1)(m - 2)}{2n}\right] .$$ For $m \gg 0$, this gives the approximation $$P \approx \exp\left(-\frac{m^2}{2 n}\right)$$ given in the comments.

For our values of $m, n$ this gives that the probability the strings are all different is $$P \approx 8.150 \cdot 10^{-30} .$$

This is reasonably close to the actual value, which one can evaluate with a CAS: $$\color{#bf0000}{\boxed{P \approx 6.700 \cdot 10^{-30}}} .$$

Using our approximation, we see that using $8$-character strings gives an estimated collision probability smaller than $10^{-4}$.

Community
  • 1
Travis Willse
  • 99,363