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?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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$ Commented Mar 12, 2023 at 23:21
-
$\begingroup$ Since they use absolute value, I think, going between one sided vs two sided? $\endgroup$– kodluCommented 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$ Commented 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$ Commented Mar 13, 2023 at 1:00
-
$\begingroup$ great that you figured it out. you can upvote the answer if it was helpful. $\endgroup$– kodluCommented Mar 13, 2023 at 2:10