Proof that Solovay randomness is equivalent to Martin-Löf randomness

What is Solovay's definition?

Consider once more a computable sequence of coverings A_k. This time, however, we do not follow Martin-Löf and assume that

for all k. Instead we only know that the sum of these measures converges, that is, that

According to Martin-Löf, a real r is non-random if it is contained in all of the A_k. Now, following Solovay, r is non-random if it is merely contained in infinitely many of the A_k.

So if a real is Martin-Löf non-random, then it will also be Solovay non-random. Solovay's criterion for non-randomness is much less demanding than Martin-Löf's.

Why is this a good definition? Because in probability theory one often uses the argument that if the infinite series of events A_k has the property that

converges, then with probability one only finitely many of the events A_k will occur. That's called the Borel-Cantelli lemma. [See W. Feller, An Introduction to Probability Theory and Its Applications, Vol. 1, Wiley, 1950.] We can therefore paraphrase Solovay's definition by saying that a real is Solovay random if it always obeys the Borel-Cantelli lemma.

Now I'll present Solovay's proof that Solovay randomness is actually equivalent to Martin-Löf randomness.

We've already seen that if a real is Martin-Löf non-random, then it is also Solovay non-random. So we only need to prove the converse, namely that if a real is Solovay non-random, then it's also Martin-Löf non-random. Why is this so?

Well, says Solovay, consider a real r which is covered by infinitely many of the A_k in a computable sequence of coverings A_k with

We'll construct a new computable sequence of coverings B_k from the A_k, in such a way that r is in all of the B_k and

How does Solovay achieve this?

Well, he defines B_k to consist precisely of all those reals, of all the points which are in at least 2^k+c of the coverings A_k! That's all there is to it!

That proves Solovay's theorem, but how do we program this? Well, for starters, to simplify matters I just produce the B_k consisting of all those points which are in at least k of the coverings A_k.

So at stage n I generate A₀ through A_n for time n. Then I extend all the prefixes for the intervals in these coverings to the same size, I increase the granularity, so that I can determine the multiplicity of each subinterval. And once I have collected those subintervals with multiplicity ≥ k, I try to reassemble them, by collapsing any pairs of adjacent subintervals α0 and α1 into the single interval whose prefix is α.

And what do I take as my coverings A_k? I let A_k consist of all those bit strings of the form

Thus 1^j0 is in precisely j of the A_k. And B_k, the set of strings that are in at least k of the A_k, is

And solovay.l calculates

Now we're finally ready to exhibit examples of statistical assertions that we can make about the bits of the halting probability Ω! Solovay randomness is just the tool that we need, and we can use it because at this point we've seen that Ω is Chaitin random, hence Martin-Löf random, and thus Solovay random. So please do the exercises!

Software for this chapter

   http://www.cs.umaine.edu/~chaitin/ait/solovay.l
   http://www.cs.umaine.edu/~chaitin/ait/solovay.r
 
   http://www.cs.auckland.ac.nz/CDMTCS/chaitin/ait/solovay.l
   http://www.cs.auckland.ac.nz/CDMTCS/chaitin/ait/solovay.r

Exercises

1. Find another sequence of coverings A_k to run solovay.l on. The A_k that I've picked aren't very interesting!

2. Equal limiting relative frequencies of 0's and 1's. Use Ω's Solovay randomness to prove that Ω is Borel simply normal in base two, i.e., that the relative frequency of 0's and 1's both tend to the limit one-half. Hint: the number of n-bit strings with exactly k 0's and n−k 1's is the binomial coefficient ``n choose k'' =

   ( n k )

   =  n! / k!(n−k)! .

   Show that this infinite sum converges:

   ∑n 2−n ∑|k/n − 1/2| > ε

   ( n k )

   <     ∞.

   Do this by considering the ratio of successive binomial coefficients. Work with estimates of base-two logarithms of probabilities using Stirling's approximation:

   log₂ n!     ~     n log₂ n.

3. Invariance of limiting frequency under subsequence selection. Show that any algorithm for picking a subset of the bits of Ω that selects infinitely many bits of Ω selects 0's and 1's with limiting relative frequency exactly one-half. A selection algorithm is one that generates an infinite sequence of position numbers of the selected bits.

4. Nonexistence of prediction algorithms. Show that any algorithm for predicting the next bit of Ω based on all the previous bits will be correct in the limit exactly half the time.

5. Nonexistence of selective prediction algorithms. Show that any algorithm for predicting the next bit of Ω based on all the previous bits, but which now has the option of saying ``no prediction'' as well as predicting that the next bit will be a 0 or a 1, will be correct in the limit exactly half the time, as long as it predicts infinitely many bits of Ω.

6. Borel absolute normality. [The subtlety of applying theoretical models to the real world is emphasized by F. Chaitin-Chatelin's Newcomb-Borel paradox, which points out that in spite of Borel normality, the first digit of a physically measured quantity is much more likely to be a 1 than a 9! See F. Chaitin-Chatelin and V. Frayssé, Lectures on Finite Precision Computations, SIAM, 1996, p. 101.] Show that the preceding exercises work if the real number Ω is written in any base, not just base-two. In fact, show that in any base all possible digits and blocks of digits of the same length have equal limiting relative frequency. E.g., in base ten each digit of Ω has limiting relative frequency exactly one-tenth, and each of the hundred possible blocks of two consecutive digits has limiting relative frequency exactly one in a hundred, etc.