Relative randomness and van Lambalgen's theorem

Randomness relative to an oracle $X$ asks a sequence to pass all tests that $X$ can enumerate. The stronger the oracle, the fewer random sequences. Van Lambalgen’s theorem describes how relative randomness interacts with the join: a sequence $A \oplus B$ is random if and only if $A$ is random and $B$ is random relative to $A$. The theorem has consequences for the Turing degrees of random sequences, and it characterizes randomness relative to $\emptyset'$, called 2-randomness, in terms of Chaitin’s $\Omega$.

1.1 Relative randomness

Definition 1.1.#

Let $X$ be a set. A Martin-Löf test relative to $X$ is a sequence of classes $(\mathcal U_n)$, uniformly $\Sigma^0_1(X)$, with $\lambda(\mathcal U_n) \leq 2^{-n}$. A sequence is Martin-Löf random relative to $X$, or $X$-random, if it passes every such test. The class of $X$-random sequences is written $\mathrm{MLR}^X$. For $n \geq 1$, a sequence is $n$-random if it is random relative to $\emptyset^{(n-1)}$; the 1-random sequences are the Martin-Löf random ones.

All results of the course on Martin-Löf randomness relativize: there is a universal test relative to $X$, $\mathrm{MLR}^X$ is conull, and $Z \in \mathrm{MLR}^X$ if and only if $K^X(Z \uh n) \geq n - O(1)$, where $K^X$ is prefix-free complexity relative to $X$. If $Y \leq_T X$, every test relative to $Y$ is a test relative to $X$, so $\mathrm{MLR}^X \subseteq \mathrm{MLR}^Y$.

Two facts of measure theory are used below. They concern a class $\mathcal W \subseteq \cs$ seen as a class of pairs, through the identification of $X \oplus Y$ with $(X, Y)$, and its sections $\mathcal W_X = \{ Y : X \oplus Y \in \mathcal W \}$.

Fact 1.2 (Fubini).#

For every open class $\mathcal W$, the function $X \mapsto \lambda(\mathcal W_X)$ is measurable and $\lambda(\mathcal W) = \int \lambda(\mathcal W_X)\, dX$. In particular, for every $q > 0$, $\lambda(\{ X : \lambda(\mathcal W_X) > q \}) \leq \lambda(\mathcal W) / q$.

This is Fubini’s theorem for the product of two copies of the uniform measure, which is the uniform measure under the identification; the second statement is Markov’s inequality. Both are admitted. Note that if $\mathcal W$ is $\Sigma^0_1$, then $\mathcal W_X$ is $\Sigma^0_1(X)$ uniformly in $X$, and $\{ X : \lambda(\mathcal W_X) > q \}$ is $\Sigma^0_1$, uniformly in a rational $q$, since $\lambda(\mathcal W_X)$ is left-c.e. relative to $X$, uniformly.

Every oracle-dependent sequence of classes can be trimmed into a test for every oracle, as in the construction of the universal test (Martin-Löf): from an oracle machine enumerating $\mathcal V^X_n$, one computes another enumerating $\widehat{\mathcal V}^X_n \subseteq \mathcal V^X_n$, with $\lambda(\widehat{\mathcal V}^X_n) \leq 2^{-n}$ for every $X$, and $\widehat{\mathcal V}^X_n = \mathcal V^X_n$ whenever $\lambda(\mathcal V^X_n) \leq 2^{-n}$.

1.2 Van Lambalgen’s theorem

Theorem 1.3 (van Lambalgen).#

For all sets $A$ and $B$, $A \oplus B$ is Martin-Löf random if and only if $A$ is Martin-Löf random and $B$ is Martin-Löf random relative to $A$.

Proof of Theorem 1.3.

We prove both directions by contraposition.

($\Rightarrow$) Suppose $A$ is captured by a test $(\mathcal U_n)$. Then $A \oplus B$ belongs to the classes $\{ X \oplus Y : X \in \mathcal U_n \}$, which are uniformly $\Sigma^0_1$ with the same measures; so $A \oplus B$ is not random. Suppose $B$ is captured by a test relative to $A$; by trimming, we may assume it is given by an oracle machine $X \mapsto (\mathcal V^X_n)$ with $\lambda(\mathcal V^X_n) \leq 2^{-n}$ for every $X$. Let $\mathcal W_n = \{ X \oplus Y : Y \in \mathcal V^X_n \}$, uniformly $\Sigma^0_1$. By Fact 1.2, $\lambda(\mathcal W_n) = \int \lambda(\mathcal V^X_n)\, dX \leq 2^{-n}$, and $A \oplus B \in \bigcap_n \mathcal W_n$.

