[27] Let x A, with d(A) < . Then in Section 2.2 the randomness deficiency of x relative to A is defined as (x|A)

[27] Let x ∈ A, with d(A) < ∞. Then in Section 2.2 the randomness deficiency of x relative to A is defined as δ(x|A) = l(d(A))−

C(x|A). (Here C(x|A) is defined as C(x|χ) with χ the characteristic sequence of A and l(χ) < ∞.) If δ(x|A) is large, this means that there is a description of x with the help of A that is considerably shorter than just giving x’s serial number in A. Clearly, the randomness deficiency of x with respect to sets A and B can be vastly different. But then it is natural to ask whether there exist absolutely nonrandom objects, objects having large randomness deficiency with respect to any appropriate set.

Prove the following: Let a and b be arbitrary constants; for every sufficiently large n, there exists a binary string x of length n such that

δ(x|A) ≥ b log n for any set A containing x for which C(A) ≤ a log n.

Comments. Source: [A.K. Shen, Soviet Math. Dokl., 28(1983), 295–299].

Compare with Kamae’s theorem, Exercise 2.7.6.

Let us give some interpretation of such results bearing on statistical inference. Given an experimental result, the statistician wants to infer a statistical hypothesis under which the result is typical. Mathematically, given x we want to find a simple set A that contains x as a typical element. The above shows that there are outcomes x such that no simple statistical model of the kind described is possible. The question remains whether such objects occur in the real world.