Wikipedia describes [Kendall and Smith's 1938 statistical randomness tests](http://en.wikipedia.org/wiki/Statistical_randomness#Tests) like this:



> 
> * The **frequency test**, was very basic: checking to make sure that there were roughly the same number of 0s, 1s, 2s, 3s, etc.
> * The **serial test**, did the same thing but for sequences of two digits at a time (00, 01, 02, etc.), comparing their observed frequencies with their hypothetical predictions were they equally distributed.
> * The **poker test**, tested for certain sequences of five numbers at a time (aaaaa, aaaab, aaabb, etc.) based on hands in the game poker.
> * The **gap test**, looked at the distances between zeroes (00 would be a distance of 0, 030 would be a distance of 1, 02250 would be a distance of 3, etc.).
> 
> 
> 


It is not obvious to me that these four particular tests were chosen with any deep understanding of how best to detect nonrandomness. Rather, it seems each one was probably chosen for simplicity.


Well, it's easy to see why early work in the field would be like that. But fast forward to 1995 and George Marsaglia's [Diehard tests](http://en.wikipedia.org/wiki/Diehard_tests) seem, on the surface, just as ad hoc:



> 
> * **Birthday spacings:** Choose random points on a large interval. The spacings between the points should be asymptotically Poisson distributed. The name is based on the birthday paradox.
> * **Overlapping permutations:** Analyze sequences of five consecutive random numbers. The 120 possible orderings should occur with statistically equal probability.
> 
> 
> *(...and so on)*
> 
> 
> 


It is not obvious to me that these tests are really independent (i.e. that none is entirely redundant, rejecting only sequences also rejected by at least one of the other tests), or that there aren't obviously better generalizations of them, much less that they were chosen as a set to try to cover any particular space efficiently.


Ideally, a test suite would be designed to reject as many sequences of low Kolmogorov complexity as possible with minimal computation and false alarms. Is a more theoretical approach to this possible? Why hasn't it happened? —Or is there more to the state of the art than meets the eye?



Why do statistical randomness tests seem so ad hoc?
It's not clear that Marsaglia's tests are really good enough. See [this Stack Overflow discussion](https://stackoverflow.com/questions/584566/pseudo-random-number-generator).


Kolmogorov complexity is not the right criterion for statistical randomness tests, since any pseudorandom sequence has low Kolmogorov complexity. What you really want in a random number generator is for the sequence to be computationally pseudorandom; that is, without knowledge of the seed, no polynomial-time test can distinguish the sequence from a truly random sequence. 


In fact, there are a number of random number generators which are believed to be computationally pseudorandom. Nobody uses these, however, partly because they are computationally too expensive, and partly because of inertia and partly because the existing pseudorandom generators we have are good enough most of the time. A while ago, for one of the most common methods of pseudorandom number generation (linear congruential), I ran into cases where they unexpectedly produced the wrong answer.


Marsaglia's tests were developed over a number of years, and I believe each was designed to detect certain flaws that many pseudorandom number generators contained at the time. Once good-enough pseudorandom number generators were available, nobody bothered creating a more stringent series of tests.


