Theoretical interlude---What is randomness? My definitions

Finally, THE definition of randomness!! Warning to the reader!

This is the basic, new fundamental idea in AIT, and it's the source of the randomness that I discovered in the heart of pure mathematics, the randomness that Gödel and Turing encountered without realizing it! This one idea is the raison d'être of AIT. I want to understand randomness, I want to formulate the theory that defines it as well as I can.

But in Part III I'll temporarily introduce a number of variant definitions just in order to show that they're equivalent!

Don't get confused!

What is randomness? Overview of six variant definitions

In this part we discuss five, really six, definitions of randomness: my two for bit strings (using absolute and relative complexity, respectively), and four for infinite binary sequences or, equivalently, for base-two real numbers. Two of the definitions for random real are statistical (Martin-Löf's and Solovay's), and two involve program size (my two: Chaitin and strong Chaitin randomness).

It turns out that the two definitions of a random bit string are equivalent, and that the four definitions for random reals are equivalent. That's a very good sign; it confirms that we've captured the correct concept!

In this chapter we'll show that my two definitions of random bit string are equivalent, but it'll take us all of Part III to prove that the four definitions of a random real number are equivalent.

The common thread of my definitions is, as I said, that incompressible implies typical, and that a ``random'' string is one that has ``close to'' the highest possible complexity. So it turns out that a random n-bit string β is one for which H(β) is close to n + H(n), which is the greatest possible and also the typical complexity of an n-bit string.

As the complexity of H(β) drops below this β becomes less and less random; it is a matter of degree. [If you must pick a cutoff, it should be at around H(β) = n.]

For random infinite binary sequences x, we consider the complexity H(x_n) of the first n bits of x as a function of n, and we'll demand that x_n always be random, as random as possible. Due, for example, to long runs of consecutive 1's and 0's, with probability one the complexity of some initial segments of x will have to dip well below n + H(n), so we cannot be as demanding as we were in the case of finite randomness.

It turns out that the correct cutoff is to allow dips of about H(n), so that we'll define x to be Chaitin random if and only if there is a c such that H(x_n) > n − c for all n.

This definition of randomness for infinite binary sequences x is of an all-or-nothing character, and it is satisfied by ``most'' infinite binary sequences x, that is, with probability one. In particular, it's easy to see that the halting probability Ω is Chaitin random; that was one of the reasons that I picked this particular definition!

So the notion of program-size complexity provides a unified view of randomness that works both for bit strings and for infinite binary sequences. I believe Chaitin randomness to be a more fundamental concept than statistical randomness, e.g. because program-size irreducibility yields statistical randomness as a corollary in the infinite case, and it also applies to bit strings, where Martin-Löf's and Solovay's statistical definitions do not apply.

When is an n-bit string β random?

because we can easily convert a program for (n  β) into one for β and vice versa by adding an appropriate prefix. And according to our fundamental theorem on relative complexity proved in the previous chapter,

Therefore,

And because the complexity of an n-bit string β given n is obviously bounded by n + c, it follows that

which we already knew in Part I.

So we have a beautifully simple relationship between the absolute complexity H(β) of an n-bit string β and its relative complexity H(β|n) given n. [It's another confirmation that we chose the right definition of relative complexity! It's the basic fact governing the randomness of n-bit strings. It opens the door to all our deeper understanding of randomness. With its help everything will become clear.]

It follows that the most complex or ``random'' n-bit strings β are those for which the complexity of β is very close to n + H(n),

or, equivalently, those for which the complexity of β given n is very close to n,

And most n-bit strings are random. In fact, a fraction of at most 1/2^{k − c} of the n-bit strings β satisfy

or, equivalently,

Why? Simply because there are 2ⁿ n-bit strings β but there are fewer than 2^n−k programs for β given n with size < n−k bits [since ∑_{j < n−k} 2^j = 2^n−k−1].

In other words,

For bit strings, randomness is a matter of degree: the most random ones have complexity very close to the maximum, and as their complexity drops, they become less and less random. But for infinite binary sequences, as we shall see, it's all or nothing!

