2
$\begingroup$

I have an algorithm that generates a random 8 digit, base 36 number with uniform distribution. Thus, this algorithm can generate $36^8$ unique numbers.

I run my algorithm 10,000 times, and write down the result on a large piece of paper. At the end of doing this, what is the probability of the same number being written down twice on my piece of paper?


This looks to me like an application of the birthday problem. Therefore, the probability of there being a collision on my piece of paper should be:

$$1 - \frac{(36^8)!}{(36^8)^{10000}(36^8-10000)!}$$

However, computing $(36^8)^{10000}$ is computationally difficult. Is there an alternative way to compute this probability with high accuracy?

$\endgroup$
2
  • $\begingroup$ With $n=36^8$, you can rewrite the fraction as $$\frac{n}{n}\cdot\frac{n-1}{n}\cdots\frac{n-9999}{n}\cdot$$ With this and Maxima, I find that your probability is $$1.77215913956941117517... \cdot 10^{-5}$$ $\endgroup$ Aug 27, 2014 at 18:54
  • $\begingroup$ It can be approximated with a Poisson distribution. $\endgroup$
    – djechlin
    Aug 27, 2014 at 19:11

2 Answers 2

2
$\begingroup$

As Jean-Claude Arbaut pointed out in a comment,

$$\frac{n!}{n^{10000}{(n-10000)}!} = \frac{n}{n}\cdot\frac{n-1}{n}\cdots\frac{n-9999}{n}$$

If we make the approximations $n(n-9999) \approx (n-1)(n-9998) \approx \ldots \approx(n-4999.5)^2$, we get

$$\frac{n!}{n^{10000}{(n-10000)}!} \approx \left(1-\frac{4999.5}{n}\right)^{10000} \approx 1 - \frac{49995000}{n}$$

So the probability of a collision is about $\dfrac{49995000}{n} \approx 0.0000177217$. This agrees with Jean-Claude's exact calculation to five significant figures.

$\endgroup$
1
$\begingroup$

If you expand the factorial on the top and then cancel the factorial in the bottom, you have a numerator of $$(36^8)(36^8-1)(36^8-2)\cdots(36^8-9999)$$

As $36^8$ is much larger than $9999$, this numerator is going to be only slightly smaller than $(36^8)^{10000}$. Hence we are subtracting off a number only minimally smaller than $1$. This leaves us with a probability of collision that is extremely tiny.

A Poisson approximation could also be used, but I am not an expert in such.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .