Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is there a reasonable statistic test one can do to standard random number generators (say, one of those that come built in in Python libs) which shows they are not really random?

(By reasonable I mean to exclude silly things like «generate a looong list and see that it is periodic»)

Later: Notice I am looking for a test that fails on standard generators.

share|improve this question
4  
This question is probably more appropriate for the Statistical Analysis forums, where it has been discussed at stats.stackexchange.com/q/375/919 . –  whuber Oct 6 '10 at 13:05
    
boallen.com/random-numbers.html –  anon Oct 6 '10 at 13:06
    
As for the sort of PRNGs that are easy to break with current standard tests, linear congruential generators have so short a period that they are caught quickly, unless one augments them with thing like L'Ecuyer's tricks. –  J. M. Oct 6 '10 at 17:32

2 Answers 2

up vote 7 down vote accepted

The standard reference is Knuth, The Art of Computer Programming, Volume 2, Seminumerical Algorithms. Anyone with serious interest in this topic should read Knuth's extensive exposition here. In addition to theoretical discussion, he presents tests including frequency, serial, gap, poker, coupon collector's, permutation, run, maximum-of-t, collision, birthday spacings, and serial correlation.

Marsaglia's DIEHARD suite of statistical test includes birthday spacings, overlapping permutations, ranks of 31x31 and 32x32 matrices, ranks of 6x8 matrices, monkey tests on 20-bit Words,monkey tests OPSO, OQSO, DNA, count the 1's in a stream of bytes, count the 1's in specific bytes, parking lot, minimum distance, random spheres, squeeze, overlapping sums, runs, and craps.

The NIST Statistical Test Suite includes frequency, block frequency, cumulative sums, runs, long runs,Marsaglia's rank, spectral (based on the Discrete Fourier Transform), nonoverlapping template matchings, overlapping template matchings, Maurer's universal statistical, approximate entropy (based on the work of Pincus, Singer and Kalman), random excursions (due to Baron and Rukhin), Lempel-Ziv complexity, linear complexity, and serial.

As for tests that fail, as Knuth mentions when discussing a typical generator in section 3.6 p. 188 "Caution: The numbers generated by ran_array fail the birthday spacings test of Section 3.3.2J, and they have other deficiencies that sometimes show up in high-resolution simulations (see exercises 3.3.2-31 and 3.3.2-35)".

share|improve this answer

Searches for Marsaglia (George), works by him or about his PRNG tests, would uncover a lot of information. e.g.,

http://en.wikipedia.org/wiki/Diehard_tests

was found by looking for "marsaglia test".

share|improve this answer
1  
cryptanalysis prng –  Jyotirmoy Bhattacharya Oct 6 '10 at 13:14
    
@Jyotirmoy: that is a very good suggestion. –  T.. Oct 6 '10 at 13:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.