Bienvenu, Laurent ;
Hölzl, Rupert ;
Kräling, Thorsten ;
Merkle, Wolfgang
Contributed Papers
Separations of Nonmonotonic Randomness Notions
Abstract
In the theory of algorithmic randomness, several notions of random sequence are defined via a gametheoretic approach, and the notions that received most attention are perhaps MartinL\"of randomness
and computable randomness. The latter notion was introduced by Schnorr and is rather natural: an infinite binary sequence is computably random if no total computable strategy succeeds on it by betting on bits in order. However, computably random sequences can have properties that one may consider to be incompatible with being random, in particular, there are computably random sequences that are highly compressible. The concept of MartinL\"of randomness is much better behaved in this and other respects, on the other hand its definition in terms of martingales is considerably less natural.
Muchnik, elaborating on ideas of Kolmogorov and Loveland, refined Schnorr's model by also allowing nonmonotonic strategies, i.e.\ strategies that do not bet on bits in order. The subsequent ``nonmonotonic'' notion of randomness, now called KolmogorovLovelandrandomness, has been shown to be quite close to MartinL\"of randomness, but whether these two classes coincide remains a fundamental open question.
In order to get a better understanding of nonmonotonic randomness notions, Miller and Nies introduced some interesting intermediate concepts, where one only allows nonadaptive strategies, i.e., strategies that can still bet nonmonotonically, but such that the sequence of betting positions is known in advance (and computable). Recently, these notions were shown by Kastermans and Lempp to differ from MartinL\"of randomness. We continue the study of the nonmonotonic randomness notions introduced by Miller and Nies and obtain results about the Kolmogorov complexities of initial segments that may and may not occur for such sequences, where these results then imply a complete classification of these randomness notions by order of strength.
BibTeX  Entry
@InProceedings{bienvenu_et_al:OASIcs:2009:2260,
author = {Laurent Bienvenu and Rupert H{\"o}lzl and Thorsten Kr{\"a}ling and Wolfgang Merkle},
title = {{Separations of Nonmonotonic Randomness Notions}},
booktitle = {6th International Conference on Computability and Complexity in Analysis (CCA'09)},
series = {OpenAccess Series in Informatics (OASIcs)},
ISBN = {9783939897125},
ISSN = {21906807},
year = {2009},
volume = {11},
editor = {Andrej Bauer and Peter Hertling and KerI Ko},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2009/2260},
URN = {urn:nbn:de:0030drops22601},
doi = {10.4230/OASIcs.CCA.2009.2260},
annote = {Keywords: MartinL{\"o}f randomness, KolmogorovLoveland randomness, Kolmogorov complexity, martingales, betting strategies}
}
2009
Keywords: 

MartinLöf randomness, KolmogorovLoveland randomness, Kolmogorov complexity, martingales, betting strategies 
Seminar: 

6th International Conference on Computability and Complexity in Analysis (CCA'09)

Issue date: 

2009 
Date of publication: 

2009 