Runs Test (Menu Analysis \ Analyse Randomness)

Choosing this menu entry opens the dialog Runs Test.

The classic runs test is used to investigate monotonically rising and falling sub-sequences in a number sequence. A "run-up" of length k is understood to mean a sub-sequence Xi; ... ; X(i + k – 1) with X(i + r) <= X(i + r + 1) for all r, 0 <= r <= k - 1. "Run-downs" of length k are defined in similar fashion. Bad generators have a tendency to create runs that are too long.

The runs test now compares the observed frequencies of different length of run with the expected frequencies. For the expected frequency of a run-up of length k in a sequence of length n, the following holds true:

Ek = [(k^2 + k + 1) * (n - k - 1)] / (k + 2)!

As contiguous runs are not independent of each other (a long run is more likely to be followed by a short run than a long run and vice versa), the chi^2 test cannot be immediately used to compare the observed runs with the expected frequencies. Knuth suggests as a simple solution to the problem that every number which comes directly after the end of a run should be discarded. This means that one obtains runs which are independent of each other and whose distribution can be tested using the chi^2 test with (k-1) degrees of freedom. The frequency distribution is divided into k classes, whereby the ith class, (0 <= i <= k - 1), contains runs with length i and class (k-1) contains runs of length >=k. The probabilities for runs of length k are given by

P(run has length k) = k / (k + 1)!

In the case of checking binary sequences, consideration of upward / downward runs simplifies itself to observation of the length of the gaps and blocks. The purpose of the runs test, applied to binary sequences, is to determine whether the number of binary runs of various lengths contained in sequence s behaves as in a genuinely random sequence.

The number of gaps (or blocks) of length i that are expected in a n-bit random sequence is given by

Ei = (n - i + 3) / 2 ^ (i + 2)

Let k be equal to the biggest number i, for which E5 holds true, and let Bi, Gi be the number of blocks and gaps of length i contained in s for all i, 1 <= i <= k. The test statistics used are given by

X4 =sum[i = 1; i = k] (Bi – Ei) ^ 2 / Ei + sum[i = 1; i = k] (Gi – Ei) ^ 2 / Ei

whereby X4 approximates a chi^2 distribution with (2k-2) degrees of freedom.

An example of the Runs Test

By way of illustration, a classical runs test will be carried out on the short binary sequence

s =
00010111 01101101 01111101 11110011 00101111 
00001111 10100100 11001111 11000011 11010001
11010001 00101110 11010100 11000011 01010001
11010110 00110010 10001111 00000111 01000111

of length n = 160 (20 bytes). The significance level is set with alpha = 0.05.

With absolute(s) = 160, in our specific runs test for s, k=3. The expected number of runs of length i = 1, 2, 3 in a 160-bit sequence amounts to Ei = (160 – i + 3) / 2 ^ (i + 2), 1 <= i <= 3.

E1 = 20.25 E2 = 10.0625 E3 = 5

Sequence s contains the following number of blocks Bi and/or gaps Gi of length i = 1, 2, 3:

B1 = 17
G1 = 20
B2 = 9
G2 = 8
B3 = 6
G3 = 7

Let us now determine the test statistics for the runs test:

X4 = [(17 – 20.25) ^ 2 / 20.25] + [(9 – 10.0625) ^ 2 / 10.0625] + [(6 – 5) ^ 2 / 5] +
  [(20 – 20.25) ^ 2 / 20.25] + [(8 – 10.0625) ^ 2 / 10.0625] + [(7 – 5) ^ 2 / 5]
= 2.0596

For a significance level of alpha = 0.05, at (2*3-2) = 4 degrees of freedom, there is the critical area above 9.488. With X4 = 2.0596 <= 9.488, sequence s passes the runs test.

References: Christian Schiestl, Pseudozufallszahlen in der Kryptographie, in Klagenfurt, 1999.