Proof that Solovay randomness is equivalent to strong Chaitin randomness

[This theorem and its proof are taken from Chapter 7 of G. Chaitin, Algorithmic Information Theory, Cambridge University Press, 1987.]

Introduction

In this chapter I'll show you that Solovay randomness is equivalent to strong Chaitin randomness. Recall that an infinite binary sequence x is strong Chaitin random iff (H(xn), the complexity of its n-bit prefix xn) − n goes to infinity as n increases. I'll break the proof into two parts.

Proof that if x isn't Solovay random, then it's not strong Chaitin random

The program that proves this is chaitin.l.

First let me explain the proof, then I'll tell you the example that our software works its way through.

Let's suppose that the real number x is not Solovay random. In other words, there is a computable sequence of coverings An which contains x infinitely often with ∑n μ{An} < ∞.

From these An, we'll build a computer C, by generating a list of (program, size-of-output) requirements for C.

Let's start by picking an N so that the following series converges and is less than 1:

∑n ≥ N μ{An} ≤ 1.

This will be our Kraft inequality ΩC ≤ 1, because our set of requirements consists precisely of all (output, size-of-program) pairs defined as follows:

{ (s, |s|) : s ∈ An, n ≥ N }.

So everything works, and x is in infinitely many of these An, and therefore there are infinitely many prefixes s of x for which HC(s) ≤ |s|, and x is not strong Chaitin random. That completes the proof. Now what's the example that chaitin.l works its way through?

The program chaitin.l goes through the special case in which An is precisely the singleton set consisting of the n-bit string of n 1's. And we suppose that N = 5. The list of requirements produced by chaitin.l is

{ (s, |s|) : s ∈ An, n ≥ 5 }   =  
{ (11111, 5), (111111, 6), (1111111, 7), ... (1n, n), ... }

as it should be.

Okay, now let's work in the opposite direction!

Proof that if r isn't strong Chaitin random, then it's not Solovay random

The program that proves this is chaitin2.l.

Here I'll only explain the proof; the example that the software works its way through is of no interest.

Let's suppose that the infinite binary sequence r isn't strong Chaitin random. In other words, that there is a k for which there are infinitely many n-bit prefixes of r such that H(rn) ≤ n + k, where rn is the first n bits of r.

Now let's define a computable sequence of coverings An as follows: An covers all reals r having a n-bit prefix rn with H(rn) ≤ n + k.

In other words, An is the set of n-bit strings that can be compressed to within k bits of n using U. What's the measure of An? Well, let's find out.

We saw in the first chapter of Part III that for an n-bit string β

Prob{ H(β) ≤ n+H(n)−k }   ≤   1/2k−c.

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)−k for k, and substituting rn, the first n bits of r, for β, gives us

Prob{ H(rn) ≤ n+k }   ≤   1/2H(n)−k−c.

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

∑n Prob{ H(rn) ≤ n+k }   ≤   ∑n 1/2H(n)−k−c   ≤   2k+c   Ω   ≤   2k+c.

So ∑n μ{An} converges.

Hence a real r with prefixes whose complexity dips below their length + k infinitely often will be in infinitely many of the An and hence will not be Solovay random.

That completes the proof of my theorem that Solovay randomness is equivalent to strong Chaitin randomness. Hence r is Chaitin random iff r is Martin-Löf random iff r is Solovay random iff r is strong Chaitin random, and Chaitin and strong Chaitin randomness are equivalent! It's been a long journey to prove that all four of the definitions of a random real are equivalent---it's been a long journey, but I hope you enjoyed it! In Part IV I'll make some suggestions for future work.

Software for this chapter

The source code and runs of the software for this chapter can be found on the web at these URL's: 
   http://www.cs.umaine.edu/~chaitin/ait/chaitin.l
   http://www.cs.umaine.edu/~chaitin/ait/chaitin.r

   http://www.cs.umaine.edu/~chaitin/ait/chaitin2.l
   http://www.cs.umaine.edu/~chaitin/ait/chaitin2.r

   http://www.cs.auckland.ac.nz/CDMTCS/chaitin/ait/chaitin.l
   http://www.cs.auckland.ac.nz/CDMTCS/chaitin/ait/chaitin.r

   http://www.cs.auckland.ac.nz/CDMTCS/chaitin/ait/chaitin2.l
   http://www.cs.auckland.ac.nz/CDMTCS/chaitin/ait/chaitin2.r

Exercises

  1. We saw at the beginning of this part that

    H(ΩN) > N − c.

    So the halting probability Ω is Chaitin random, hence Martin-Löf random, hence Solovay random, and finally strong Chaitin random. Therefore H(ΩN) − N → ∞, the complexity of the first N bits of Ω minus N goes to infinity,

    limN → ∞ H(ΩN) − N = ∞.

    I don't know a direct proof of this interesting fact. Can you find one?

  2. Highly non-random reals! If a real number r is computable, then

    H(rn) = H(n) + O(1)
    H(rn|n) = O(1).

    But in his 1975 manuscript, Solovay managed to construct a non−computable real that also satisfies these conditions. Not much else is known. Try to figure out what the hell is going on!

  3. Complexity oscillations and microstructure! Compare and contrast the behavior of H(Ωn) with the behavior of H(rn) for a typical random real number r. Solovay (1975) has some unpublished work on this. [Solovay's results are stated without proof in G. Chaitin, ``Algorithmic information theory,'' IBM Journal of Research and Development 21 (1977), pp. 350-359, 496.]