Recovering randomness from an asymptotic Hamming distance
Bjørn Kjos-Hanssen · arXiv (Cornell University) · 2010
A notion of asymptotic Hamming distance suitable for the study of algorithmic randomness is developed. As an application, it is shown that Theorem There is no fixed procedure that computes a Mises-Wald-Church stochastic set from a complex set. Here a set is complex if its prefixes have Kolmogorov complexity bounded below by an order function (an unbounded, nondecreasing computable function). Definition A sequence X ∈ 2ω is Mises-Wald-Church stochastic if no partial computable monotonic selection rule can select a biased subsequence of X, i.e., a subsequence where the relative frequencies of 0s and 1s do not converge to 1/2. Similarity and standard similarity Hamming distance d(σ, τ) is given by d(σ, τ) = |{n : σ(n) 6= τ(n)}| . Let the collection of all infinite computable sets be denoted by C. Let p : ω→ ω. For X, Y ∈ 2ω and N ∈ C we write X ∼p,N Y ⇐⇒ (∀∞n ∈ N) (d(X n, Y n) 6 p(n)). X ∼p Y ⇐⇒ X ∼p,ω Y . X p Y ⇐⇒ X ∼p,L Y (∃L ∈ C). Easy to understand randomness extraction in terms of p. Seems hard in terms of ∼p. Theorem (Law of the iterated logarithm for subsequences, Michel Weber 1990) Let N = {ν1 1 part of the law of iterated logarithm satisfied. (X could be 1-generic relative to A, so the LIL will not be satisfied, but the lim sup > 1 part will be.) Extracting DNR functions Theorem (Greenberg and J. Miller, 2009) A has non-DNR Turing degree ⇐⇒ each Martin-Lof random set X is Kurtz random relative to A. Corollary A is close to a Martin-Lof random set in Hamming distance =⇒ A has DNR degree. (The amount of closeness is sharp because ∅ does not have DNR degree.)