The basic property of finite randomness is this: if an n-bit string β is unusual, if it stands out from the crowd in any way, if it has any special distinguishing property P, then it isn't random. Why is this?

Because if β is a member of a small set (the set of all strings having some unusual, atypical property P), then a simpler way to specify β is by indicating its unusual property P (via a program for enumerating all strings that have that property), and then give β's position or index κ (a small number, much less than 2ⁿ) in that enumeration. If the number of bits needed to specify the distinguishing property P is not greater than the number of bits saved because the property is unusual, i.e., if the complexity H(P) of the distinguishing property is substantially less than n − log₂ κ, then we win; we've found a way to specify β using much less than n bits!

In other words, we're given n for free, and a program that given n enumerates all n-bit strings β with property P, and an integer κ that tells us at what position in this enumeration the particular β that we're interested in appears.

Let's restate this.

Given n, it normally takes n bits to specify an n-bit binary string β. But if β has an unusual property P, and there are only about 2^m < 2ⁿ n-bit strings with this unusual property P, and if it takes much less than n−m bits to specify P, then we may be able to compress β by specifying its unusual property P and which n-bit string with this property β is (about m bits). The result is a program for β given n with about m + H(P) bits, which is much less than m + n−m = n bits.

Mutual information again

Let's look at the mutual complexity of n-bit strings. We consider H(α:β), where α and β are both n-bit strings. How high and how low can we make the mutual information H(α:β)?

Well, to get the lowest possible mutual information for n-bit strings, let α = 0ⁿ be the string of n 0's, and let β = 1ⁿ be the string of n 1's. Then the mutual information is H(n) + O(1), the lowest possible.

[Why must two n-bit strings α, β always have mutual information H(α:β) ≥ H(n) − c? Well,

But obviously

(relativised subadditivity). So

which was to be proved.]

