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 1s in their subsequences selected by simple Kolmogorov-Loveland selection rules. Roughly speaking the difference between frequency m/n 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 Oroot(d + k + logn)/n) 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/n - 1/2\ = Omega (d/(n log(N/d))). (C) 2004 Elsevier B.V. All rights reserved.