How to determine the likelihood a random number generator is using a uniform distribution?

Question

Let's say I have a blackbox function generate_number() that generates a random number between 1-N; and assume N is known. Each function call is independent from each other and carries no state.

I use this to generate X numbers; let's say these numbers are not stored anywhere so i can't build an exact list of them.

I also have another blackbox function num_seen_numbers() that tells me Y which is how many unique numbers of the N numbers have been generated.

For example. Let's say N = 100 (given), and I call generate_number() 40 times (X = 40). Then I call num_unseen_numbers() and it says out of the total N = 100 possible numbers, it has only generated 15 unique ones (Y = 15).

Is there a way to to determine the likelihood that generate_number() has an underlying uniform probability distribution for it's generation?

Answer 1

This is the birthday problem in another form.

With $d$ equally likely days and $n$ independent draws, the expected number of distinct days drawn is $d(1-(1-\frac1d)^n)$ which in your case of $d=100$ and $n=40$ is about $33.1$, rather more than $15$.

The probability of $x$ distinct days drawn is $\dfrac{d! \, S_2(n,x)}{(d-x)!\, d^n}$ where $S_2(n,x)$ is a Stirling number of the second kind.

In your case of $d=100$ and $n=40$ and $x=15$ this probability is about $9.47\times 10^{-17}$ and for $x \le 15$ is about $9.61\times 10^{-17}$, both of which are extremely small. By contrast, the probability for $29 \le x \le 38$ is about $0.9765$.

You can use this as a possible test that the draws are uniform and independent.

Answer 2

With $N = 365$ and $x = 23,$ randomly generated numbers, your vetting procedure is similar to the famous birthday problem, in which one would expect matching numbers among the $x$ a little more than half the time. However, the likelihood of matching birthdays among $23$ is reasonably robust to real-life situations in which some months are more likely to generate actual human birthdays than others.

Thus a failure to get one or more matches about half the time would cast doubt on the randomness of the 'generator', but getting matches nearly half the time time would not be strong evidence that the numbers are generated truly at random.

Classic birthday problem with equally likely 365 equally likely birthdays. By simulation in R, $P(Y = 0) = 0.494 \pm 0.003$ [the exact probability of $0$ matches is $0.4927$ to four places] and $E(Y) = 0.678\pm 0.005.$

set.seed(1234)
x = 23;  N = 365
y = replicate(10^5, x-length(unique(sample(1:N,x,rep=T))))
mean(y==0);  mean(y)
[1] 0.49395   # aprx P(No Match)
[1] 0.67842   # aprx E(Nr Matches)
2*sd(y==0)/sqrt(10^5)
[1] 0.003162062
2*sd(y)/sqrt(10^5)
[1] 0.005012195

With days not equally likely (roughly 95% and 110% as likely in two halves of the year): $P(Y=0) = 0.491\pm 0.002, E(Y)=0.683\pm 0.003.$

Within the margin of simulation error, results are not significantly different from those for equally likely days.

set.seed(1235)
x = 23;  N = 365;  pr = c(rep(95, 180), rep(105, 185))
y = replicate(10^5, x-length(unique(sample(1:N,x,rep=T,p=pr))))
mean(y==0);  mean(y)
[1] 0.49102
[1] 0.68265
sd(y==0)/sqrt(10^5)
[1] 0.001580892
sd(y)/sqrt(10^5)
[1] 0.002509512

The birthday problem has been shown with more extensive simulations not to be especially finicky in case birthdays are not exactly equally likely.

There are lists of problems that are notoriously sensitive to imperfections in random number generators. You can google the 'Die Hard Battery' of especially finicky simulation problems that have been used to vet pseudorandom number generators.