# 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.

• 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? – Shinaolord Apr 10 at 4:26
• expected frequency of all $m$ bit patterns* – Shinaolord Apr 10 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. – kodlu Apr 10 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? – Shinaolord Apr 10 at 5:07