Randomness testsFrom CryptoDox, The Online Encyclopedia on Cryptography and Information SecurityThere 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 ZD. 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. On probabilistic grounds, all strings, say of length 64, have the same randomness. However, two strings such as those given below:
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. See alsoExternal links
Notes
