Algorithmic Complexity and Randomness

Algorithmic complexity theory allows as rigorous definition of randomness as is possible. All non-computable strings are algorithmically random (Li and Vitànyi, 1990). They cannot be compressed, by definition; so they contain no detectable overall order, and cannot be distinguished from random strings by any effective statistical test. This notion of randomness can be generalised to finite strings with the notion of effective randomness: a string is effectively random if it cannot be compressed. Random strings do not contain information in earlier parts of the sequence that determines in any way later members of the sequence (or else they could be compressed). The converse is not true. Arbitrarily long substrings of non-computable strings (and, for that matter, incompressible finite strings) can be highly ordered, and therefore computable, but the location and length of these highly ordered substrings cannot be predicted from earlier or later elements in the string. In general, the incompressibility of a string does not imply the incompressibility of its substrings. Since it is possible to change an effectively random string into a compressible string with the change of one digit and yet, intuitively, the change of one digit should not affect whether a string is random, randomness of finite strings of length n is loosely defined as incompressibility within O(logn) (Li and Vitányi, 1990: 201). By far the greatest proportion of strings are random and in the infinite case the set of random strings has measure 1. For strings of n digits, we can rank their randomness according to their algorithmic complexity. Whether or not something is random in the everyday sense will be relative to purposes; some strictly non-random things will be random enough to be termed `random' in certain contexts.

It is worth noting that there are infinite binary strings whose frequency of 1s in the long run is .5, even though the strings are compressible, e.g. an alternation of 1s and 0s. It is likely that the binary expansion of  has equal numbers of 1s and 0s at the infinite limit, though it is also likely that an arbitrary segment would pass a test of statistical randomness, and would, for that matter, be incompressible. The expansion of , however, is entirely predictable, and can be compressed to a short program. If probability requires randomness, probability is not identical to frequency in the long run. It seems unreasonable, e.g. to assign .5 to probability of a 1 at a given point in the sequence because the frequency of 1s in the long run is .5, if the chance of getting a 1 at any point in the sequence can be determined exactly to be 1 or 0. On the other hand, it is true that the long run frequency of a random series must very likely (the exceptions are of measure 0) to converge on the probability. This is the correct form of the well-known law of large numbers.

It is easy to show that a sequence (or anything that can be mapped isomorphically onto a sequence) is non-random. Simply produce a program that compresses the sequence. It is not, in general, possible to show that a sequence is random, however, since one must prove that there is no small program that compresses the sequence. According to the central theorem of algorithmic complexity (see here), for a formal system with complexity n, it is impossible to prove that the complexity of a sequence is higher than n+c, c being a constant depending on the implementation of the system. Any formal system is finite, but a sequence can be arbitrarily large. Hence for any formal system there are sequences whose randomness cannot be proven. This result more or less directly implies Gödel's Incompleteness Theorem, showing a tight connection among information, randomness and metalogic.

It is unclear at this time how algorithmically determined probability compares with subjective, or Bayesian probability, though subjective probability is not unrelated to information. Perhaps, since some versions of information can be characterised in terms of probability, and basic concepts of probability involve information, information theory and all acceptable interpretations of probability will some day be shown to fully coincide at some fundamental level. It is too early to say this with any certainty, however. There are still too many disparate intuitions about each of information and probability that must be reconciled first.