Schnorr and Kurtz randomness

Martin-Löf randomness requires the measures of the components of a test to be bounded by $2^{-n}$, but not to be known. Schnorr argued that a test whose measures cannot be computed is not fully effective, and proposed to require them to be computable. Weakening further, Kurtz considered the null classes that are closed and effectively given. This lesson compares these notions with Martin-Löf randomness, and shows that they collapse on computably dominated sequences.

3.1 Definitions

Definition 3.1.#

1. A sequence is Kurtz random, or weakly random, if it belongs to no null $\Pi^0_1$ class.
2. A Schnorr test is a Martin-Löf test $(\mathcal U_n)$ such that the reals $\lambda(\mathcal U_n)$ are computable, uniformly in $n$. A sequence is Schnorr random if it passes every Schnorr test.

Proposition 3.2.#

Every weakly 2-random sequence is Martin-Löf random; every Martin-Löf random sequence is Schnorr random; every Schnorr random sequence is Kurtz random.

Proof of Proposition 3.2.

The first implication is Proposition 2.2 (1), and the second holds since Schnorr tests are Martin-Löf tests. For the third, let $\mathcal P = [T]$ be a null $\Pi^0_1$ class, with $T$ computable. By the second exercise of Measure on Cantor space, there are finite sets $F_n$, computable from $n$, with $\mathcal P \subseteq [F_n]^{\prec}$ and $\lambda([F_n]^{\prec}) \leq 2^{-n}$. The measures of these clopen classes are rationals computed from $F_n$, so $([F_n]^{\prec})$ is a Schnorr test, and it captures every member of $\mathcal P$.

The law of large numbers holds for Schnorr random sequences. The proof of Proposition 2.7 of “Martin-Löf tests” uses, for a fixed rational $\varepsilon > 0$, the classes $\mathcal V_n = \bigcup_{m > n} [C_m]^{\prec}$, and the number $a = e^{-2\varepsilon^2} < 1$. Their measures are computable: the measure of the clopen class $\bigcup_{n < m \leq M} [C_m]^{\prec}$ is a rational computable from $n$ and $M$, and it differs from $\lambda(\mathcal V_n)$ by at most the tail $\sum_{m > M} 2^{-m} |C_m| \leq 2a^{M+1}/(1-a)$, which tends to $0$ computably. The subsequence $(\mathcal V_{m_n})_n$ built in Lemma 2.3 of “Martin-Löf tests” is then a Schnorr test, and it captures every sequence whose frequencies of ones deviate from $\frac12$ by more than $\varepsilon$ infinitely often. Kurtz random sequences need not satisfy it.

Proposition 3.3.#

Every weakly 1-generic sequence is Kurtz random, and no weakly 1-generic sequence is Schnorr random.

Proof of Proposition 3.3.

The first statement is the third exercise of Martin-Löf tests. For the second, a weakly 1-generic sequence has frequencies of ones at least $\frac{2}{3}$ at infinitely many lengths, by the same exercise, so it fails the law of large numbers, hence a Schnorr test.

The other implications are strict as well. A Schnorr random sequence need not be Martin-Löf random: Nies, Stephan and Terwijn (2005) showed that every high degree contains a Schnorr random sequence that is not Martin-Löf random, and that conversely a Schnorr random sequence that is not high is Martin-Löf random. These results are admitted.

3.2 Collapse in computably dominated degrees

Theorem 3.4 (Nies, Stephan, Terwijn).#

If $Z$ is computably dominated and Kurtz random, then $Z$ is Martin-Löf random.

Proof of Theorem 3.4.

Suppose that $Z$ is captured by a Martin-Löf test $(\mathcal U_n)$; we show that $Z$ lies in a null $\Pi^0_1$ class. Let $\mathcal U_{n,s}$ be the clopen approximation of $\mathcal U_n$ at stage $s$, with $\mathcal U_n = \bigcup_s \mathcal U_{n,s}$. Let $f(n)$ be the least $s$ with $Z \in \mathcal U_{n,s}$; it exists since $Z \in \mathcal U_n$, and $f$ is computable in $Z$. Since $Z$ is computably dominated, there is a computable function $g$ and a number $N$ with $f(n) \leq g(n)$ for all $n \geq N$. Then $Z \in \mathcal U_{n, g(n)}$ for every $n \geq N$, so $Z$ belongs to

$$\mathcal P = \bigcap_{n \geq N} \mathcal U_{n, g(n)}.$$

Each $\mathcal U_{n, g(n)}$ is a clopen class computable uniformly in $n$, so $\mathcal P$ is a $\Pi^0_1$ class, and $\lambda(\mathcal P) \leq \lambda(\mathcal U_n) \leq 2^{-n}$ for every $n \geq N$, so $\mathcal P$ is null. Hence $Z$ is not Kurtz random.

The proof converts the time at which $Z$ enters each component into a computable bound; once the stages are bounded, the test becomes a closed null class. For computably dominated sequences, Kurtz, Schnorr and Martin-Löf randomness therefore coincide.

3.3 Exercises

Exercise 3.5 ★.

Show that every computably dominated Martin-Löf random sequence is weakly 2-random, and that no computably dominated sequence is 2-random.

Solution

A computably dominated random sequence computes no non-computable c.e. set, as shown in the second exercise of Weak 2-randomness, so it is weakly 2-random by Theorem 2.3. By Kurtz’s theorem, admitted in Relative randomness and van Lambalgen's theorem, 2-random sequences have hyperimmune degree, so they are not computably dominated.

Exercise 3.6 ★★.

Show that there is a Kurtz random sequence computable in $\emptyset'$ that is not Martin-Löf random.

Solution

By Proposition 5.7 of “The finite extension method”, there is a 1-generic set $G \leq_T \emptyset'$. It is weakly 1-generic, since a dense set of strings has no string without an extension in it, hence Kurtz random by Proposition 3.3, and not Schnorr random, hence not Martin-Löf random.

3.4 Notes and references

Schnorr (1971) introduced his notion in a critique of Martin-Löf’s definition, and characterized it by martingales with computable rates of success. Kurtz (1981) introduced weak randomness. Nies, Stephan and Terwijn (2005) proved the collapse in computably dominated (hyperimmune-free) degrees and the relation with highness. Downey and Hirschfeldt’s book contains the full hierarchy, including computable randomness, defined by computable martingales.

• S. A. Kurtz, Randomness and genericity in the degrees of unsolvability, PhD thesis, University of Illinois, 1981.
• C.-P. Schnorr, Zufälligkeit und Wahrscheinlichkeit, Lecture Notes in Mathematics 218, Springer, 1971.
• A. Nies, F. Stephan and S. A. Terwijn, Randomness, relativization and Turing degrees, Journal of Symbolic Logic 70 (2005), 515–535.
• R. G. Downey and D. R. Hirschfeldt, Algorithmic Randomness and Complexity, Springer, 2010, Chapter 7.