TY - JOUR

T1 - Kolmogorov-Loveland randomness and stochasticity

AU - Merkle, Wolfgang

AU - Miller, Joseph S.

AU - Nies, André

AU - Reimann, Jan

AU - Stephan, Frank

N1 - Funding Information:
∗Corresponding author. Tel.: +49 06221 545409; fax: +49 06221 544465. E-mail address: [email protected] (W. Merkle). 1Joseph S. Miller was supported by the Marsden fund of New Zealand. 2André Nies is partially supported by the Marsden fund of New Zealand, grant no 03-UOA-130. 3Frank Stephan is supported in part by NUS grant number R252–000–212–112.

PY - 2006/3

Y1 - 2006/3

N2 - 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-Löf randomness is the same as KL-randomness. Our first main result states that KL-random sequences are close to Martin-Löf random sequence at least one of the halves is Martin-Löf 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-Löf 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 ∏10 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.

AB - 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-Löf randomness is the same as KL-randomness. Our first main result states that KL-random sequences are close to Martin-Löf random sequence at least one of the halves is Martin-Löf 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-Löf 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 ∏10 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.

UR - http://www.scopus.com/inward/record.url?scp=33644802778&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33644802778&partnerID=8YFLogxK

U2 - 10.1016/j.apal.2005.06.011

DO - 10.1016/j.apal.2005.06.011

M3 - Article

AN - SCOPUS:33644802778

SN - 0168-0072

VL - 138

SP - 183

EP - 210

JO - Annals of Pure and Applied Logic

JF - Annals of Pure and Applied Logic

IS - 1-3

ER -