5
$\begingroup$

I asked a student of mine this question:

If you have a random number generator that outputs a number between $1$ and $k$, how would you write a test that decides whether the generated distribution is uniform ?

The student understood that we need to call the generator $n$ times and save a histogram $h_i$.

However I would expect the end test to be: $$\sum{(h_i-\frac{n}{k})^2}<t$$ Where $t$ is a threshold that depends on $n$ and $k$

And what the student suggested is $$1-t<\frac{h_i}{n/k}<1+t$$ Again, for some $t$ that is a function of $n$ and $k$

Is the student correct ? Are those two ways equivalent ?

$\endgroup$
  • 3
    $\begingroup$ Both are poor tests. Use the standard $\chi^2$ test. $\endgroup$ – whuber Mar 28 '16 at 19:32
  • $\begingroup$ $\chi^2$ test (or any other test) answers the question "how do you determine the threshold ?", whats interesting here, is "what do you do with the threshold ?" $\endgroup$ – Uri Goren Mar 28 '16 at 21:04
  • $\begingroup$ Could you elaborate? Your stated question asks for a decision concerning whether the distribution is uniform or not. Your subsequent remarks appear to focus on developing a test statistic. (Both suggestions are likely to be inferior to the $\chi^2$ statistic for detecting non-uniformity.) In this context, what do you mean by "what do you do with the threshold"? $\endgroup$ – whuber Mar 28 '16 at 21:35
  • 1
    $\begingroup$ The issues to address in a testing situation like this are not "validity" but power and efficiency. I confess I don't fully understand the student's suggestion because it appears to be a collection of criteria applied separately to each $i$ without stating how those results are to be combined into a single test. I have therefore not been reading this question closely, because I believe it must have typographical errors in it, and have only responded to the general nature of it. $\endgroup$ – whuber Mar 28 '16 at 21:53
  • 2
    $\begingroup$ By a number between $1$ and $k$ is this intended to be a test of a generator of a discrete uniform (values on $1,2,3,...,k$) or a continuous uniform between $1$ and $k$? The phrasing in the quoted part suggests the second, but the part with the histogram suggests the first (since if you were histogramming a continuous variate you'd get $k-1$ bins ... but it wouldn't be the first time someone made a fencepost error in a question). Please make the discreteness or non-discreteness of the random variate clear. $\endgroup$ – Glen_b -Reinstate Monica Mar 29 '16 at 2:28
1
$\begingroup$

UPDATE 2: striked wrong points, and replaced some by stuff I think are correct.

UPDATE 1: added direct analysis of both your uniformity tests, and kept my old answer as a proposed superior uniformity test that I suggest.

Summary

  • Both you and your student have offered uniformity tests that work.
  • Both of your tests don't work well with continuous numbers (i.e. if RNG spits out numbers in $[1,k]$ instead of $\{1,2,\ldots,k\}$.
  • Since the output of your uniformity score is not a probability, I think it has the disadvantage of being difficult to interpret.
  • Since your student's uniformity score is a probability, I think it has the advantage of being easy to interpret.
  • While not harmful to the correctness of the test, your student's uniformity test has one aspect that is useless (but also harmless; just redundant), namely: there is not point to add $t$ on right side of the inequality as the output is a probability.
  • One small error in your student's uniformity test is using $<$ instead of $\le$ for the upper bound. I think he/she should have used $\le$.

On the other hand, I think my proposed test is:

  • Unlike your tests, mine works with continuous numbers.
  • Similar to your student's test, mine is also easy to interpret cause it's a probability as well.

The disadvantage is that my test is possibly harder to compute. But this is not a big deal as I think the correctness of the test is worth the slight increase in difficulty.

Analysing your uniformity tests

Your notation confused me a bit. I assume that you mean that $h$ is a histogram, and $h_i$ is the frequency that is associated with input $i$ where $i$ is some number between $1$ and $k$ (which your RNG produces).

So to rewrite your test, I think you wanted to say this: \begin{equation} \text{teacher uniformity score} = \sum_{i \in \{1,2,\ldots,k\}} (h_i - \frac{n}{k})^2 \end{equation}

