Abstract
The properties of statistical procedures based on occurrences of aperiodic patterns in a random text are summarized. Accurate asymptotic formulas for the expected value of the number of aperiodic words occurring a given number of times and for the covariance matrix are given. The form of the optimal linear test based on these statistics is established. These procedures are applied to testing for the randomness of a string of binary digits originating from block ciphers, US government-approved random number generators or classical transcendental numbers.
MSC 2000 Subject Classifications :
Acknowledgements
Z. Volkovich is also affiliated with the Department of Mathematics and Statistics, University of Maryland at Baltimore County. A. L. Rukhin's research was supported by a grant no. MSPF-02G-068 from the National Security Agency. The authors are grateful to the referee for his helpful comments and to J. Soto and A. Roginsky for their interesting discussion.