Читать книгу Chance, Calculation and Life - Группа авторов - Страница 19

Sequences are the simplest mathematical infinite objects. We use them to discuss some subtle differences in the quality of randomness. In evaluating the quality of randomness of the following four examples, we employ various tests of randomness for sequences, i.e. formal tests modeling properties or symptoms intuitively associated with randomness.

The Champernowne sequence, 012345678910111213, is random with respect to the statistical test which checks equal frequency – a clearly necessary condition of randomness¹¹. Indeed, the digits 0, 1, 2, …, 9 appear with the right frequency 10^-1, every string of two digits, like 23 or 00 appears with the frequency 10^-2, and by a classical result of Champernowne (1933), every string – say 366647888599991 00200030405060234234 or 00000000000000000000000000000000000 – appears with the frequency 10^{-(length of stnng)} (10^-35 in our examples). Is the condition sufficient to declare the Champernowne sequence random? Of course not. The Champernowne sequence is generated by a very simple algorithm – just concatenate all strings on the alphabet {0, 1, 2, 3, …, 9} in increasing length order and use the lexicographical order for all strings of the same length. This algorithm allows for a prefect prediction of every element of this sequence, ruling out its randomness. A similar situation appears if we concatenate the prime numbers in base 10 obtaining the Copeland-Erdös sequence 235711131719232931374143 (Copeland and Erdös 1946).

Now consider your favorite programing language L and note that each syntactically correct program has an end-marker (end or stop, for example) which makes correct programs self-delimited. We now define the binary halting sequence H(L) = h1h2…hn : enumerate all strings over the alphabet used by L in the same way as we did for the Champernowne sequence and define hi = 1 if the ith string considered as a program stops and hi= 0 otherwise. Most strings are not syntactically correct programs, so they will not halt: only some syntactically correct programs halt. The Church-Turing theorem – on the undecidability of the halting problem (Cooper 2004) – states that there is no algorithm which can correctly calculate (predict) all the bits of the sequence H(L); so from the point of view of this randomness test, the sequence is random. Does H(L) pass the frequency test? The answer is negative.

The Champernowne sequence and the halting sequence are both non-random, because each fails to pass a randomness test. However, each sequence passes a non-trivial random test. The test passed by the Champernowne sequence is “statistical”, more quantitative, and the test passed by the halting sequence is more qualitative. Which sequence is “more random”?

Using the same programing language L we can define the Omega sequence as the binary expansion Ω(L) = ω1ω2… ωn… of the Omega number, the halting probability of L:

It has been proved that the Omega sequence passes both the frequency and the incomputability tests; hence, it is “more random” than the Champernowne, Copeland-Erdös and halting sequences (Calude 2002; Downey and Hirschfeldt 2010). In fact, the Omega sequence passes an infinity of distinct tests of randomness called Martin-Löf tests – technically making it Martin-Löf random (Calude 2002; Downey and Hirschfeldt 2010), one of the most robust and interesting forms of randomness.

Have we finally found the “true” definition of randomness? The answer is negative. A simple way to see it is via the following infinite set of computable correlations present in almost all sequences, including the Omega sequence (Calude and Staiger 2014), but not in all sequences: that is, for almost all infinite sequences, an integer k > 1 exists (depending on the sequence), such that for every m ≥ 1:

In other words, every substring ω_m+1 ω_m+2 … ω_mk has to contain at least one 1, for all m ≥ 1, a “non-randomness” phenomenon no Martin-Löf test can detect. A more general result appears in Calude and Staiger (2014, Theorem 2.2).

So, the quest for a better definition continues! What about considering not just an incremental improvement over the previous definition, but a definition of “true randomness” or “perfect randomness”? If we are confined to just one intuitive meaning of randomness – the lack of correlations – the question becomes: Are there binary infinite sequences with no correlations? The answer is negative, so our quest is doomed to fail: there is no true randomness. We can prove this statement using the Ramsey¹² theory (see Graham and Spencer (1990) and Soifer (2011)) or the algorithmic information theory (Calude 2002).

Here is an illustration of the Ramsey-type argument. Let s₁ … s_n be a binary string. A monochromatic arithmetic progression of length k is a substring s_i s_i+t s_i+2t … s_{i+ (k-1) t}, i ≥ 1 and i + (k-1) t ≤ n with all characters equal (0 or 1) for some t > 0. The string 01100110 contains no arithmetic progression of length 3 because the positions 1, 4, 5, 8 (for 0) and 2, 3, 6, 7 (for 1) do not contain an arithmetic progression of length 3; however, both strings 011001100 and 011001101 do: 1, 5, 9 for 0 and 3, 6, 9 for 1.

THEOREM 1.5.– Van der Waerden. Every infinite binary sequence contains arbitrarily long monochromatic arithmetic progressions.

This is one of the many results in Ramsey theory (Soifer 2011): it shows that in any sequence there are arbitrary long simple correlations. We note the power of this type of result: the property stated is true for any sequence (in contrast with typical results in probability theory where the property is true for almost all sequences). Graham and Spencer, well-known experts in this field, subtitled their Scientific American presentation of Ramsey Theory (Graham and Spencer 1990) with the following sentence:

Complete disorder is an impossibility. Every large¹³ set of numbers, points or objects necessarily contains a highly regular pattern.

Even if “true randomness” does not exist, can our intuition on randomness be cast in more rigorous terms? Randomness plays an essential role in probability theory, the mathematical calculus of random events. Kolmogorov axiomatic probability theory assigns probabilities to sets of outcomes and shows how to calculate with such probabilities; it assumes randomness, but does not distinguish between individually random and non-random elements. So, we are led to ask: is it possible to study classes of random sequences with precise “randomness/symptoms” of randomness? So far we have discussed two symptoms of randomness: statistical frequency and incomputability. More general symptoms are unpredictability (of which incomputability is a necessary but not sufficient form), incompressibility and typicality.

Algorithmic information theory (AIT) (Calude 2002; Downey and Hirschfeldt 2010), which was developed in the 1960s, provides a close analysis of randomness for sequences of numbers, either given by an abstract or a concrete (machine) computation, or produced by a series of physical measurements. By this, it provides a unique tool for a comparative analysis between different forms of randomness. AIT also shows that there is no infinite sequence passing all tests of randomness, so another proof that “true randomness” does not exist.

As we can guess from the discussion of the four sequences above, randomness can be refuted, but cannot be mathematically proved: we can never be sure that a sequence is “random”, there are only forms and degrees of randomness (Calude 2002; Downey and Hirschfeldt 2010).

Finally, note that similarly to randomness in classical dynamics, which was made intelligible by Poincaré’s negative result, AIT is also rooted in a negative result: Gödel’s incompleteness theorem. As recalled above, a random sequence is a highly incomputable sequence. That is, algorithmic randomness is in a certain sense a refinement of Gödel’s undecidability, as it gives a fine hierarchy of incomputable sets that may be related, as we will hint below, to relevant forms of randomness in natural sciences.