Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/40418
Title: Kolmogorov-Loveland randomness and stochasticity
Authors: Merkle, W.
Miller, J.
Nies, A.
Reimann, J.
Stephan, F. 
Issue Date: 2005
Source: Merkle, W.,Miller, J.,Nies, A.,Reimann, J.,Stephan, F. (2005). Kolmogorov-Loveland randomness and stochasticity. Lecture Notes in Computer Science 3404 : 422-433. ScholarBank@NUS Repository.
Abstract: One of the major open problems in the field of effective randomness is whether Martin-Löf randomness is the same as Kolmogorov-Loveland (or KL) randomness, where an infinite binary sequence is KL-random if there is no computable non-monotonic betting strategy that succeeds on the sequence in the sense of having an unbounded gain in the limit while betting successively on bits of the sequence. Our first main result states that every KL-random sequence has arbitrarily dense, easily extractable subsequences that are Martin-Löf 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-Löf random. We show that this splitting property does not characterize KL-randomness by constructing a sequence that is not even computably random such that every effective split yields subsequences that are 2-random, hence are in particular Martin-Löf random. A sequence X is KL-stochastic if there is no computable non-monotonic selection rule that selects from X an infinite, biased sequence. Our second main result asserts that every KL-stochastic sequence has constructive 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 with respect to prefix-free Kolmogorov complexity. This improves on a result by Muchnik, who has shown a similar implication where the premise requires that such compressible prefixes can be found effectively. © Springer-Verlag Berlin Heidelberg 2005.
Source Title: Lecture Notes in Computer Science
URI: http://scholarbank.nus.edu.sg/handle/10635/40418
ISSN: 03029743
Appears in Collections:Staff Publications

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

Page view(s)

63
checked on Jan 12, 2018

Google ScholarTM

Check


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