The Levin–Schnorr theorem

The course on Kolmogorov complexity proposed to call a sequence random when its initial segments are incompressible, and showed that plain complexity cannot be used for this purpose (Corollary 2.4 of “Complexity of initial segments”). With prefix-free complexity, the proposal succeeds, and gives exactly the Martin-Löf random sequences. This theorem of Levin and Schnorr connects the measure-theoretic definition of the previous lesson with the definition by incompressibility. It shows at once that $\Omega$ is random, and leads to finer information on the complexity of random sequences.

Throughout, $K$ is the prefix-free complexity defined by an optimal prefix-free machine $U$, and $\leq^+$ denotes inequality up to an additive constant.

3.1 Randomness and incompressibility

Theorem 3.1 (Levin, Schnorr).#

A sequence $Z$ is Martin-Löf random if and only if there is a constant $c$ with $K(Z \uh n) \geq n - c$ for every $n$.

Proof of Theorem 3.1.

($\Rightarrow$) Suppose that for every $c$ there is $n$ with $K(Z \uh n) < n - c$. For each $c$, let $\mathcal V_c$ be the open class generated by the set of strings $\sigma$ with $K(\sigma) < |\sigma| - c$. This set is c.e., uniformly in $c$, since $K$ is approximable from above: $K(\sigma) < k$ if and only if $U(\tau)\converge = \sigma$ for some $\tau$ of length less than $k$. Let $W$ be the set of the minimal elements of this set, those with no proper prefix in it; it is prefix-free and generates $\mathcal V_c$. Then

$$\lambda(\mathcal V_c) = \sum_{\sigma \in W} 2^{-|\sigma|} < \sum_{\sigma \in W} 2^{-K(\sigma) - c} \leq 2^{-c},$$

by Proposition 3.4 of “Prefix-free complexity” (4), if $W$ is non-empty; otherwise $\lambda(\mathcal V_c) = 0$. So $(\mathcal V_c)$ is a Martin-Löf test, and $Z$ belongs to every $\mathcal V_c$ by hypothesis, so it is not random.

($\Leftarrow$) Suppose that $Z$ is captured by a Martin-Löf test $(\mathcal U_n)$. By Lemma 1.2, there are c.e. prefix-free sets $W_n$, uniformly in $n$, with $\mathcal U_n = [W_n]^{\prec}$. Every $\sigma \in W_n$ satisfies $2^{-|\sigma|} \leq \lambda(\mathcal U_n) \leq 2^{-n}$, so $|\sigma| \geq n$. Enumerate the requests $(\sigma, |\sigma| - c)$ for $c \geq 1$ and $\sigma \in W_{2c}$; their lengths are at least $c$. Their weight is

$$\sum_{c \geq 1} \sum_{\sigma \in W_{2c}} 2^{-|\sigma| + c} = \sum_{c \geq 1} 2^c \lambda(\mathcal U_{2c}) \leq \sum_{c \geq 1} 2^{-c} = 1.$$

By the KC theorem (KC theorem; Levin, Schnorr, Chaitin), there is a constant $d$ with $K(\sigma) \leq |\sigma| - c + d$ for every $c \geq 1$ and $\sigma \in W_{2c}$. Since $Z \in \mathcal U_{2c}$, some prefix $Z \uh n$ belongs to $W_{2c}$, and $K(Z \uh n) \leq n - c + d$. As $c$ is arbitrary, no constant bounds $n - K(Z \uh n)$.

The two directions use the two faces of $K$. Incompressibility fails on an effectively open class of small measure, because $K$ satisfies the Kraft inequality and is approximable from above. Conversely, the KC theorem turns a test into a machine that compresses the strings generating its components, the gain $c$ being paid for by the measure $2^{-2c}$ of the component used.

Corollary 3.2.#

The classes $\mathcal V_c = [\{ \sigma : K(\sigma) < |\sigma| - c \}]^{\prec}$ form a universal Martin-Löf test.

Proof of Corollary 3.2.

The first part of the proof shows that $(\mathcal V_c)$ is a Martin-Löf test. The second shows that if $Z$ is captured by some test, then for every $c$ there is $n$ with $K(Z \uh n) < n - c$, that is, $Z \in \mathcal V_c$.

3.2 The halting probability is random

Corollary 3.3 (Chaitin).#

The binary expansion of $\Omega$ is Martin-Löf random. In particular there is a random sequence Turing equivalent to $\emptyset'$, and a random left-c.e. real.

