7
$\begingroup$

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?

$\endgroup$
5
  • 2
    $\begingroup$ Recommend clarifying whether you are assuming independence of successive function calls. If not, this XKCD gives a function that "has an underlying uniform probability distribution for its generation" but may not be what you had in mind. $\endgroup$ Aug 1 at 0:22
  • 1
    $\begingroup$ @GeoffreyBrent though Dilbert had something similar earlier $\endgroup$
    – Henry
    Aug 1 at 0:38
  • $\begingroup$ added independence of successive calls to post. $\endgroup$
    – Taako
    Aug 1 at 1:06
  • $\begingroup$ Is this about good vs. bad random number generators, or about good random number generators drawing from a uniform distribution vs. some other distribution? $\endgroup$
    – hobbs
    Aug 1 at 14:49
  • $\begingroup$ @hobbs this question was inspired by the former, but i was curious about the latter as well. I thought it would be interesting to learn if there was some manner in which you can test a blackbox RNG against a distribution to see the likelihood that the blackbox uses that distribution. But without having a list of the output values generated by the RNG i dont think we could determine the underlying distribution; so for this question i really was focusing on determining if it was uniform or not. $\endgroup$
    – Taako
    Aug 1 at 16:35
10
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Exactly! Die Hard exploits the birthday problem as one of its many tests. $\endgroup$
    – Xi'an
    Aug 25 at 11:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.