Then the uniformity test: the RNG is uniformly distributed if the uniformity score is less than some threshold $t_{teacher}$ that we agree upon. I.e. output from RNG is uniformly distributed if the following statement is true: \begin{equation} \text{teacher uniformity score} < t_{teacher} \end{equation}

I see why your method makes sense. Basically, your score is essentially the sum of squared errors of observed frequencies against expected frequencies, where expected is what should happen if the RNG is perfectly uniform. So if the sum of squared errors is minimal, the more uniform it is.

So my opinion about your test is this:

  • Pros:
    • it does have merit, and it does reflect the degree of uniformity of the RNG.
  • Cons:
    • it is not easy to interpret because the output is not a probability. If you augment it such that the output is a probability, then it would be easier to interpret. At least I can't interpret it easily. This interpret-ability is a subjective thing.
    • it is not friendly with continuous RNGs. You can't use histograms with continuous numbers without approximating numbers into bins, which essentially deletes information and opens the vulnerability that might potentially lead to masking non-uniformity of some poor RNGs. We need to look at the probability density functions (PDFs) instead.

What you wrote about what your student claimed is also confusing, but I rewrite that to what I think is the closest thing that makes best sense in my view (kindly correct me if you think the student didn't say this): \begin{equation} \text{student uniformity score} = \sum_{i \in \{1,2,\ldots,k\}} \frac{h_i}{n/k} \end{equation}

This is essentially the ratio between observed histogram and expected histogram (expected is the perfect uniform one). Clearly, if the ratio is 1 then it's perfectly uniform. But if it isn't (i.e. greater or less than 1) then it is not perfectly uniform.

So your student is suggesting that the closer the ratio is to 1, the more random it is. So $t_{student}$ is essentially some kind of error term that accounts for deviations from 1: \begin{equation} 1-t_{student} \le \text{student uniformity score} \le 1+t_{student} \end{equation}

My opinion about your student's uniformity test is as follows:

  • Pros:
    • It does have merit for the same reason yours does.
    • It is easy to interpret (thanks to it being a probability). This is subjective though. I think most humans agree with me (correct me if you disagree).
  • Cons:
    • It's not easy to interpret just like yours.
    • It doesn't work well with continuous RNGs for the same reason yours doesn't.

My test which I think is superior to both of your tests

Based on the question, you only seem to be interested in finding whether a sequence is uniformly distributed. I.e. it doesn't need to satisfy any other property.

If your PRNG is outputting some float, e.g. something in $[0,1]$, I would personally suggest doing this (which seems somehow similar to your student's suggest? I don't know..):

  • Repeat PRNG $n$ times, where $n$ is large enough.
  • Estimate the true probability density function $f_X$. Let $\hat f_X$ be your best estimation.

Then your sequence is perfectly uniformly distributed if $\hat f_X(x)$ forms a line with a slope of 0. This is usually unachievable in reality.

So you need to define a degree of uniformity that, if satisfied, you subjectively declare that the PRNG is uniformly distributed.

To do this, I would personally suggest to define the null hypothesis:

  • A sequence is uniform if the probability of each number to appear is $1/n$.

You then compute the probability based on your empirical trials.

Finally, you do some variant of Fisher's exact test to find the probability that your sequence can exist if the null hypothesis is true.

Once you get that probability, it is there where you plug your threshold. You and your student need to agree on this threshold. It's subjective.

In this specific approach, I'd expect you to agree on a very large probability that is very close to $1$. Maybe $0.999$, or whatever you and your student seem to be happy with.

Or maybe do the opposite: define the null hypothesis as:

  • Your sequence is not uniform, and probability of each number to appear is not $1/n$.

Then, you need to choose a a very small threshold in order to reject it.

$\endgroup$
  • $\begingroup$ Dude my answer is incorrect at least with respect to analyzing your student's test. It's clearly not a probability :D -- sorry. I just had a brain fart when I wrote that answer. You need to unmark this answer as an accepted answer because it's still wrong. $\endgroup$ – caveman Mar 30 '16 at 22:07
5
$\begingroup$

Note that we cannot conclude on the basis of only a sample that data is drawn from a uniform, only that it is consistent with having come from a uniform (sufficiently small deviations will be undetectable at any given sample size), or that it is not consistent.x

Since the request is for a test rather than simply a measure, presumably it is goodness of fit of uniformity that is the principle object.

There are a host of tests of uniformity that focus on different test statistics, and offer different power against various alternatives. It often makes sense to focus on the known ones instead of causally inventing new ones, because their characteristics are understood and (in particular) the kind of situations where they have good power will often be known.

I discuss some possible choices of statistic here.

Note that if your observations are an iid sample from a uniform, then histogram counts will have a multinomial distribution.

There are effectively two suggested test statistics in your question. Setting $E_i = n/k$, and slightly rearranging the second:

  1. $T_1=\sum_i {(h_i-E_i)^2}$

  2. $T_2=\max_i|\frac{h_i}{E_i}-1|$

Since your $E_i$ is constant over $i$ ($=E$ say), the first statistic is a scaled chi-squared test statistic ($T_1=E\cdot X^2$). So critical values (marking the boundary of the rejection region, i.e. your "t") can be determined quite readily.

Note further that 2. is equivalent to using the largest absolute Pearson residual (for either a Poisson or multinomial model) as a test statistic, since $\sqrt{E}\cdot T_2 = \max_i|\frac{h_i-E_i}{\sqrt{E_i}}|$ - noting further that $\sqrt{\frac{E}{1-p}}\cdot T_2 = \max_i|\frac{h_i-E_i}{\sqrt{E_i(1-p_i)}}|$ - where $p_i=p=k/n$).

