Home » Comp. Sci. / Eng., Science » “Using Information Theory Approach to Randomness Testing”

“Using Information Theory Approach to Randomness Testing”

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.

  • Delicious
  • Facebook
  • Reddit
  • StumbleUpon
  • Twitter
  • RSS Feed

Leave a Reply