Kolmogorov–Loveland randomness and stochasticity

An infinite binary sequence X is Kolmogorov–Loveland (or KL-) random if there is no computable non-monotonic betting strategy that succeeds on X in the sense of having an unbounded gain in the limit while betting successively on bits of X . A sequence X is KL-stochastic if there is no computable non-monotonic selection rule that selects from X an infinite, biased sequence. One of the major open problems in the field of effective randomness is whether Martin-Lof randomness is the same as KL-randomness. Our first main result states that KL-random sequences are close to Martin-Lof random sequences in so far as every KL-random sequence has arbitrarily dense subsequences that are Martin-Lof random. A key lemma in the proof of this result is that for every effective split of a KL-random sequence at least one of the halves is Martin-Lof random. However, this splitting property does not characterize KL-randomness; we construct a sequence that is not even computably random such that every effective split yields two subsequences that are 2-random. Furthermore, we show for any KL-random sequence A that is computable in the halting problem that, first, for any effective split of A both halves are Martin-Lof random and, second, for any computable, nondecreasing, and unbounded function g and almost all n , the prefix of A of length n has prefix-free Kolmogorov complexity at least n − g ( n ) . Again, the latter property does not characterize KL-randomness, even when restricted to left-r.e. sequences; we construct a left-r.e. sequence that has this property but is not KL-stochastic and, in fact, is not even Mises–Wald–Church stochastic. Turning our attention to KL-stochasticity, we construct a non-empty Π 1 0 class of KL-stochastic sequences that are not weakly 1-random; by the usual basis theorems we obtain such sequences that in addition are left-r.e., are low, or are of hyperimmune-free degree. Our second main result asserts that every KL-stochastic sequence has effective dimension 1, or equivalently, a sequence cannot be KL-stochastic if it has infinitely many prefixes that can be compressed by a factor of α 1 . This improves on a result by Muchnik, who has shown that were they to exist, such compressible prefixes could not be found effectively.