Block Frequency Test

Let's say we have the following binary string.

It is obviously not random since the zeros and ones are not mixed together. Therefore, we must check that there are roughly an equal number of zeros and ones in each part of the string. Let's break the string into two substrings.

A useful property of $\chi^{2}$ variables with $m$ and $n$ degrees of freedom is that their sum is also a $\chi^{2}$ variable with $m+n$ degrees of freedom.

Therefore, in the example above, we get the following $\chi^{2}$ value.

The p-value for a chi-squared of 20 with 2 degrees of freedom is 0.0000, which is less than 0.01, indicating that this sequence of numbers was probably not randomly generated.

This test, known as the block frequency test, is a slightly better version of the basic frequency test. However, it fails on the following binary string that was obviously not randomly generated.

Notes

The technique of dividing the input string into "blocks" and testing each block independently works for any test of randomness that uses the chi-squared statistic.

The block frequency test, as implemented in this guide, doesn't work correctly with small blocks on large input strings. This is due to a floating-point precision issue caused by having a large number of degrees of freedom. (One of the numbers in the calculation of the p-value becomes NaN.)