Word Frequency Test

Let's say we have the following binary string.

It is obviously not random because it is a concatenation of predetermined bit sequences. Therefore, we must check that the same groups of bits are not repeated too often.

We can use the frequency of "words" to determine if certain bit groups occur too often. There are four possible 2-bit words: 00, 01, 10, and 11. If we assign A, B, C, and D to these words, respectively, then the sequence above transforms into the following sequence.

Now we can run a frequency test on this string with four categories.

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

This sequence isn't quite long enough to see that it's not random, but a longer version of the same sequence does fail the test.

This test, known as the word frequency test, is a significantly more difficult to pass than the runs test. Instead of concatenating predetermined strings, we must use a mathematical process that has seemingly random behavior. One very simple off-the-shelf method for doing this is using a linear congruential generator, which is defined by the following formula.

In this formula, $X_n$ is the current value in the sequence, $a$ is the multiplier, $c$ is the increment, and $m$ is the modulus. $X_0$ is a seed that can be arbitrarily chosen. The word frequency test fails to detect output from a linear congruential generator.

Notes

The word frequency test can give very different results depending on the block size chosen. Larger block sizes don't always result in smaller p-values.