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<j$. 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.

  • $\begingroup$ 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. $\endgroup$
    – Chris VP
    Jun 2, 2020 at 5:52
  • $\begingroup$ 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 $\endgroup$
    – Henry
    Jun 23, 2020 at 14:46


You must log in to answer this question.

Browse other questions tagged .