Randomness tests

Randomness tests (or tests of randomness), in data evaluation, are used to analyze the distribution pattern of a set of data. In stochastic modeling, as in some computer simulations, the expected random input data can be verified to show that tests were performed using randomized data. In some cases, data reveals an obvious non-random pattern, as with so-called "runs in the data" (such as expecting random 0-9 but finding "4 3 2 1 0 4 3 2 1..." and rarely going above 4). If a selected set of data fails the tests, then parameters can be changed or other randomized data can be used which does pass the tests for randomness.

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. [Terry Ritter, Randomness tests: a literature survey. http://www.ciphersbyritter.com/RES/RANDTEST.HTM ]

Several of these tests, 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. On probabilistic grounds, all strings, say of length 64, have the same randomness. However, two strings such as those given below:

: string 1: 0101010101010101010101010101010101010101010101010101010101010101

: string 2: 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.

ee also

*Diehard tests
*Statistical randomness

External links

* George Marsaglia, Wai Wan Tsang, [http://www.jstatsoft.org/v07/i03/paper "Some Difficult-to-pass Tests of Randomness,"] Journal of Statistical Software, Volume 7, 2002, Issue 3.

* [http://www.phy.duke.edu/~rgb/General/dieharder.php DieHarder: A Random Number Test Suite]

* [http://www.cacert.at/random/ Online randomness test]

Notes