But here is a more interesting example, [Taken from my paper ``Toward a mathematical definition of `life','' in R. Levine and M. Tribus, The Maximum Entropy Formalism, MIT Press, 1979, pp. 477-498.] in which we minimize the mutual information H(α:β) while maximizing the individual information contents H(α) and H(β) of two n-bit strings α and β. Consider a highly random 2n-bit string γ, and let α and β be, respectively, the first n bits of γ and the last n bits of γ. So, by hypothesis,

and H(γ) is very close, within a few bits of, 2n + H(2n).

Now on the one hand we have

[Why? Because we can easily convert a program for n into one for 2n, and vice versa, just by adding a suitable prefix.] On the other hand H(α) must be within a few bits of n + H(n), and H(β) must also be within a few bits of n + H(n). Why? Because

That is, start by computing n, then compute α from n and β from n. These n-relative programs for α and β must both have size very close to n; otherwise we get a program for γ that is too small, that is, that is much smaller than 2n + H(2n) = 2n + H(n) + O(1) bits in size.

It follows that the two halves α and β of a 2n-bit string γ that has close to the maximum possible complexity, simultaneously have H(α) very close to n + H(n), H(β) very close to n + H(n), and H(α,β) very close to 2n + H(n). Thus

which was to be proved.

And to maximize the mutual information of two n-bit strings, just let α be an n-bit string with very close to the maximum possible complexity n + H(n), and let β be α or the bit by bit complement of α. Then

The number of n-bit strings with maximum complexity is random

Consider the set of all n-bit strings β. Let h_n be the maximum complexity of an n-bit string:

And let κ_n be the n-bit base-two numeral for the number of n-bit strings β with exactly the maximum possible complexity h_n:

There must be at least one string β that achieves this maximum. If there should happen to be exactly 2ⁿ such β, then we will let κ_n ``wrap around'' and be the n-bit string consisting entirely of 0's.

We know that

and let's define Δ_n to be their difference

and σ_n to be the sign of this difference, either a plus or a minus.

Now consider the following n-relative computation. We're given for free n*, a minimum-size program for n, and a program p consisting of a suitable prefix followed by Δ_n and σ_n and a minimum-size program to get κ_n from n. From this we first get n = U(n*) and H(n) = |n*|. Then we add n and H(n), and we are within O(1) of h_n. Next we use Δ_n and σ_n, which are O(1) bits of information, to ``correct'' n + H(n) and get the exact value of h_n, the maximum possible complexity of an n-bit string. Next we calculate κ_n from n*; the program that we are given for doing this is exactly H(κ_n|n) bits long.

At this point we've read in all of p; it's H(κ_n|n) + O(1) bits long.

Then by systematically running more and more programs on U for more and more time, we start determining better and better upper bounds on the complexity H(β) of each n-bit string β, until we are sure that we have all 2ⁿ − κ_n n-bit strings β with H(β) < h_n. At that point the remaining κ_n n-bit strings β must all have precisely the maximum possible complexity H(β) = h_n. Pick one, let's call it β_max,

and return β_max as the value of this computation.

So what we have here is an

bit program to calculate from n* an n-bit string β_max with

It follows that

and so

Therefore κ_n is itself an n-bit string with almost exactly the maximum possible complexity! It's full of valuable information!

From this it is easy to see that

For if there were an unbounded number of initial 0 bits at the beginning of the bit string κ_n, then the complexity of κ_n would drop substantially, which is impossible. Indeed, j initial 0's would reduce κ_n's complexity by about j − log₂ j bits.

So we have shown that κ_n, the number of n-bit strings β with exactly the maximum possible complexity H(β) = h_n, is large because it is a random n-bit number! κ_n has to be at least a fixed fraction of all the n-bit strings, it has to be greater than 2^{n − c}.

In order to prove this assertion, which involves only absolute complexity, we had to make a foray into the world of relative complexity. I hope you enjoyed reading it as much as I enjoyed discovering it! I think it's a cute example. And it is good preparation for our future discussion of the fact that the halting probability Ω is a random real number. In fact, the κ_n are like finite versions of Ω. Ω sort of combines all of the κ_n into a single real number.

By the way, it also follows that the number of 0's and 1's in the bit string κ_n is nearly the same, otherwise κ_n could be compressed. In fact, if the relative frequency of 0's is p and the relative frequency of 1's is q and n is large, then κ_n can be compressed from n bits to about (−p log₂ p −q log₂ q) × n bits. [Actually it's better to fix an ε > 0 and show that for large n, any n-bit string with relative frequencies of 0's and 1's that differ from 1/2 by more than ε can be compressed into a program whose size is at most about n × (−p log₂ p −q log₂ q) bits, where p = 1/2 − ε and q = 1/2 + ε. I.e., the n-bit string is compressed into a program a fixed percentage smaller (depending only on ε).] Can you figure this out for yourself? Look at base-two logarithms of binomial coefficients and use Stirling's approximation:

Using AIT to prove that there are infinitely many prime numbers

Consider a positive integer n, and suppose on the contrary that there are only finitely many prime numbers, in fact, exactly k of them: p₀,...,p_k−1. Then n can always be expressed via a prime factorization of the form

And if we are given the exponents of the k primes in this factorization, then we can calculate n. So, using the subadditivity of program-size complexity, we have

But on the one hand, each exponent e_i is ≤ log₂ n and thus

On the other hand, for most n, for random n, [Definition: An integer is random iff its base-two numeral is a random bit string.]

So we conclude that for random n,

which is impossible, since the logarithm grows much faster than the iterated logarithm. Therefore our assumption that there were exactly k primes must be incorrect, no matter what the value of k is. Therefore the number of primes must be infinite! [Please note that in this proof we did not use the fact that the prime factorization is unique. That is why I started with

instead of with

]

This amusing proof of Euclid's result that there are infinitely many primes certainly feels like it belongs to the new millennium! [It was first published as an appendix in my paper ``Toward a mathematical definition of `life','' in R. Levine and M. Tribus, The Maximum Entropy Formalism, MIT Press, 1979, pp. 477-498. It was more widely seen in my paper ``Gödel's theorem and information,'' International Journal of Theoretical Physics 22 (1982), pp. 941-954.] It's very different from the proof known to the ancient Greeks, which is that if there were only k primes p_i, then the expression

