Uncommon Descent Serving The Intelligent Design Community

“Using Information Theory Approach to Randomness Testing”

Share
Facebook
Twitter
LinkedIn
Flipboard
Print
Email

Interesting paper on randomness and information theory:

Using Information Theory Approach to Randomness Testing
http://arxiv.org/abs/cs.IT/0504006.
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.

Comments

Leave a Reply