0
$\begingroup$

(Forewarning: I'm a programmer, not a statistician, so I apologize in advance for any misuse of terminology!)

I'm testing a known random number generator that implements the PCG algorithm. This RNG outputs integers in the range $[0, 2^{64})$. I built a function on top of it $F(n)$ that allows me to generate a random integer in the range $[0, n)$ by calculating $X \bmod n$ where $X$ is an output of the PCG RNG. This is subject to modulo bias, so I implemented the solution to that in my function as well.

Now I want to make sure that the numbers produced by $F$ are uniformly distributed. I generate 1,000,000 samples for each of several values of $n$. I then attempt to use the Kolmogorov-Smirnov test, but I have the following questions:

  1. For small values of $n$, like 10, the stepping of the function interferes with the test (which, as we know, isn't designed to work with discrete distributions). I tried to work around the problem by using a chi-squared test, but my binning method seemed to have more of an impact on the test than the actual distribution. So I came up with the "brilliant" solution of adding to each sample a fraction of the step value, $i/N$ where $i$ is the iteration and $N$ is the number of samples (in my case 1,000,000). In other words, I am testing $F'(n, i) = F(n) + \frac{i}{N}$ instead.

    This makes the Kolmogorov-Smirnov test appear to work for even the small values of $n$ I mentioned, i.e., if I run my test suite 100 times I get roughly 1 failure at $\alpha = 0.01$. And if I mess with the values produced by the RNG, for example by changing $X \bmod n$ to $(X \land {10101010101010101010101010101010}_2) \bmod n$, the p-value immediately diminishes to 0.

    That said, I haven't found any academic research that suggests adding a fraction of the step value to each sample is a reasonable way to convert a discrete distribution to a seemingly continuous one. Is this a valid approach or am I actually testing something I don't want to, like the uniformity of the step itself?

  2. If I pick an $n$ that I suspect will be subject to a lot of modulo bias, for example $\frac{2}{3}({2^{64}-1})$, I do get reliable rejection of the null hypothesis if I omit my bias correction code (yay!). But I wonder if there's a more analytic way to choose $n$ values to test? I just chose a few that I thought would be common use cases or interact with the code in question in interesting ways.

Thanks for any insight you can provide!

$\endgroup$
4
  • 1
    $\begingroup$ Kolmogorov-Smirnov or any other goodness-of-fit test only assesses one aspect of the RNG. There is a large literature on PRNG tests, starting with George Marsaglia's DieHard battery of tests. Note also that the outcome of the KS test should be compared to a Uniform distribution, rather than using a p-value, which is much less informative since binary. $\endgroup$ – Xi'an Dec 29 '20 at 9:55
  • $\begingroup$ Hi, thank you for that information -- I had never heard of this and I will look through it to see if a test suits my needs! I should note though that I already have confidence that the RNG itself is producing uniformly random numbers; I just want to test my derived function F. For my K-S test, I'm currently using a 1-sample test against the uniform distribution and comparing the result to a critical value I found in a table for α = 0.01 (1.63 / √N). Are you saying that I should perform a 2-sample test that should itself produce uniform p-values? What would the second sample be in that case? $\endgroup$ – impl Dec 29 '20 at 18:38
  • 1
    $\begingroup$ I picked the 2D minimum distance test from the diehard tests and it works very well for my use case! It also helped me understand what you meant by uniform distribution of outcomes as I now run this test many times. Thanks for the suggestion. I will consider adding more tests over time as well. I'll leave this question up for now because I think the question I proposed is still interesting, but I'm happy with my new approach to testing! $\endgroup$ – impl Dec 30 '20 at 8:39
  • $\begingroup$ Regarding the use of the KS-test, I am suggesting NOT to use a critical value but the comparison of the empirical distribution of the p-values with a Uniform target. $\endgroup$ – Xi'an Dec 30 '20 at 9:40

Your Answer

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

Browse other questions tagged or ask your own question.