This is a revised summary of my talk from the November 29, 2012 Theory Lunch. I confess to having made an obnoxious amount of errors during that presentation, for which I apologize to all the listeners. This version is hopefully correct.
There are at least two ways of defining randomness. One is about randomness of distributions of objects: this is the subject of the theory of probability. There is another one, which is about randomness of single objects, and is the subject of algorithmic information theory. Consider the following infinite sequences:
The first sequence does not look random at all: it is just a sequence of zeroes. The second one is only slightly more complicated: just a sequence of pairs 01. The third one seems much more complicated, until one notices that it is the sequence of finite nonempty binary strings in length-lexicographic order: 0, 1, 00, 01, 10, 11, 000, 001, and so on. The last one displays no clear pattern.
We are thus tempted to declare the first three strings, nonrandom: and the last one, random. The underlying logic is that the former have short descriptions, while the latter doesn’t seem to.
The formalization of this approach leads to the definition of the Kolmogorov complexity of a finite string. Kolmogorov complexity is defined according to a given computer, which is considered as a partial function which, given a program and an input which are finite strings on a -ary alphabet , possibly returns an output . The Kolmogorov complexity of a string relative to a string with respect to a computer is then defined as the quantity
with the usual convention ; we write for , where is the empty string. A computer is said to be prefix-free, or a Chaitin computer, if for every input the domain of the function is a prefix-free set: in this case, the prefix-free Kolmogorov complexity (also called Chaitin complexity) of with respect to and is indicated by . The following result, proved independently by Andrei Kolmogorov and Ray Solomonoff for ordinary computers and by Chaitin for prefix-free computers, is what makes the entire theory sound.
Invariance Theorem. There exists a (prefix-free) computer with the following property: for every (prefix-free) computer there exists a constant such that, for every program and input such that is defined, there exists a program such that and .
A computer with the property stated in the Invariance Theorem is said to be universal. The Invariance Theorem then states the existence of universal computers, and that the (prefix-free) Kolmogorov complexity according to a universal computer is well defined up to an additive constant. We can thus speak about the (prefix-free) Kolmogorov complexity of a string with respect to an arbitrary, but fixed, universal (prefix-free) computer : which we then omit from the subscript. As an immediate consequence of the Invariance Theorem, there exist constants such that and for every finite word .
We can now define random string according to the notion of prefix-free Kolmogorov complexity. We say that is random if is maximal among the strings of the same length as . Moreover, if and , we say that is -random. It is then possible to prove that, if is -random with , then .
Another way to look at randomness is to consider statistical properties such as the law of large numbers or the law of the iterated logarithm: then we expect that a random string satisfies every “conceivable” statistical property. This, in turn, raises the question of what should the word “conceivable” mean.
The following idea is due to Per Martin-Löf, and dates back to 1966. Consider a set with the following two properties:
- The level sets satisfy for every .
- For every we have .
We call such a set a Martin-Löf test (briefly, M-L test). Recall that is a -ary alphabet: the analogy with statistical test is thus that the level set represents the confidence interval at level with . It is then straightforward to say that a word passes a M-L test at level , if . We thus only have to decide what “conceivable” means, and we do this by requiring to be recursively enumerable. Then the concepts of Chaitin randomness and Martin-Löf randomness are almost equal in the following sense: almost every Chaitin random finite word is ultimately declared random by every M-L test.
Notably, Martin-Löf tests also have a universality property: there exists a M-L test which improves all M-L tests at once, that is, for every there exists such that for every .
The idea of M-L randomness can be adapted to deal with infinite words. However, a plain adaptation is impossible, because just defining an infinite word as random if all its finite prefixes are, means that random infinite words would form a null set. In fact, if is number of consecutive zeroes in from position , then with probability , so that for infinitely many : however, it follows from the Invariance Theorem and the previously observed relation between and that when is Chaitin random.
What is done instead, is to add the further requirement that the tests are sequential, that is, closed by extensions: for every and , if and , then too. We then say that an infinite word fails a sequential M-L test if : which, because of sequentiality, means that none of the finite prefixes of pass . Notably, the class of sequential M-L tests also contains a universal element: there exists a sequential M-L test such that, for every sequential M-L test there exists a constant such that for every . This means that an infinite word passes every sequential M-L test if and only if it passes the universal sequential M-L test : we call these infinite words random.
Such approach to randomness has another advantage: it can be reformulated in a way that allows extension to more general contexts. To see how, let be the -th word over in length-lexicographic order, so that is the empty word, , , , and so on: then is a computable enumeration of a subbase—in fact, a base—of the product topology of . Consider then the enumeration of finite sets of natural numbers, defined by if and only if the -th bit of is 1: the derived sequence defined by is a computable enumeration of a base of the product topology. Moreover, given two sequences , of open sets (recall that r.e. sets are open in the product topology) we say that is -computable if there is a recursively enumerable set such that
where is the standard primitive recursive bijection from to . Finally, let us recall that there is a product measure on the Borel -algebra of , defined via the Hahn-Kolmogorov theorem as the only probability measure satisfying for every .
Theorem. (Hertling and Weihrauch) Let . The following are equivalent.
- is M-L random.
- For every -computable sequence such that for every , we have .
Observe that we require even if is a -ary alphabet: after all, what we expect from , is to pass the test at some level , and we know that if it does, then it does it also at level for every .
Then, given a topological space together with a computable enumeration of a subbase of its topology and a computable measure defined on the Borel -algebra, we can reason as before and define the random elements of the randomness space as those that respect the following condition: for every (attention here!) -computable sequence of open sets such that for every , we have . Recall that is the sequence derived from , as is derived from in the case . Observe that, as such ‘s are countably many and is a measure, the set of the random elements of satisfies . Then we can, for instance, speak about random configurations where is a group satisfying some additional conditions: but this is going to be the topic of another talk.