I have suggested$^\dagger$ using just a statistic equivalent to $T_2$ as a quick visual test when testing roleplaying dice for uniformity (which dice generate discrete uniforms). While not a "standard" test, it's not hard to find critical values here either. This is particularly suitable when the alternative is for a single discrepant bin to have a substantially higher or lower proportion than expected but where the remaining bins are uniformly sharing the rest of the probability.

$^\dagger$ - see the dashed and dotted grey lines in the last two plots there, which mark two different choices for $t$ with different type I error rates. If you expect (or are most interested in being able to pick up) particular kinds of deviations, other statistics may be better than either of these.

$\endgroup$
2
$\begingroup$

It's like saying $a$ is close to be $b$ when $a-b$ is 0 or when $\frac{a}b$ is 1. I don't see why one should be better than the other.

$\endgroup$
  • $\begingroup$ The problem is that the two test statistics are not mathematically equivalent when there is more than one bin--and that suggests this answer is misleading. $\endgroup$ – whuber Mar 28 '16 at 19:33
  • $\begingroup$ @whuber: I don't think they're equivalent (never said they were). But any measure of "uniformity" seems to me to be arbitrarily defined. $\endgroup$ – Neil G Mar 28 '16 at 19:34
  • $\begingroup$ I believe most people would understand "I don't see why one should be better than the other" to mean they are equivalent in your opinion. But do you really mean "arbitrarily defined"? Even when the problem concerns a random generator for a set of integers $\{1,2,\ldots, k\}$? Besides the implicit sense of "equiprobable" expressed in the question, what alternative meanings of "uniformity" do you have in mind that would make sense and be meaningful in this context? $\endgroup$ – whuber Mar 28 '16 at 19:47
  • 1
    $\begingroup$ This is not a veterinary site; statistical procedures are not animals. In statistics, it is standard that "equally good" tests are tests with identical risk functions. If that's not what you meant, your answer is likely to be misunderstood, so you ought to consider clarifying your meaning. Your claims about "uniform" being "personal" fly in the face of all the literature on testing RNGs, so there's no need to argue that one. $\endgroup$ – whuber Mar 28 '16 at 19:54
  • 1
    $\begingroup$ @whuber Okay, I will do that, thanks for the suggestion. Yes, I knew there was some analysis possible with this question. For example, what is the probability a truly uniform RNG fails either test for given thresholds. I usually leave the harder math on this site to people like you ;) $\endgroup$ – Neil G Mar 28 '16 at 20:08

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.