Does the p value in randomness tests provide any real value?

Question

In the dieharder test suite there are things like:-

diehard_3dsphere|   3|      4000|     100|0.56011310|  PASSED  

and in the NIST IID (brief mode) and randomness test suites there are things like:-

** Passed IID permutation tests

and:-

  1   2   1   1   0   2   2   0   0   1  0.739918     10/10      Universal
  1   0   2   3   1   0   0   1   1   1  0.534146     10/10      ApproximateEntropy
  0   1   2   0   2   1   0   1   0   0     ----       7/7       RandomExcursions
  2   0   0   1   3   0   0   0   0   1     ----       7/7       RandomExcursions
  0   0   0   1   0   1   1   1   2   1     ----       7/7       RandomExcursions
  2   0   0   0   1   2   0   2   0   0     ----       7/7       RandomExcursions
  0   1   1   0   0   3   0   1   1   0     ----       7/7       RandomExcursions
  0   0   0   2   0   1   1   0   2   1     ----       7/7       RandomExcursions
  0   0   1   0   1   1   0   1   2   1     ----       7/7       RandomExcursions
  1   0   1   0   2   2   1   0   0   0     ----       6/7       RandomExcursions
  0   0   2   0   2   1   0   1   1   0     ----       7/7       RandomExcursionsVariant
  0   1   1   1   0   2   1   0   0   1     ----       7/7       RandomExcursionsVariant
  0   2   1   0   1   0   1   1   1   0     ----       7/7       RandomExcursionsVariant
  0   2   1   0   1   0   0   0   2   1     ----       7/7       RandomExcursionsVariant
  0   1   1   0   0   2   0   0   2   1     ----       7/7       RandomExcursionsVariant
  0   0   1   1   0   0   1   1   2   1     ----       7/7       RandomExcursionsVariant
  0   0   0   1   2   1   0   1   2   0     ----       7/7       RandomExcursionsVariant
  0   0   1   1   0   2   1   0   1   1     ----       7/7       RandomExcursionsVariant
  0   1   0   2   1   0   0   0   2   1     ----       7/7       RandomExcursionsVariant
  0   2   0   1   1   1   0   0   2   0     ----       7/7       RandomExcursionsVariant
  0   1   1   1   0   2   0   1   1   0     ----       7/7       RandomExcursionsVariant
  0   1   0   1   0   1   0   0   1   3     ----       7/7       RandomExcursionsVariant
  0   0   1   0   1   0   2   1   1   1     ----       7/7       RandomExcursionsVariant
  0   0   1   0   2   1   0   2   1   0     ----       7/7       RandomExcursionsVariant
  0   0   1   1   1   0   1   2   1   0     ----       7/7       RandomExcursionsVariant
  0   0   0   0   2   1   0   3   1   0     ----       7/7       RandomExcursionsVariant
  0   0   0   0   1   2   0   3   1   0     ----       7/7       RandomExcursionsVariant
  0   0   0   1   1   2   0   0   1   2     ----       7/7       RandomExcursionsVariant
  0   0   2   3   1   0   1   1   0   2  0.350485     10/10      Serial
  1   2   1   1   1   1   1   0   1   1  0.991468     10/10      Serial

In the above you will notice that there are no p values available for the RandomExcursionsVariant tests (as the sample was only 10 MB). p values are uniformly distributed $ \mathcal{U}(0,1) $ so they fall randomly anywhere within that interval. They can be high, low or middling. And occasionally we even expect them to be outside of the critical $\alpha$ value for what we know to be valid data samples. IMHO, the failure or success of the these tests is most clearly conveyed by a test score (e.g. 7/7) as above, or a semantic message stating so, e.g. "PASS.."

Given that p values sometimes do not even appear, and are randomly distributed when they do, what value are they in randomness testing?

Answer 1

I believe the lack of p-values is because you are not using enough bit streams. In the NIST 800-22 suite, if you use too few bit streams you will not get those p-values for some of the tests. For this reason, I recommend using at least 20. (If you use 20 and don't get a p-value, then that would surprise me and that would not be good). So to answer your question:

Given that p values sometimes do not even appear, and are randomly distributed when they do, what value are they in randomness testing?

The p-values you see in the summary there are the p-values of the uniformity of the n p-values for the n bit streams you tested (using a KS test I imagine). Them not appearing is only because there weren't enough to feed a KS test. As for the randomly distributed part: that's the whole point! We expect the n p-values to be uniformly distributed over [0, 1), and when there is an indication that they are not uniformly distributed (indicated by a low p-value for the KS test), then you will get a star next to that p-value indicating it is below the threshold that NIST uses.

As for the semantic PASS/FAIL messages, NIST does have those, just perhaps not in the exact format you prefer. Namely, they put a star next to p-values that are below the threshold. If you don't see any stars, then everything passed!

Disclaimer: I have only used the NIST 800-22 tests. If you are referring to another NIST test suite I have not used it so I am not familiar with those.

Answer 2

I'm not very familiar with dieharder, but I think the p-values are very useful for such tests. Far more than some arbitrary threshold.

If the data indeed behaves like random data, we expect the p-values to be uniform. But the pupose of the tests is to find a way in which the data doesn't behave like random data.

Obviously every possible bit stream could have come from a true random source, so it's difficult to conclusively state anything.

But the p-value allow us to quanitify the tests, how likely is this test to product a similar or more extreme result on truely random data. A low p-value should be worriesome, and we might want to collect more data. If a test has low p-value and we collect more data and still has a low p-value, that would be very serious evidence for non-randomness.

Alternatively we might apply some correction for multi-hypothesis testing. The simplest would be to multiply the pValue by the number of tests. Is it still low? That again would be strong evidenence for non randomness.

pValues we can understand and reason about. pass/fail is simply trusting somebody else who may have had different goals and applications in mind of setting a good threshold.