Kolmogorov-Loveland Stochasticity and Kolmogorov Complexity

摘要

Merkle et al. (Ann. Pure Appl. Logic 138(1-3): 183-210, 2006) showed that all Kolmogorov-Loveland stochastic infinite binary sequences have constructive Hausdorff dimension 1. In this paper, we go even further, showing that from an infinite sequence of dimension less than H(1/2 + δ) (H being the Shannon entropy function) one can extract by an effective selection rule a biased subsequence with bias at least S. We also prove an analogous result for finite strings.