($\Leftarrow$) Suppose $A \oplus B \in \bigcap_n \mathcal U_n$ for a Martin-Löf test $(\mathcal U_n)$, and $A$ random. For each $n$, let $\mathcal V^X_n = (\mathcal U_{2n})_X = \{ Y : X \oplus Y \in \mathcal U_{2n} \}$, and $\mathcal S_n = \{ X : \lambda(\mathcal V^X_n) > 2^{-n} \}$. The classes $\mathcal S_n$ are uniformly $\Sigma^0_1$, and $\lambda(\mathcal S_n) \leq 2^{-2n} / 2^{-n} = 2^{-n}$ by Fact 1.2. So $(\mathcal S_n)$ is a Solovay test, and since $A$ is random, $A \notin \mathcal S_n$ for all $n \geq N$, for some $N$ (Solovay). For $n \geq N$, $\lambda(\mathcal V^A_n) \leq 2^{-n}$, so $(\mathcal V^A_{n+N})_n$ is a Martin-Löf test relative to $A$. It captures $B$, since $A \oplus B \in \mathcal U_{2n}$ for every $n$. So $B$ is not random relative to $A$.

The statement of the theorem is not symmetric in $A$ and $B$, but its consequences are: $A \oplus B$ is random if and only if $B \oplus A$ is (second exercise below), so $A$ is random and $B$ is $A$-random if and only if $B$ is random and $A$ is $B$-random. Two sequences $A$ and $B$ with this property, that is, such that $A \oplus B$ is random, are called mutually random.

Corollary 1.4.#

1. If $A \oplus B$ is random, then $A$ and $B$ are Turing incomparable.
2. A sequence $A$ is 2-random if and only if $A \oplus \Omega$ is random, where $\Omega$ is Chaitin’s halting probability. In particular, no 2-random sequence computes $\emptyset'$.

Proof of Corollary 1.4.

1. If $B \leq_T A$, then $B$ is not random relative to $A$: the classes $[B \uh n]$ form a test relative to $A$. By the theorem, $A \oplus B$ is not random. If $A \leq_T B$, apply the same argument to $B \oplus A$, which is random as the image of $A \oplus B$ under the computable measure-preserving map exchanging even and odd positions.
2. Since $\Omega \equiv_T \emptyset'$ (Chaitin), randomness relative to $\Omega$ is randomness relative to $\emptyset'$. By the theorem applied to $\Omega \oplus A$, this sequence is random if and only if $A$ is random relative to $\Omega$, since $\Omega$ is random (Chaitin); and $\Omega \oplus A$ is random if and only if $A \oplus \Omega$ is. If a 2-random $A$ computed $\emptyset'$, then $A \geq_T \Omega$, contradicting (1) for the random sequence $A \oplus \Omega$.

1.3 2-randomness

The 2-random sequences avoid every class captured by a Martin-Löf test relative to $\emptyset'$. They are computationally weaker than arbitrary random sequences: by Corollary 1.4 (2), a 2-random sequence does not compute $\emptyset'$, whereas $\Omega$ is random and computes it. Kurtz (1981) showed that every 2-random sequence has hyperimmune degree, and Kautz (1991) that every 2-random sequence $A$ satisfies $A' \equiv_T A \oplus \emptyset'$; we admit both results. Miller (2004) and Nies, Stephan and Terwijn (2005) characterized 2-randomness by plain complexity: $A$ is 2-random if and only if $C(A \uh n) \geq n - O(1)$ for infinitely many $n$.

1.4 Exercises

Exercise 1.5 ★.

Let $Z$ be random, $Z_0 = \{ n : 2n \in Z \}$ and $Z_1 = \{ n : 2n + 1 \in Z \}$. Show that $Z_0$ and $Z_1$ are random, and Turing incomparable.

Solution

$Z = Z_0 \oplus Z_1$. By Theorem 1.3, $Z_0$ is random and $Z_1$ is random relative to $Z_0$, hence random. By Corollary 1.4 (1), they are Turing incomparable.

Exercise 1.6 ★.

Show that if $A$ is random and $B$ is random relative to $A$, then $B$ is random and $A$ is random relative to $B$.

Solution

By Theorem 1.3, $A \oplus B$ is random. The map $X \oplus Y \mapsto Y \oplus X$ is computable and preserves the measure, so it maps Martin-Löf tests to Martin-Löf tests; hence $B \oplus A$ is random. By Theorem 1.3 again, $B$ is random and $A$ is random relative to $B$.

1.5 Notes and references

Van Lambalgen proved his theorem in his thesis (1987). The theorem fails for some other randomness notions, such as Schnorr randomness, in one direction. Kurtz’s thesis (1981) and Kautz’s thesis (1991) contain the basic results on $n$-randomness.

• M. van Lambalgen, Random sequences, PhD thesis, University of Amsterdam, 1987.
• S. A. Kurtz, Randomness and genericity in the degrees of unsolvability, PhD thesis, University of Illinois, 1981.
• S. M. Kautz, Degrees of random sets, PhD thesis, Cornell University, 1991.
• J. S. Miller, Every 2-random real is Kolmogorov random, Journal of Symbolic Logic 69 (2004), 907–913.
• A. Nies, F. Stephan and S. A. Terwijn, Randomness, relativization and Turing degrees, Journal of Symbolic Logic 70 (2005), 515–535.