Kolmogorov-Loveland stochasticity for finite strings

摘要

Asarin [Theory Probab. Appl. 32 (1987) 507-508] showed that any finite sequence with small randomness deficiency has the stability property of the frequency of 1 s in their subsequences selected by simple Kolmogorov-Loveland selection rules. Roughly speaking the difference between frequency m of zeros and 1/2 in a subsequence of length n selected from a sequence with randomness deficiency d by a selection rule of complexity k is bounded by O(((d + k + log n))~(1/2)) in absolute value. In this paper we prove a result in the inverse direction: if the randomness deficiency of a sequence is large then there is a simple Kolmogorov-Loveland selection rule that selects not too short subsequence in which frequency of ones is far from 1/2. Roughly speaking for any sequence of length N there is a selection rule of complexity O(log(N/d)) selecting a subsequence such that |m - 1/2| = Ω(d/(n log(N/d))).