Using information theory approach to randomness testing

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 H 0 that a given bit sequence is generated by Bernoulli source with equal probabilities o...

Full description

Saved in:
Bibliographic Details
Published in:Journal of statistical planning and inference 2005-07, Vol.133 (1), p.95-110
Main Authors: Ryabko, B.Ya, Monarev, V.A.
Format: Article
Language:English
Subjects:
Hypothesis testing
Information Theory
Random number generator
Random number testing
Randomness testing
Shannon entropy
Universal code
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 H 0 that a given bit sequence is generated by Bernoulli source with equal probabilities of 0 and 1 and the alternative hypothesis H 1 that the sequence is generated by a stationary and ergodic source which differs from the source under H 0. We show that data compression methods can be used as a basis for such testing and describe two new tests for randomness, which are based on ideas of universal coding. Known statistical tests and suggested ones are applied for testing PRNGs. Those experiments show that the power of the new tests is greater than of many known algorithms.
ISSN:0378-3758
1873-1171
DOI:10.1016/j.jspi.2004.02.010