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.

SCOPUSTM   
Citations

32
checked on May 20, 2018

WEB OF SCIENCETM
Citations

26
checked on Apr 16, 2018

Page view(s)

26
checked on May 18, 2018

Google ScholarTM

Check

Altmetric


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