“Using Information Theory Approach to Randomness Testing”
|April 23, 2005||Posted by William Dembski under Comp. Sci. / Eng., Science|
Interesting paper on randomness and information theory:
Using Information Theory Approach to Randomness Testing
B. Ya. Ryabko and V.A. Monarev
ABSTRACT: We address the problem of detecting deviations of binary sequence from randomness,which is very important for random number (RNG) and pseudorandom number generators (PRNG). Namely, we consider a null hypothesis H0 that a given bit sequence is generated by Bernoulli source with equal probabilities of 0 and 1 and the alternative hypoth esis H1 that the sequence is generated by a stationary and ergodic source which differs from the source under H0. We show that data compression methods can be used as a basis for such testing and de- scribe two new tests for randomness, which are based on ideas of universal coding. Known statistical tests and suggested ones are ap- plied for testing PRNGs. Those experiments show that the power of the new tests is greater than of many known algorithms.
KEYWORDS: Hypothesis testing, Randomness testing, Random number testing, Universal code, Information Theory, Random number generator, Shannon entropy.