would also have to be prime, which is impossible.

When is an infinite binary sequence random? Random reals---My definition

and

aren't different, but the corresponding infinite binary sequences certainly are! But this will not be a problem.

We saw at the beginning of this chapter that for an n-bit string β

In other words, there's a c such that (the probability that the complexity of an n-bit string is less than or equal to n + H(n) − k) is less than or equal to 2^−k+c.

Substituting H(n) + c for k, and substituting x_n, the first n bits of an infinite binary sequence x, for β, gives us

Let's sum this over all positive integers n. That gives us

It follows that with probability one,

is only the case finitely often.

[Why? Well, this is a special case of what Feller [W. Feller, An Introduction to Probability Theory and Its Applications, Vol. 1, Wiley, 1950.] calls the Borel-Cantelli lemma, which states that if

converges, then with probability one only finitely many of the events A_n can occur. How come? Well, just look at the tails of this convergent infinite series. Since this series converges, we can get the tail to be arbitrarily small by going out far enough. So for any real ε > 0, there will be an integer N such that

Hence the probability that any of the events A_n occur for n ≥ N is less than ε, and can be made arbitrarily small, and the probability that infinitely many of the A_n occur is less than ε for every ε > 0 and is therefore zero.]

It follows that with probability one there must be a c' depending on x such that for all n,

I'll take this to be my program-size irreducibility definition of a random real, more precisely, of what I'll call a Chaitin-random real.

Actually, repeating this reasoning again and again, each time with a different complexity cutoff, also shows that with probability one it must be the case that

That is, with probability one, H(x_n) − n → ∞, H(x_n) − n goes to infinity. I'll call this strong Chaitin randomness. But we'll postpone considering strong Chaitin randomness until the last chapter of Part III, where we'll show that there's actually a complexity gap and that if

then

So Chaitin and strong Chaitin randomness are actually equivalent; but that's not at all obvious.

The halting probability Ω is Chaitin random

Let's consider the first N bits of the binary expansion of Ω, the halting probability of our universal self-delimiting binary computer U, a real number between 0 and 1. And for the purposes of this discussion, let me say that if I have to choose between

and

I prefer the binary expansion for Ω with infinitely many 1's.

Let's suppose we know the halting probability to within one part in 2^N, in other words, that we've been told its numerical value with an accuracy of 2^−N. More precisely, we truncate Ω, we don't round it off. So I'll define Ω_N to be the first N bits of the binary expansion of Ω with infinitely many 1's, which ensures that Ω > Ω_N, that Ω is strictly greater than Ω_N, which is important for everything to work.

The crucial fact is that Ω_N settles the halting problem for U(p) for all programs p up to N bits in size. In fact, there is a prefix π such that

In other words, by slapping on a prefix we can make any program to calculate the first N bits of the halting probability into a program for computing a list of all the S-expressions with complexity ≤ N. But this list itself cannot have complexity ≤ N, because it cannot be contained in itself!

Therefore taking p to be a minimum-size program for Ω_N, we have

So

and Ω is Chaitin random. The proof is a bit like the one that H(κ_n|n) = n + O(1); that was a warm-up exercise for this.

You systematically run more and more programs on U for more and more time, and get better and better lower bounds on the halting probability for U. As soon as the first N bits of the halting probability are correct (that is, the same as Ω_N), you know all ≤ N bit programs for U that halt!

Yes indeed, you can compute Ω in the limit from below. But---unless you're given Ω_N!---you never know how close you are, there is no ``computable regulator of convergence.''

Can you work through the details on your own and write the prefix π in LISP? If so, what value do you get for c? If, God forbid, you give up, or, what's more commendable, if you want to compare your answer with mine to see if you did a better job, see The Limits of Mathematics for the detailed proof that

