randomstatisticsgoodness-of-fit

Computing correlations and performing goodness of fit for prng testing


I'm following along with a description of a test for pseudo-random number generators, and attempting to implement the test in C. There's one thing I'm hung up on though. The text in question is as follows:

Applies a correlation test on the Hamming weights of successive blocks of L bits. Let Xj be the Hamming weight (the numbers of bits equal to 1) of the jth block, for j = 1, . . . , n. The test computes the empirical correlation between the successive Xj’s,

enter image description here

Under H0, as n ⇢ infinity, p̂ * sqrt(n - 1) has asymptotically the standard normal distribution. This is what is used in the test. The test is valid only for large n.

Now, my plan is to compute this test statistic and perform a goodness of fit test to the normal distribution using the Anderson–Darling test. However, I'm a bit confused as to how you get a distribution from this single test statistic. From my understanding, for my full set of bits n, I'll get just one . So then I'll get just one test statistic p̂ * sqrt(n - 1). How am I supposed to compare this to the normal distribution? Would the idea be to break up my dataset into multiple chunks with their own n, compute a test statistic for each, and then compare this distribution to the standard normal? I just want to make sure I'm understanding the calculation of correctly.


Solution

  • IF you want to perform perform a goodness of fit test to the normal distribution, it means you have to have many sampled gaussian values. So if p̂ * sqrt(n - 1) is asymptotically N(0,1), then single test run will produce single number. So if you have software based RNG to test, you continue with another n samples and get another random N(0,1) number etc. If you're already got N numbers from, say, some hardware device, you have to split it in chunks, run test, from each chunk you'll get one number supposedly from N(0,1), and you run distribution test.

    Paper: Beware of Linear Congruential Generators with Multipliers of the Form a = +-2q +-2r PIERRE L’ECUYER and RICHARD SIMARD, AACM, 1999

    I have a copy if you need it