# About some tests in NIST SP 800-22 rev 1a and erfc function

I'm learning the randomness test of the NIST SP 800-22 rev 1a documentation.

https://csrc.nist.gov/publications/detail/sp/800-22/rev-1a/final

As I was reading, a few questions came up and I put them up like this. My questions are:

1. In the Frequency Test within a Block of 2.2, looking at (3) of 2.2.4, there is a part that is calculated as follows. $$\chi^2(obs)=4M\sum_{i=1}^{N}(\pi_i - 1/2)^2$$ I don't understand why it's multiplied by 4 here.

2. In the Runs Test of 2.3, the p-value is calculated as $$P-value = erfc(\frac{|V_n(obs)-2n\pi(1-\pi)|}{2\sqrt{2n}\pi(1-\pi)}).$$ What is the value of the denominator here? I know that $$2\pi(1-\pi)$$ is the mean, but I don't know where the denominator came from.

3. Is there any reason to find the p-value through erf instead of the normal distribution in (2)?

Thank you.

1. This is worrisome. The usual Pearson $$\chi^2$$ test would be $$M\sum_{i=1}^n\frac{\left(\pi_i-\frac12\right)^2}{\frac12}=2M\sum_{i=1}^n\left(\pi_i-\frac12\right)^2.$$ I will think some more, but it might be worth dropping aquifers to NIST.
2. It's supposed to be the standard deviation. For independent, identically distributed bits the run statistic should be binomially distributed. The central limit theorem then tells us that the binomial can be approximated with the normal distribution. Note however that the square root sign should extend over the $$\pi(1-\pi)$$ factor.
• Thanks for your reply. But I don't quite understand the second answer. If I write the expression as you say, shouldn't $p-value$ be $erfc(\frac{|V_n(obs)-n\pi|}{\sqrt{n\pi(1-\pi)}})$?because for CLT I need to construct the expression $\frac{V_n-np}{\sqrt{npq}}$. Mar 19, 2022 at 10:39
• Your statistic would be correct for testing the number of 1s ($\pi$ is the probability that a 1 is output). They're counting the number of 01s and 10s. These occur with probability $(1-\pi)\pi$ and $\pi(1-\pi)$ so that we have a $\mathrm{Bin}(n-1,2\pi(1-\pi))$ distribution. Looking deeper, there seems to be some strange approximation going on. Fortunately, this document is being revised, so there may be a chance to clear things up in the new version. Mar 19, 2022 at 11:13
• As you mentioned, it is understandable that $V_n(obs)$~$Bin(n-1, 2\pi(1-\pi))$ is satisfied because they count the number of 10s and 01s. However, since even such a case satisfies expression $P-value = erfc(\frac{|V_n(obs)-2n\pi(1-\pi)|}{\sqrt{n2\pi(1-\pi)(1-2\pi(1-\pi))}}).$, the expression in the document is not satisfied. Is the expression in the document wrong? (+Actually, it should be written as $n-1$ instead of $n$, is it okay to change it arbitrarily?) Mar 19, 2022 at 11:31
• I hesitate to claim incorrectness as they might be using some approximation to the variance that I'm not aware of. Note that your erf expression requires a $\sqrt 2$ in the denominator. The error switching from $n-1$ to $n$ is negligible as $n$ grows. I do think that it's worth raising this and your first query with NIST if the expressions still appear in the revised version and I will try to do so. Mar 19, 2022 at 12:04