Proof of Corollary 3.3.

By Chaitin, $K(\omega \uh n) \geq n - c$ for every $n$, and $\omega \equiv_T \emptyset'$. Apply Theorem 3.1.

Random sequences can therefore be computationally powerful, unlike the low random sequences of Corollary 2.5. A left-c.e. real of $(0, 1)$ is random if and only if it is the halting probability of some optimal prefix-free machine, by results of Calude, Hertling, Khoussainov and Wang, and of Kučera and Slaman (2001); this is admitted here.

3.3 The ample excess lemma

The Levin–Schnorr theorem gives a lower bound $n - c$ on the complexity of the prefixes of a random sequence. The excess $K(Z \uh n) - n$ is in fact large for most $n$.

Theorem 3.4 (Ample excess lemma; Miller, Yu).#

A sequence $Z$ is Martin-Löf random if and only if $\sum_n 2^{n - K(Z \uh n)} < \infty$.

Proof of Theorem 3.4.

($\Leftarrow$) If the sum is at most $2^c$, each term is, so $K(Z \uh n) \geq n - c$ for every $n$, and $Z$ is random by Theorem 3.1.

($\Rightarrow$) For a string $\tau$ of length $N$, let $F(\tau) = \sum_{n \leq N} 2^{n - K(\tau \uh n)}$. For each $k$, let $D_N$ be the set of strings $\tau$ of length $N$ with $F(\tau) > 2^k$, and $\mathcal V_k = \bigcup_N [D_N]^{\prec}$. Since $K$ is approximable from above, $F(\tau)$ is the limit of a computable non-decreasing sequence of rationals, so $F(\tau) > 2^k$ is a $\Sigma^0_1$ property of $\tau$ and $k$, and $(\mathcal V_k)$ is uniformly $\Sigma^0_1$.

A string extending an element of $D_N$ has a larger value of $F$, so $[D_N]^{\prec} \subseteq [D_{N+1}]^{\prec}$. We bound the size of $D_N$ by summing $F$ over all strings of length $N$. Each string $\rho$ of length $n \leq N$ is the prefix of $2^{N - n}$ strings of length $N$, so

$$2^k |D_N| < \sum_{|\tau| = N} F(\tau) = \sum_{n \leq N} \sum_{|\rho| = n} 2^{N-n}\, 2^{n - K(\rho)} = 2^N \sum_{|\rho| \leq N} 2^{-K(\rho)} \leq 2^N,$$

when $D_N$ is non-empty, by Proposition 3.4 of “Prefix-free complexity” (4). Hence $\lambda([D_N]^{\prec}) \leq 2^{-k}$ for every $N$, and $\lambda(\mathcal V_k) \leq 2^{-k}$ by continuity. So $(\mathcal V_k)$ is a Martin-Löf test. If the sum diverges for $Z$, then $F(Z \uh N) > 2^k$ for some $N$, for every $k$, and $Z$ is captured.

The proof is an averaging argument: the average of $\sum_n 2^{n - K(X \uh n)}$ over all sequences $X$ is $\sum_\rho 2^{-K(\rho)} \leq 1$, and the test collects the sequences on which the sum is large.

Corollary 3.5 (Chaitin).#

A sequence $Z$ is Martin-Löf random if and only if $\lim_n (K(Z \uh n) - n) = +\infty$.

Proof of Corollary 3.5.

If $Z$ is random, the terms $2^{n - K(Z \uh n)}$ of a convergent series tend to $0$, so $K(Z \uh n) - n$ tends to $+\infty$. Conversely, if the limit is infinite, $K(Z \uh n) - n$ is bounded from below, and $Z$ is random by Theorem 3.1.

The lemma says more than the corollary. Let $A$ be the set of $n \geq 1$ with $K(Z \uh n) < n + \log n$. Each $n \in A$ contributes more than $1/n$ to the convergent series, so $\sum_{n \in A} 1/n < \infty$: for a random sequence, the excess falls below $\log n$ only on a sparse set of lengths.

3.4 Exercises

Exercise 3.6 ★.

Let $Z$ be Martin-Löf random and $f$ a strictly increasing computable function. Show that the sequence $Y = Z(f(0))\, Z(f(1))\, Z(f(2)) \cdots$ is random.

Solution

