27
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ I think the big issue is the meaning of randomness here. Give a precise meaning to it, then you get a good test. The problem with the Kolmogorov complexity, you mention, is that it is a complicated thing to compute. Playing poker is soooo much easier. $\endgroup$
    – Helge
    Commented Sep 2, 2010 at 18:44
  • 4
    $\begingroup$ While an important question, I disagree that the meaning of randomness is the main issue here. Optimizing the computational efficiency of the test, given the sequences it rejects, is not a very subjective question. I imagine at least some thought was given to this in designing the tests, and I'd like to know more about it $\endgroup$
    – Andrew Critch
    Commented Sep 2, 2010 at 19:55
  • $\begingroup$ One thing that strikes me about the first set of tests especially, and the second set to a lesser extent, is that most any human-generated set of "random" numbers will miserably fail the first set of tests (unless of course they are trying to design the sequence to pass these randomness tests, in which case the sequence is decently close to random...) $\endgroup$
    – dvitek
    Commented Sep 3, 2010 at 5:05

3 Answers 3

Reset to default
18
$\begingroup$

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.

Improve this answer
$\endgroup$
12
  • 5
    $\begingroup$ Ed Coffman and I stumbled across the following example when trying to debug a program (for some related stochastic process). Take $k$ points on a circle, and repeat the following steps indefinitely. (a) Add a random point on the circle. (b) Choose a random number $j$ between $1$ and $k+1$, and delete the $j$'th point (starting from the origin). This process should converge to $k$ random points on the circle, so you can easily compute what the expected square of the distance between a random point and its neighbor should be. With our random number generator, we got the wrong answer. $\endgroup$
    – Peter Shor
    Commented Sep 3, 2010 at 1:53
  • 5
    $\begingroup$ (Excessively long comment continued ...) If I remember correctly, we tried several linear congruential random number generators, and they all gave us the wrong answer. (It was close, but statistically significantly wrong in one of the later decimal points; some were better than others.) And again, if I remember correctly, the details of the program are exactly how you would program this in the most obvious way. All of the other types of random number generators we tried worked fine for this problem (but after this experience, I don't trust that they will work for all problems.) $\endgroup$
    – Peter Shor
    Commented Sep 3, 2010 at 1:58
  • 5
    $\begingroup$ (Excessively long comment concluded.) My advice for people doing simulations who want to be exceedingly careful would be to try two different types of psuedorandom number generator, and check that they agree. This is computationally cheaper than using a cryptographically good one. The Mersenne Twister was highly recommended in the Stack Overflow discussion I linked to above, and there are lots of linear congruential ones around, which generally have fairly good statistics. If the two different types give the same answer, you should be very safe. And if they don't, you know something's wrong. $\endgroup$
    – Peter Shor
    Commented Sep 3, 2010 at 2:08
  • 1
    $\begingroup$ I would say that the tests were designed to detect "certain flaws that many pseudorandom number generators contained at the time", rather than fix them. This would allow testing new pseudorandom number generators to make sure that they don't also contain the same sort of mistakes. I had a similar error initially in some cellular automata simulations, where the size of the lattice and a coincidental state recurrence interval multiplied together equaled the 2^32 cycle length of the RND PRNG function in the GNU C-compiler. Better PRNGs exist:e.g. statmath.wu.ac.at/prng/doc/prng.html $\endgroup$
    – sleepless in beantown
    Commented Sep 3, 2010 at 3:13
  • 1
    $\begingroup$ @peter, that's also the same reasoning behind using two hashing algorithms to double check the integrity of a downloaded source package. While there have been a couple of different ways found to successfully find an MD5sum hash collision, finding a way to modify a file which doesn't also change an SHA-1 sum hash has not been discovered. @András Salamon: It's imperative to understand the algorithms underlying PRNGs when using them to avoid a systematic error in using them inappropriately, or in not noticing that there might be too limited an entropy source used to seed them, as with Debian SSL. $\endgroup$
    – sleepless in beantown
    Commented Sep 4, 2010 at 0:25
5
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ That sounds very interesting. What about hardware based random number generation based on chaotic processes, such as when SGI patented and implemented Lavarand, a hardware RNG using an image of a lava lamp as the seed for a PRNG. It's still questionable how chaotic the lava lamp image is; however an improved version LavaRND uses noise from a CCD image sensor as an entropy source followed by multiple SHA hash, rotates, and folds. www.lavarnd.org/what/digital-blender.html $\endgroup$
    – sleepless in beantown
    Commented Sep 3, 2010 at 5:00
  • $\begingroup$ @sleepless: I need to find a really good quote from that chapter. But he does mention a lot of hardware-based solutions and attendant issues, including the fact that a generator based on radio-active decay may miss disintegration that are too close together. The book is aimed at a wide readership, and the chapter covers as much cryptographic applications as sources of randomness, so there must be better references for this out there. $\endgroup$
    – Thierry Zell
    Commented Sep 3, 2010 at 15:20
3
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Kolmogorov complexity can be used to inform an entropy that captures the information in the OP's question as well as the latent information in intrasequence correlations. Without accounting for this, you can shuffle up chunks of a sequence so that the doublet, triplet,...,k-let frequencies match and yet the sequences themselves will be very different globally. $\endgroup$
    – Steve Huntsman
    Commented Sep 2, 2010 at 18:59
  • $\begingroup$ But how do you define Kolmogorov complexity for finite string... $\endgroup$
    – Yaroslav Bulatov
    Commented Sep 15, 2010 at 18:08
  • $\begingroup$ @Yaroslav Isn't Kolmogorov complexity defined in terms of finite objects. According to Li and Vitanyi (arxiv.org/pdf/cs/9901014v1) "the Kolmogorov complexity of a finite object $x$ is the length of the shortest effective binary description of $x$." (Appendix C of the linked manuscript is all about randomness tests and may be relevant to the OP.) $\endgroup$
    – R Hahn
    Commented Sep 26, 2010 at 18:33
  • $\begingroup$ Shortest program for which Turing Machine? Here's a cool one rendell-attic.org/gol/utm/index.htm $\endgroup$
    – Yaroslav Bulatov
    Commented Sep 26, 2010 at 19:35
  • $\begingroup$ Well, the KC is defined for finite strings. But 1.) it is only defined up to an additive constant (translating between Turing machines) and 2.) it isn't computable...yeah, Conway's Life is super fun. $\endgroup$
    – R Hahn
    Commented Sep 26, 2010 at 20:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .