Reliability conditions for the two-level testing approach of the NIST SP800-22 test suite

The two-level approach to evaluating the quality of random number generators, proposed in the NIST SP 800-22 test suite, which consists in calculating the frequencies of $p$-values that fall into $k=10$ equal intervals of $[0,1]$, and checking their distribution for uniformity with the Pearson's chi-square test, was considered. Such approach may increase the reliability of the test, however it is sensitive to the approximation error introduced by the computing of $p$-values. In this paper it is shown that for AES-based sequences the two-level testing approach is not reliable too. The systematic error in the computing of $p$-values depends on the accuracy of approximation the prelimit distributions of statistic by its limit distribution for the sample size $n$ tends to infinity. For a reliable second-level test, this error should be smaller, or at least, approximately equal to $\sigma/N = \frac{1}{k}\sqrt{ \frac{k - 1}N}$, where $\sigma =\sqrt{\frac1k\left(1-\frac1k\right)N}$ is the standard deviation from the mean number of particles $\frac{N}k$ in a bin for the equiprobable scheme of allocation $N$ particles ($p$-values) in $k$ bins. Such heuristic assumptions and carried out experiments suggest that for example in the second-level test of the Frequency test of NIST SP 800-22 test suite with $n=2^{20}$ the number of tested sequences $N$ should not exceed $26000$.
Two-sided estimates of the quantiles of the binomial law are proposed, the combined application of which, with universal inequalities for the distribution function of the binomial law, makes it possible to completely eliminate the systematic error appearing in the Frequency test when determining the numbers of $p$-values found in each sub-interval of the $k$ possible disjoint sub-intervals of $[0,1]$.