NIST random excursion results

Question

NIST specifies so-called random excursions test and random excursions variant test. From the description I can derive that the number of p-values should be 8 in the first case and 18 in the second. But the result table gives only one line for each test. Keeping all of them is obviously redundant due to correlations. But it is not clear for me, which string out of 8 (or 18) should I take and why only one. Plus there is a question: what if only one of them is not passed, what should that mean?

Answer 1

So, there are a few things here.

8 in the first case and 18 in the second

Yes, that's correct but only if there is enough sample data. These last two tests need looads of numbers. In fact, in excess of the recommended minimum 10 x 1 million bits. I don't know exactly, and NIST doesn't say exactly. If happy, the test will return something like the bottom of the print out in Interpretation of the results of NIST (p)NRG suite, innocently plagiarised below:-

  4  12   3  15  10   4   7   6   3   7  0.011440     70/71      RandomExcursions
  6   8   6   7   8   6   7  11   7   5  0.937294     70/71      RandomExcursions
  6   6   4   4   5  12   9   9   8   8  0.491599     71/71      RandomExcursions
  2   6   2  10   9  11   9   5   7  10  0.127498     71/71      RandomExcursions
  5   7   5   8   9   8   9   4   7   9  0.881013     71/71      RandomExcursions
  6   8   4   8  12   8   3   8   8   6  0.519816     69/71      RandomExcursions
  5   5   7   5   3   7  10   7   9  13  0.275709     70/71      RandomExcursions
  3   6  11   6  14   6   6   3   8   8  0.099089     71/71      RandomExcursions
  7  13   8   4   6   4   5   8  10   6  0.339044     71/71      RandomExcursionsVariant
 11   9   6   6   8   7   7   1   6  10  0.362174     71/71      RandomExcursionsVariant
 10   8   9   8   8   6   8   3   6   5  0.781926     70/71      RandomExcursionsVariant
  9   8   7   8   5  10   9   6   6   3  0.754127     71/71      RandomExcursionsVariant
  9  10   7   9   5   5   7   9   5   5  0.808725     70/71      RandomExcursionsVariant
  5  14   8   5   2   3  11  11   6   6  0.025193     70/71      RandomExcursionsVariant
  9   3   6   5  10   8   7   7   8   8  0.808725     70/71      RandomExcursionsVariant
  6   5   5   8  10   8   7   9   5   8  0.901761     69/71      RandomExcursionsVariant
  3   9   5  12   6   6   6  10   8   6  0.437274     71/71      RandomExcursionsVariant
  3   6   7   2  10  11   6  10   7   9  0.238562     71/71      RandomExcursionsVariant
  4  10   6  12   3  13   4   4   5  10  0.033552     71/71      RandomExcursionsVariant
  7   2  15   7   7   9   7   4   8   5  0.083381     71/71      RandomExcursionsVariant
  8   6  13   6   6   6   5   9   7   5  0.577844     71/71      RandomExcursionsVariant
  6  15   6   8   6   5   8   4   3  10  0.083381     71/71      RandomExcursionsVariant
 11   4   7  10   6  10   3   8   6   6  0.437274     71/71      RandomExcursionsVariant
 11   5   4  11   5   9  10   4   7   5  0.295803     69/71      RandomExcursionsVariant
 10   5   8   6   4  13   4   7   8   6  0.339044     70/71      RandomExcursionsVariant
 10   5   6   7   5  11   8   8   7   4  0.696376     71/71      RandomExcursionsVariant

obviously redundant due to correlations

They're not correlated, unless your data is :-) The suite takes your sample set and partitions it into multiple streams/chunks. Each test is run on a different sequence. That's why you need so much data. I typically use at least 10 times the 10 x 1 million bits (~10MB). Even more is even betterer.

what if only one of them is not passed, what should that mean?

That your sample is properly random. Or to be mathematically and philosophically pedantic, there is insufficient evidence to suggest that your sample set is not independently and identically distributed. Again from that example:-

The minimum pass rate for each statistical test with the exception of the
random excursion (variant) test is approximately = 96 for a
sample size = 100 binary sequences.

The minimum pass rate for the random excursion (variant) test
is approximately = 67 for a sample size = 71 binary sequences.

Because randomness is quite pesky, there is no theoretical threshold that can be used as a hard cut off in the (is random?) decision process. And the issue is confounded by multiple independent tests that might contradict each other on the same data set.

From experience, you tend to look at the results and see what sort of feeling you get. A very few test failures probably do not mean anything adverse. Rerunning the tests on another sample set might produce slightly different results. Experience is required. When your RNG is misbehaving, it will be pretty obvious with multiple p values near 0.0 or 1.0. NIST use a 1% decision rule, but a bad RNG will be way outside that.