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.
