# Probability distribution for collisions / birthday problem

Let's say I have a source of randomly produced values from a range $$M$$. I want to test if the source is a uniform distribution by examining a sample sequence of $$n$$ values $$m_1, m_2,\dots,m_n$$. Because the range $$M$$ is very large, and $$n << M$$, many statistical tests cannot be applied (e.g. Chi-square test on frequencies of each possible outcome).

I can count the number of collisions $$k$$, which is the number of values $$m_j$$ such that $$m_j=m_i$$ for at least one $$i. I want to determine the probability of $$k$$ given $$n$$ and $$M$$. (Assuming I can use a large enough $$n$$ such that $$\bar{k}$$, the expected average number of collisions, is significant enough for such a test).

I have found the expected number of collisions is provided by: $$\bar{k}=n-M+M\left(\frac{M-1}{M}\right)^n$$

I don't know how to get to calculate the probability for a given value of $$k$$ though. E.g. can $$k$$ be modeled using a binomial or Poisson distribution?

More specifically, I want the probability that a true random source would provide the same or more extreme value of $$k$$ away from the expected average. I am using computer software to do this, so I'm happy to consider numerical solutions.

I could use:

• A cumulative distribution function (CDF), if one is known that gives the probability of a result $$p_{k'}=Prob(k<=k')$$. E.g. if $$k$$ conforms to a normal or binomial distribution, then I can use the known CDFs for those.

• A probability distribution function (PDF), again, if one is known. I can sum up the probabilities for $$0$$ to $$k$$ to get $$p_k$$. After all, it is a discrete distribution, and I won't be doing tests where $$\bar{k}$$ is particularly large.

• In either of the above cases, if $$p_k$$ is the probability of $$<=k$$ collisions, then the p-value I need for my test is, I believe, $$p=1-2\lvert{p_k-0.5}\rvert$$.

• I could theoretically enumerate all sequences of collisions and unique numbers. Practically speaking, this would not be possible, as this would be $$2^n$$ sequences, and therefore too many.

• Another numerical approach would be to build up a table of $$p_{i,j}$$'s, where $$p_{i,j}$$ is the probability of $$i$$ collisions after $$j$$ values (I only need $$i=0\dots k$$ for $$j=0\dots n$$). For each step, the number of unique values is given as $$u=j-i$$, and the probability of a collision is therefore $$u/M$$. That still requires something of the order $$O(k^2n)$$, which is much better, but may still be infeasible.

I could create several samples of sequences, count the collisions in each, and look at the resulting distribution to see if that tells me anything. However, I would much prefer to use something with a more solid mathematical basis. Note that $$M$$ and $$n$$ can vary from test to test.

• A similar test is the Birthday Spacings Test from the Diehard suite. That counts the number of unique gaps between sorted values, and can be adapted. That uses a Poisson distribution, but that's only an approximation and I'll need to see if that would work for my parameters. Jun 2, 2020 at 5:52
• There are several ways of measuring collisions though I am not sure any of them exactly give your expectation. The distribution may involve Stirling numbers of the second kind, though a Poisson or binomial approximation might not be so bad in limited circumstances Jun 23, 2020 at 14:46