As detailed in the paper Statistical test suite for random and pseudorandom number generators for cryptographic applications by NIST, the first test is given as a basic significance test, it uses a bit sum and calculates the p-value and test statistic. But I do not have the clearest understanding of why $S_{obs}$ is defined as the sum of the sequence divided by the square root of the length of the sequence. What is the statistical rationale behind why this is done two times in order to find a z value?


1 Answer 1


Since the test uses $X_k=\pm 1$ as its symbols, it is statistically based on the idea of a simple random walk with unknown bias (if $p=1/2$ then the bias is zero).

By the Central Limit Theorem, for an independent identically distributed sequence $X_k$ we have convergence in distribution, i.e., $$ \frac{(X_1+X_2+\cdots+X_n)-n\mathbb{E}(X)}{\sqrt{ n\sigma^2}} \stackrel{\cal D}{\longrightarrow} \cal{N}\mathrm{(0,1)}. $$ If you do some algebraic manipulation, you can see that the test statistic is exactly the left hand side and the $Z$ value is of course based on a gaussian distribution.

  • $\begingroup$ Your answer is very good. And I believe it is helpful, but do you mind elaborating on why in the paper they divided by $\sqrt{2}$ from the test statistics in the erfc equation? $\endgroup$ Mar 12, 2023 at 23:21
  • $\begingroup$ Since they use absolute value, I think, going between one sided vs two sided? $\endgroup$
    – kodlu
    Mar 12, 2023 at 23:29
  • $\begingroup$ I thought it had something to do with the positive values defined only as well, but what does it mean to be half normal? In particular, why can't they just change the significance level why does dividing by the square root of two and not 2 solve the issue? $\endgroup$ Mar 12, 2023 at 23:35
  • 1
    $\begingroup$ I figured it out, you are right about the two-tailed. It is just that there are different gaussian distributions in the text and it was hard to make them relate when I was looking at them. $\endgroup$ Mar 13, 2023 at 1:00
  • $\begingroup$ great that you figured it out. you can upvote the answer if it was helpful. $\endgroup$
    – kodlu
    Mar 13, 2023 at 2:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.