Appendix: Randomness

[Back to Konton2]

What Is Randomness?

There are a few useful ways to define randomness. To make things simpler, consider a sequence of bits: either 0 or 1. Functionally, this is the same as a series of coin flips: either heads or tails.

A sequence of bits could be said to be random if:

• the probability that the next bit will be 1 is exactly 0.5 for every bit, no matter what the earlier part of the sequence looks like.
  This quality is called "independence." Each flip of the coin is independent of the previous flips; the coin can't remember its past. Analyzing the bits already output doesn't make it possible to predict the next bit.
• there is no complete description of the sequence that is smaller than the sequence itself.
  This is the information theory approach to understanding randomness. This is the approach used by compression algorithms, which compress data by creating a description that is smaller than the data itself (impossible if the data is random). Most compression algorithms create descriptions based in classical information theory (developed by Shannon); however, with Algorithmic Information Theory (developed by Chaitin), a "description" can also be an algorithm.

Note that the output of a PRNG can not meet the second condition if Algorithmic Information Theory is taken into account. See Introduction to Pseudo-Random Number Generators (PRNGs) for more information.

All statistical tests of randomness are designed with these two definitions of randomness in mind. The design of such tests is, I've discovered, an interesting subject in its own right. Some tests are almost traditional; others are clever ideas that have occurred to individuals.

For some examples of tests, see my test suite in The Tests in KonStat2.c section of the Konton2 page, Prof. George Marsaglia's famous DIEHARD suite of tests, "Some difficult-to-pass tests of randomness" by Marsaglia and Tsang, and the NIST's test suite.

[Back to Konton2]