Randomness tests

From Wikipedia, the free encyclopedia

There are many practical measures of randomness for a binary sequence. These include measures based on statistical tests, transforms, and complexity or a mixture of these. The use of Hadamard transform to measure randomness was proposed by S. Kak and developed further by Phillips, Yuen, Hopkins, Beth and Dai, Mund, and Marsaglia and Zaman.^[1]

Several of these texts, which are of linear complexity, provide spectral measures of randomness. T. Beth and Z-D. Dai showed that Kolmogorov complexity and linear complexity are practically the same.

These practical tests make it possible to compare and contrast the randomness of strings strings. On probabilistic grounds, all strings, say of length 64, have the same randomness. However, two strings such as those given below:

0101010101010101010101010101010101010101010101010101010101010101

1100100001100001110111101110110011111010010000100101011110010110

appear to have different complexity. The first string admits a short linguistic description, namely "32 repetitions of '01'", which consists of 20 characters, and it can be efficiently constructed out of some basis sequences. The second one has no obvious simple description other than writing down the string itself, which has 64 characters, and it has no comparably efficient basis function representation. Using linear Hadamard spectral tests, the first of these sequences will be found to be of much less randomness than the second one, which agrees with intuition.