[34] Let x be string and , natural numbers. Kolmogorov called a string (, )-stochastic if there is a finite set A N

[34] Let x be string and α, β natural numbers. Kolmogorov called a string (α, β)-stochastic if there is a finite set A ⊆ N and x ∈ A such that x ∈ A, K(A) ≤ α, K(x|A) ≥ log d(A) − β.

The first inequality (with α not too large) means that A is sufficiently simple. The second inequality (with β not too large) means that x is an undistinguished (typical) element of A. If x had properties defining a very small subset B of A, then these could be used to obtain a simple description of x by determining its ordinal number in B. This would require log d(B) bits, which would be significantly less than log d(A).

(a) Show that (α, β)-stochasticity of x is equivalent to βx(α) ≤ β.

(b) Show that the overwhelming majority of strings of length n with an equal number of 0s and 1s is (O(log n), O(1))-stochastic.

(c) Similarly, show that the overwhelming majority of strings of length n is (O(log n), O(1))-stochastic.

(d) Show that for some constants

c, C, for every n and every α, β with

α ≥ log n + C and α + β ≥ n + c log n + C, every string of length n is

(α, β)-stochastic.

(e) Show that for some constants

c, C, for all n and all α, β with α+β <

n−c log n−C, there is a string x of length n that is not (α, β)-stochastic.

(f) Show that the fraction of strings of length n that are not (α, β)-

stochastic is at least 2−2α−β−O(log n).

(g) Let A be the set of strings of length n that are not (α, β)-stochastic.



Show that in case 2α + β

Comments. Hint for Item (b): The set A has cardinality n n/2 = Θ(2n/
√n)
and K(A) = K(n) + O(1) = O(log n). The majority of elements x ∈ A have complexity K(x|A) = log d(A) + O(1). Hint for Item (c): Although the overwhelming majority of strings in {0, 1}n do not belong to A, they are nonetheless also (O(log n), O(1))-stochastic, this time with respect to the set {0, 1}n. Source for Item (d): [A.K. Shen, Soviet Math. Dokl., 28:1(1983), 295–299]. Item (e): in [A.K. Shen, Ibid.] it is proven that for some constants

c, C, for all n and all α, β with 2α + β

(d) and

(e) that if we take α = β, then for some boundary around 1 2n, the last non-(α, β)-stochastic elements disappear if the complexity constraints are sufficiently relaxed by having α, β exceed this boundary. Source for Item (e): [N.K. Vereshchagin and P.M.B. Vit´anyi, IEEE Trans. Inform.
Theory, 50:12(2004), 3265–3290]. Source for Items

(f) and (g): [A.K.
Shen,, V.A. Uspensky and N.K. Vereshchagin, Kolmogorov Complexity and Algorithmic Randomness, American Mathematical Society, 2017].