In the next three chapters we'll deduce from this lower bound on H(Ω_N), which states that Ω is Chaitin random, that Ω is also Martin-Löf and Solovay random (statistically random) and finally is strong Chaitin random, so that in fact H(Ω_N) − N   →   ∞. This will keep us busy for the rest of Part III, and to do it we'll have to figure out how to do a little bit of measure theory on the computer.

Should you stop reading here?

The reason I go on with three more (misleading) chapters in Part III after this one, is (a) a new concept feels slightly more comfortable if it keeps company, if it connects with old (even obsolete!) concepts! (b) I need the detour through Martin-Löf and Solovay to prove that strong Chaitin randomness is equivalent to my main definition, Chaitin randomness. But I don't use strong Chaitin randomness anywhere, I just like the information that it gives me about Ω. I challenge the reader to find a simple, direct proof, and eliminate any need for ever introducing strong Chaitin randomness. ``Strong'' Chaitin randomness is really an expression of weakness, of the fact that I don't (yet) have an immediate proof that this is equivalent to my main randomness definition. I'm counting on you to rectify this!

Similarly, (c) I do need Solovay randomness to show that very sparse infinite subsets of the bits of Ω must have 0's and 1's with equal limiting relative frequency. A straight-forward program-size compression argument will not do. [If a fixed percentage of the bits of Ω are selected, then a straight-forward program-size compression argument does work.] But that may just be my fault! Can you fix this by giving a direct proof? Then AIT will be free from any dependence on old, dying ideas!

Do the research that will obviate any need for me to temporarily introduce variant definitions of randomness! These direct proofs avoiding Martin-Löf, Solovay, and strong Chaitin randomness, will no doubt be obtained by unraveling the equivalence proofs linking these concepts with Chaitin randomness that I present in the remaining chapters of Part III, and extracting the central idea from each proof. To work!

Exercises

1. Prove that the complexity of a minimum-size program p is almost the same as its size. I.e., if U(p) = x and |p| = H(x), then
   H(p) = |p| + O(1).

   Thus the complexity of a minimum-size program p drops down below the maximum possible for strings of size |p| just enough for p to be self-delimiting. [This was one of the clues that led me to chose the randomness complexity cutoff that I did: minimum-size programs should be border-line random. [In a previous version of AIT, the 1960's version, in which programs were not self-delimiting, minimum-size programs were maximally random. I was sorry to lose this in my new version of AIT, the 1970's version, but it was worth it! In exchange, I got the halting probability Ω! At any rate, this degree of randomness is still enough for us to be able to show that large minimum-size programs must have nearly the same relative frequency of 0's and 1's, and many other statistical randomness properties. In fact, Question: are there any statistical randomness properties that Chaitin-random infinite binary sequences have but which large minimum-size programs do not have? If you find the answer, let me know!] ]

2. Prove that if p and p' are both minimum-size programs for the same S-expression x, then
   H(p) = H(x) + O(1)
   H(p') = H(x) + O(1)
   H(p:p') = H(x) + O(1) .

3. Prove the result of R.M. Solovay [In his unpublished book-length manuscript on AIT dated May 1975.] that
   log₂ # { x : H(x) < n } = n − H(n) +O(1).

   In other words, show that there are 2^{n − H(n) + O(1)} different S-expressions x of complexity less than n.

4. Show that
   Ω^# = ∑_{n = 1,2,3,...} 2^−H(n)

   is also a Chaitin-random real number. Can you find other examples?

5. Find other examples like κ_n, other situations in which we can get information about a number by showing that it's random. Are there any other interesting applications of this technique?

6. Prove that Ω is irrational, i.e., not the ratio of two integers.

7. Prove that Ω is transcendental, i.e., not algebraic, not the solution of an equation
   axⁿ + bxⁿ⁻¹ + ... + px + q = 0

   with integer coefficients. [Cf. Cantor's and Liouville's proofs of the existence of transcendentals in R. Courant and H. Robbins, What is Mathematics?, Oxford University Press, 1941. This problem has a colorful intellectual history. See T. Dantzig, Number, Macmillan, 1954.]