Randomness tests
Encyclopedia
The issue of randomness is an important philosophical and theoretical question.
Many random number generators in use today generate what are called "random sequences" but they are actually the result of prescribed algorithms and so they are called pseudo-random number generators.
These generators do not always generate sequences which are sufficiently random and generate very repetitive patterns such as the infamous RANDU which fails many randomness tests dramatically including the Spectral Test.
The use of an ill-conceived random number generator will result in invalid experiments, due to the lack of randomness.
Tests for randomness are not restricted to analysing the output of pseudo-random number generators, they can also be used to determine whether a set of data has a recognisable pattern to it.
For example Wolfram used randomness tests on the output of Rule 30
to examine its potential for generating random numbers
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 simulation
s, 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.
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:
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 (see Hadamard transform
), the first of these sequences will be found to be of much less randomness than the second one, which agrees with intuition.
Many random number generators in use today generate what are called "random sequences" but they are actually the result of prescribed algorithms and so they are called pseudo-random number generators.
These generators do not always generate sequences which are sufficiently random and generate very repetitive patterns such as the infamous RANDU which fails many randomness tests dramatically including the Spectral Test.
The use of an ill-conceived random number generator will result in invalid experiments, due to the lack of randomness.
Tests for randomness are not restricted to analysing the output of pseudo-random number generators, they can also be used to determine whether a set of data has a recognisable pattern to it.
For example Wolfram used randomness tests on the output of Rule 30
Rule 30
Rule 30 is a one-dimensional binary cellular automaton rule introduced by Stephen Wolfram in 1983. Wolfram describes it as being his "all-time favourite rule" and details it in his book, A New Kind of Science...
to examine its potential for generating random numbers
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 simulation
Computer simulation
A computer simulation, a computer model, or a computational model is a computer program, or network of computers, that attempts to simulate an abstract model of a particular system...
s, 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
Randomness
Randomness has somewhat differing meanings as used in various fields. It also has common meanings which are connected to the notion of predictability of events....
for a binary sequence. These include measures based on statistical tests, transforms
Hadamard transform
The Hadamard transform is an example of a generalized class of Fourier transforms...
, and complexity
Complexity
In general usage, complexity tends to be used to characterize something with many parts in intricate arrangement. The study of these complex linkages is the main goal of complex systems theory. In science there are at this time a number of approaches to characterizing complexity, many of which are...
or a mixture of these. The use of Hadamard transform
Hadamard transform
The Hadamard transform is an example of a generalized class of Fourier transforms...
to measure randomness was proposed by S. Kak
Subhash Kak
Subhash Kak is an Indian American computer scientist, most notable for his controversial Indological publications on history, the philosophy of science, ancient astronomy, and the history of mathematics...
and developed further by Phillips, Yuen, Hopkins, Beth and Dai, Mund, and Marsaglia
George Marsaglia
George Marsaglia was an American mathematician and computer scientist. He established the lattice structure of congruential random number generators in the paper "Random numbers fall mainly in the planes". This phenomenon is sometimes called the Marsaglia effect...
and Zaman.
Several of these tests, which are of linear complexity, provide spectral measures of randomness. T. Beth and Z-D. Dai showed that Kolmogorov complexity
Kolmogorov complexity
In algorithmic information theory , the Kolmogorov complexity of an object, such as a piece of text, is a measure of the computational resources needed to specify the object...
and linear complexity are practically the same.
These practical tests make it possible to compare and contrast the randomness of strings
String (computer science)
In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....
. 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
Basis function
In mathematics, a basis function is an element of a particular basis for a function space. Every continuous function in the function space can be represented as a linear combination of basis functions, just as every vector in a vector space can be represented as a linear combination of basis...
representation. Using linear Hadamard spectral tests (see Hadamard transform
Hadamard transform
The Hadamard transform is an example of a generalized class of Fourier transforms...
), the first of these sequences will be found to be of much less randomness than the second one, which agrees with intuition.
See also
- Diehard testsDiehard testsThe diehard tests are a battery of statistical tests for measuring the quality of a random number generator. They were developed by George Marsaglia over several years and first published in 1995 on a CD-ROM of random numbers.These are the tests:...
- TestU01TestU01TestU01 is a software library, implemented in the ANSI C language, and offering a collection of utilities for the empirical statistical testing of uniform random number generators....
- RandomnessRandomnessRandomness has somewhat differing meanings as used in various fields. It also has common meanings which are connected to the notion of predictability of events....
- Statistical randomnessStatistical randomnessA numeric sequence is said to be statistically random when it contains no recognizable patterns or regularities; sequences such as the results of an ideal dice roll, or the digits of π exhibit statistical randomness....
- Algorithmically random sequenceAlgorithmically random sequenceIntuitively, an algorithmically random sequence is an infinite sequence ofbinary digits that appears random to any algorithm...
- Seven states of randomnessSeven states of randomnessThe seven states of randomness in probability theory, fractals and risk analysis are extensions of the concept of normal distribution. These seven states were first introduced in by Benoît Mandelbrot in his 1997 book Fractals and scaling in finance which applied fractal analysis to the study of...
- Statistical randomness
External links
- George MarsagliaGeorge MarsagliaGeorge Marsaglia was an American mathematician and computer scientist. He established the lattice structure of congruential random number generators in the paper "Random numbers fall mainly in the planes". This phenomenon is sometimes called the Marsaglia effect...
, Wai Wan Tsang, Some Difficult-to-pass Tests of Randomness, Journal of Statistical Software, Volume 7, 2002, Issue 3. - DieHarder: A Random Number Test Suite
- Online randomness test