Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.apal.2005.06.011
Title: Kolmogorov-Loveland randomness and stochasticity
Authors: Merkle, W.
Miller, J.S.
Nies, A.
Reimann, J.
Stephan, F. 
Keywords: Algorithmic randomness
Effective Hausdorff dimension
Kolmogorov complexity
Kolmogorov-Loveland stochastic sequences
Issue Date: Mar-2006
Citation: Merkle, W., Miller, J.S., Nies, A., Reimann, J., Stephan, F. (2006-03). Kolmogorov-Loveland randomness and stochasticity. Annals of Pure and Applied Logic 138 (1-3) : 183-210. ScholarBank@NUS Repository. https://doi.org/10.1016/j.apal.2005.06.011
Abstract: 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 ∏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. © 2005 Elsevier B.V. All rights reserved.
Source Title: Annals of Pure and Applied Logic
URI: http://scholarbank.nus.edu.sg/handle/10635/103465
ISSN: 01680072
DOI: 10.1016/j.apal.2005.06.011
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.