Serial Test (Menu Analysis \ Analyse Randomness)

Choosing this menu entry opens the dialog Serial Test.

This test examines whether pairs of consecutive numbers are equally distributed and thus checks their independence of each other.

In the case of a binary sequence s, the test determines whether the probability, that consecutive elements in the sequence are the same or different, is equal or not. This is an index of whether every bit is independent from its immediate predecessor or not. The number of sub-sequences 00, 01, 10, 11 in s should approach the number expected if a number sequence is truly random. Since under this test two bits are always examined together, the test is also known in the literature as the two-bit test.

Let n0 and n1 be the numbers of zeros and ones, respectively, in s; and let n00, n01, n10 and n11 be the relevant numbers of sub-sequences 00, 01, 10, 11 in s. As the sub-sequences overlap, the following applies (with n = bit length of s):

n00 + n01 + n10 + n11 = n - 1

The test statistics used are given by

X2 = [4 / (n –1)] * (n00^2 + n01^2 + n10^2 + n11^2) – (2 / n) * (n0^2 + n1^2) + 1,

whereby X2 approaches a chi^2 distribution with two degrees of freedom, provided that n>=21.

In the serial test dialog it is possible to determine significance level, offset and test length.

Example of the Serial Test

By way of illustration, a classical serial 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.

The number of overlapping pairs 00, 01, 10 and 11 in s is

n00 = 35 n10 = 38
n01 = 39 n11 = 47

The test statistics for the two-bit test is calculated by

X2 = [4 / (160 –1)] * (35^2 + 39^2 + 38^2 + 47^2) – (2 / 160) * (74^2 + 86^2) + 1 = 1.081

The threshold for X2 in a chi^2 distribution with two degrees of freedom and a significance level of alpha = 0.05 is given by 5.991.

With X2 = 1.081 <= 5.991, sequence s passes the serial test.

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