2
$\begingroup$

Each of the NIST tests are generally explained in Random Bit Generation - Guide to the Statistical Tests. I was wondering if some one can help me understand them better. For example, which tests show the robustness, independence, ergodicity, stationarity, etc.

Based on the description provided on NIST website, I think, the mentioned features can be understood from following tests:

  1. robustness: cumulative sum test

  2. independence: random binary rank test

  3. ergodicity: Maurer's universal statistical test or linear complexity test

  4. stationarity: cumulative sum test

I was wondering if these are correct. In addition, if other NIST tests can be summarized.

$\endgroup$
-1
$\begingroup$

It's difficult to map each of the 15 tests to a particular qualitative descriptor. Adjectives like robust are not mentioned in the 800-22 documentation.

The null hypothesis of randomness ($H_0$) in all tests fundamentally requires samples from a stationary and ergodic process. Otherwise the tests would be inconsistent with respect to time, and could not accurately model the samples' shifting distributions or test score expectations. Or the test scores for this million bits would differ widely from that million's. Although be mindful of some variability implicit in any random process.

The requirement for independence within each test varies though. §2 of 800-22 details the mathematical assumptions underpinning each test. NIST doesn't always highlight the level of significance of independence within each test. They often don't attempt to debate the causality of a $H_0$ sequence, just it's effect and characteristics.

Some are explicitly discussed. The Discrete Fourier Transform (Specral) test is an example of a test that specifically targets independence in the mathematical sense. It looks for correlations between samples spaced $n$ samples apart. Maurer’s "Universal Statistical" test is similar, exploiting correlation for compressibility. As is the Binary Matrix Rank test. Conversely the Frequency (Monobit) test doesn't. It will accept any degree of correlation as long as the ones and zeros are evenly matched in line with a half normal distribution.

The sensitivity to independence is harder to identify with some of the other tests. You may have to decompose the statistics beneath tests like the Serial or Cumulative Sums (Cusum) tests.


Don't confuse the recommended input lengths with non ergodicity. The recommendations are there simply to facilitate some of the test metrics' reference distributions, or to limit processing time.

$\endgroup$
  • 2
    $\begingroup$ Please indicate why the question is downvoted. I express my sincere hope that it won't lead to extended discussion. Please agree to disagree. $\endgroup$ – Maarten Bodewes May 16 '19 at 12:06

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.