For a string $\sigma$, the class of $X$ with $X(f(i)) = \sigma(i)$ for $i < |\sigma|$ is a clopen class $[\sigma]_f$ of measure $2^{-|\sigma|}$, computable from $\sigma$. If $Y$ is captured by $(\mathcal U_n)$, write $\mathcal U_n = [W_n]^{\prec}$ with $W_n$ c.e. prefix-free (Lemma 1.2), and let $\mathcal V_n = \bigcup_{\sigma \in W_n} [\sigma]_f$. The classes $[\sigma]_f$, $\sigma \in W_n$, are pairwise disjoint since the strings are incomparable, so $\lambda(\mathcal V_n) = \lambda(\mathcal U_n) \leq 2^{-n}$. The sequence $(\mathcal V_n)$ is uniformly $\Sigma^0_1$, and it captures $Z$.

Exercise 3.7 ★★.

Let $Z$ be Martin-Löf random. Show that for almost every $n$, the bits $Z(n), \dots, Z(n + K(n) - 1)$ are not all $0$.

Hint

Use a Solovay test whose $n$-th component has measure $2^{-K(n)}$.

Solution

Let $\mathcal S_n$ be the class of sequences $X$ with $X(n + i) = 0$ for every $i < K(n)$. It is the union over $s$ of the clopen classes defined with $K_s(n)$ instead of $K(n)$, where $K_s$ approximates $K$ from above; these increase with $s$, so $(\mathcal S_n)$ is uniformly $\Sigma^0_1$. Its measure is $2^{-K(n)}$, so $\sum_n \lambda(\mathcal S_n) \leq 1$ by the Kraft inequality. By Theorem 2.9, $Z$ belongs to only finitely many $\mathcal S_n$.

Exercise 3.8 ★★.

Identify a sequence $X$ with the real $0.X = \sum_i X(i) 2^{-i-1}$. Let $Z$ be random, and suppose that there is a computable sequence of rationals $(r_t)$ converging to $\alpha = 0.Z$ with $\sum_t |r_{t+1} - r_t| < \infty$. Show that $\alpha$ is left-c.e. or right-c.e.

Solution

For rationals $a < b$, the class of $X$ with $a < 0.X < b$ is a $\Sigma^0_1$ class of measure at most $b - a$, uniformly in $a$ and $b$: it is generated by the strings $\sigma$ whose dyadic interval $[0.\sigma, 0.\sigma + 2^{-|\sigma|}]$ is contained in $(a, b)$. Let $\mathcal S_t$ be this class for the open interval with endpoints $r_t$ and $r_{t+1}$ (empty if they are equal). This is a Solovay test, so there is $t_0$ such that $\alpha$ lies strictly between $r_t$ and $r_{t+1}$ for no $t \geq t_0$. The real $\alpha$ is not rational: a sequence $X$ with $0.X$ rational is eventually periodic, hence computable, hence not random. So $\alpha \neq r_t$ for every $t$, and for $t \geq t_0$, $r_t$ and $r_{t+1}$ lie on the same side of $\alpha$. All $r_t$, $t \geq t_0$, are then on the same side. If they are below $\alpha$, the computable non-decreasing sequence $\max_{t_0 \leq u \leq t} r_u$ converges to $\alpha$, which is left-c.e.; if they are above, $\alpha$ is right-c.e. by the symmetric argument.

3.5 Notes and references

The characterization of randomness by prefix-free complexity was found independently by Levin (1973), with monotone complexity, and Schnorr (1973), with process complexity; the form with $K$, and Corollary 3.5, are due to Chaitin. The ample excess lemma is due to Miller and Yu (2008). A third characterization of randomness, by the failure of c.e. martingales to win unbounded capital, is due to Schnorr (1971); see Downey and Hirschfeldt, Chapter 6. The last exercise is due to Rettinger, as reported by Nies.

• L. A. Levin, On the notion of a random sequence, Soviet Mathematics Doklady 14 (1973), 1413–1416.
• C.-P. Schnorr, Process complexity and effective random tests, Journal of Computer and System Sciences 7 (1973), 376–388.
• G. J. Chaitin, A theory of program size formally identical to information theory, Journal of the ACM 22 (1975), 329–340.
• J. S. Miller and L. Yu, On initial segment complexity and degrees of randomness, Transactions of the American Mathematical Society 360 (2008), 3193–3210.
• A. Kučera and T. A. Slaman, Randomness and recursive enumerability, SIAM Journal on Computing 31 (2001), 199–211.