Why do statistical randomness tests seem so ad hoc? - MathOverflow

Why do statistical randomness tests seem so ad hoc?

2010-09-02T17:53:09Z

Wikipedia describes Kendall and Smith's 1938 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 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?

Answer by Yaroslav Bulatov for Why do statistical randomness tests seem so ad hoc?

2010-09-02T18:39:09Z

Kolmogorov complexity is a universal quantity for infinite strings. But since randomness tests are run on finite strings, particular choice of architecture or encoding will play a large role in how the strings will be ordered. A goal of good randomness test designer is to choose an encoding such that strings coming from known random sources (like random.org) are deemed more complex than strings coming from known non-random sources (like pseudo-random generators). Good tests incorporate knowledge of how typical non-random strings are generated, hence the apparent ad hockery.

Answer by Thierry Zell for Why do statistical randomness tests seem so ad hoc?

2010-09-02T19:04:56Z

In Chapter 2 of the book Group Theory in the Bedroom, Brian Hayes mentions how difficult it is to extract "true" randomness from the physical world (including constructing tables of random numbers the old-fashioned way, and how Fisher and Yates had to "fix" their tables in post-processing to re-balance the digits, causing their colleagues to comment: "a procedure of this kind may cause others, as it did us, some misgivings").

The point he makes is that physical randomness is hard to achieve, because even if your source is truly random (whatever that means), the measurement process is apt to introduce bias, so that pseudo-random generators can out-perform physical random sources on many statistical test. [I'll add a more precise page reference as soon as I can find it.]

Given this state of affairs, the ideal test suite seems unlikely to exist. I would agree with you that less ad-hoc tests do seem desirable, though.

Answer by Peter Shor for Why do statistical randomness tests seem so ad hoc?

2010-09-02T23:11:39Z

It's not clear that Marsaglia's tests are really good enough. See this Stack Overflow discussion.

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.