0
$\begingroup$

Particular pseudo-random number generators are tested for their their ability to produce sequences of numbers that behave like values of independent variables that are each uniformly distributed on [0,1) or (0,1). Most tests apply a statistical test such as a $\chi^2$ or Kolmogorov-Smirnov test to a function of data generated by the PRNG. If the the p-value from a particular test is too close to 0 or to 1, that counts against the PRNG, since it is producing patterns that would be very improbable if the generator were truly uniformly distributed. If the p-value is not close to 0 or 1, we say that the PRNG has "passed" that particular test.

There are things about this procedure that seem odd to me, and I want to see whether I understand. Does the following reflect misunderstandings about PRNG testing or statistical testing in general?

  1. The procedure is based on a null hypothesis that the PRNG produces numbers that are uniformly distributed. However, there's one sense in which it's known from the start that the output is not II uniformly distributed: each number generated has a probability of 1 conditional on the internal state of the generator (and that state is a deterministic function of earlier state, etc.).

  2. A related point: If you read Knuth or L'Ecuyer or other authors on this topic, even if a PRNG has passed all previous tests it's always assumed that there may be further tests that a given PRNG would not pass. The sense you get is not that this is null hypothesis testing in the usual sense. If a PRNG passes all tests so far, the conclusion is not that we cannot reject the assumption that the output is uniformly distributed. The conclusion is that the output looks enough like what a truly uniformly distributed r.v. would produce, that it's OK, as far as we know, to use this PRNG for simulations. (EDIT: I am assuming that the usual goal of frequentist testing is to make inferences about the nature of an underlying process. [I don't think this assumption is free of controversy, but I can cite statistical authorities that make it, if requested.] The point here is that the PRNG authorities are never so rash as to think that any PRNG actually is a process that produces uniformly distributed output. All they want is a good simulation of uniformly distributed output.)

  3. The alternative hypothesis is not even a composite probabilistic hypothesis. It's not that the output has some probability distribution or other, though we have no clue as to what that would be. The alternative also includes the possibility that the output is not even probabilistically distributed at all (except in the sense that given a particualr initial seed, the subsequent sequence of numbers has probability 1). Maybe it's OK that the only alternative is completely vague, but it means, for example, that it's impossible to calculate power.

  4. The null in this case is unusual in that it doesn't represent a default state of affairs, or a low-information assumption, or lack of structure, or a safe assumption. If anything, the claim that the null is false is the default, low-information, lack of structure assumption, and it's dangerous to assume the null is true: If you incorrectly assume that your generator produces uniform-like output, your simulations might be misleading. (PRNG designers have to work very hard to design an algorithm that will not lead to rejecting the null.)

I understand that Cross Validated isn't a forum for debate. I just want to know whether I am simply confused about something above.

$\endgroup$
  • $\begingroup$ Chapter 10 might contain answers to some of your questions. $\endgroup$ – Dimitriy V. Masterov May 29 at 20:50
  • $\begingroup$ Your question seems overly broad. Perhaps with a little clarification it might be less so. 1. In what way are the aspects mentioned in point 2 unlike usual hypothesis testing for goodness of fit? 2. For that matter, how is point 3 unlike any typical omnibus goodness of fit testing? Note than you can calculate power against any specific alternative, and the power will in general be different for each such specific alternative. Neither of these points seem to be raising anything specifically different when testing RNGs compared to goodness of fit testing in other applications. $\endgroup$ – Glen_b May 30 at 0:37
  • $\begingroup$ Thanks @DimitriyVMasterov. I had not read that piece by Cook. It really is a nice introduction to certain aspects of the subject. It's not too relevant, as it turns out, because much of the focus is on avoiding a buggy implementation of a good PRNG algorithm. My question concerns testing different algorithms when they are implemented as intended. The question is whether a particular algorithm does what it's supposed to do. This is a nontrivial challenge for PRNGs. $\endgroup$ – Mars May 30 at 0:55
  • $\begingroup$ Thanks @Glen_b. I've added clarification to #2. About your comment on #3, and maybe the comment on #2 as well: I think these are actually answers, or partial answers, at least. You are telling me why my assumptions are wrong. That's what I wanted to know. $\endgroup$ – Mars May 30 at 1:04

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.