Origin of the Chi-Squared test statistic for serial test (two bit test)

On page 181 of Handbook of Applied Cryptography Chapter Five, it states the following:

The purpose of this test is to determine whether the number of occurrences of 00, 01, 10, and 11 as subsequences of s are approximately the same, as would be expected for a random sequence. Let $$n_0$$, $$n_1$$ denote the number of 0’s and 1’s in s, respectively, and let $$n_{00}$$,$$n_{01}$$,$$n_{10}$$,$$n_{11}$$ denote the number of occurrences of 00, 01, 10, 11 in s, respectively. Note that $$n_{00} + n_{01} + n_{10} + n_{11} = (n − 1)$$ since the subsequences are allowed to overlap. The statistic used is $$X_2 = \frac{4}{n-1}(n_{00}^2+n_{01}^2+n_{10}^2+n_{11}^2)-\frac2n (n_0^2 +n_1^2) +1$$

Where does this statistic come from? I'm not entirely sure, and the book doesn't explain it's derivation. Normally, $$X=\frac{(Z-\mu)^2}{n^2}$$ for Chi-Squared test ( if i recall correctly), but I don't see how this can result in the expression above. For each $$n_{ij}$$, the approximate value is $$\frac{n_i+n_j-1}{4}$$, and the expected value would be $$\frac{n_i+n_j}2$$, but how do we combine them in such a way that we get the expression for $$X_2$$?

If this belongs in Math, rather than Cryptography, I can happily delete and move it. I just figured since the question is cryptography related, it may receive better attention here.

This is an interesting question. According to page 3-18 of available at NIST here it is a common mistake to think the variance statistic is a traditional chi squared statistic. It is not, due to dependence of the overlapping length 2 windows, so a differential statistic is used.

This statistic has been shown to converge to chi squared by I.J. Good, see the reference on the following page of the linked document, who was involved in the enigma decryption effort with Turing. Thus one must take at least a bitstring of 21 bits.

Here is the discussion • May I inquire, what is the significance of $\frac{\text{Number of Possible Combinations of m-bits}}{\text{Total number of bits}}=\frac{2^m}n$? I would have expected it to be $\frac{2^m}{2^n}=2^{m-n}$, which combinatorics wise, would be the expected frequency? Apr 10 '19 at 4:26
• expected frequency of all $m$ bit patterns* Apr 10 '19 at 4:32
• Since there are $2^m$ $m-$ bit patterns but output string length is $n$, there are $n$ positions for the patterns to start (taken cyclically). If it wasn't cyclic it would have been $n-1$ starting position. Apr 10 '19 at 5:06
• So we divide $2^m$ by $n$, because for each $m$-bit pattern, it has a $\frac1n$ chance of starting at each position in the original string? Apr 10 '19 at 5:07
• yes that is correct Apr 10 '19 at 5:08