2 Search Results for "Muchnik, Andrej"

Document

DOI: 10.4230/OASIcs.CCA.2009.2260

Separations of Non-monotonic Randomness Notions

Authors: Laurent Bienvenu, Rupert Hölzl, Thorsten Kräling, and Wolfgang Merkle

Published in: OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009)

Abstract

In the theory of algorithmic randomness, several notions of random sequence are defined via a game-theoretic approach, and the notions that received most attention are perhaps Martin-L\"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 Martin-L\"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 non-monotonic strategies, i.e.\ strategies that do not bet on bits in order. The subsequent ``non-monotonic'' notion of randomness, now called Kolmogorov-Loveland-randomness, has been shown to be quite close to Martin-L\"of randomness, but whether these two classes coincide remains a fundamental open question. In order to get a better understanding of non-monotonic randomness notions, Miller and Nies introduced some interesting intermediate concepts, where one only allows non-adaptive strategies, i.e., strategies that can still bet non-monotonically, 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 Martin-L\"of randomness. We continue the study of the non-monotonic 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.

Cite as

Laurent Bienvenu, Rupert Hölzl, Thorsten Kräling, and Wolfgang Merkle. Separations of Non-monotonic Randomness Notions. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 71-82, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{bienvenu_et_al:OASIcs.CCA.2009.2260,
  author =	{Bienvenu, Laurent and H\"{o}lzl, Rupert and Kr\"{a}ling, Thorsten and Merkle, Wolfgang},
  title =	{{Separations of Non-monotonic Randomness Notions}},
  booktitle =	{6th International Conference on Computability and Complexity in Analysis (CCA'09)},
  pages =	{71--82},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-12-5},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{11},
  editor =	{Bauer, Andrej and Hertling, Peter and Ko, Ker-I},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2260},
  URN =		{urn:nbn:de:0030-drops-22601},
  doi =		{10.4230/OASIcs.CCA.2009.2260},
  annote =	{Keywords: Martin-L\"{o}f randomness, Kolmogorov-Loveland randomness, Kolmogorov complexity, martingales, betting strategies}
}

Document

DOI: 10.4230/LIPIcs.STACS.2008.1335

Limit complexities revisited

Authors: Laurent Bienvenu, Andrej Muchnik, Alexander Shen, and Nikolay Veraschagin

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract

The main goal of this paper is to put some known results in a common perspective and to simplify their proofs. We start with a simple proof of a result from (Vereshchagin, 2002) saying that $limsup_{nKS(x|n)$ (here $KS(x|n)$ is conditional (plain) Kolmogorov complexity of $x$ when $n$ is known) equals $KS^{mathbf{0'(x)$, the plain Kolmogorov complexity with $mathbf{0'$-oracle. Then we use the same argument to prove similar results for prefix complexity (and also improve results of (Muchnik, 1987) about limit frequencies), a priori probability on binary tree and measure of effectively open sets. As a by-product, we get a criterion of $mathbf{0'$ Martin-L"of randomness (called also $2$-randomness) proved in (Miller, 2004): a sequence $omega$ is $2$-random if and only if there exists $c$ such that any prefix $x$ of $omega$ is a prefix of some string $y$ such that $KS(y)ge |y|-c$. (In the 1960ies this property was suggested in (Kolmogorov, 1968) as one of possible randomness definitions; its equivalence to $2$-randomness was shown in (Miller, 2004) while proving another $2$-randomness criterion (see also (Nies et al. 2005)): $omega$ is $2$-random if and only if $KS(x)ge |x|-c$ for some $c$ and infinitely many prefixes $x$ of $omega$. Finally, we show that the low-basis theorem can be used to get alternative proofs for these results and to improve the result about effectively open sets; this stronger version implies the $2$-randomness criterion mentioned in the previous sentence.

Cite as

Laurent Bienvenu, Andrej Muchnik, Alexander Shen, and Nikolay Veraschagin. Limit complexities revisited. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 73-84, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{bienvenu_et_al:LIPIcs.STACS.2008.1335,
  author =	{Bienvenu, Laurent and Muchnik, Andrej and Shen, Alexander and Veraschagin, Nikolay},
  title =	{{Limit complexities revisited}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{73--84},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1335},
  URN =		{urn:nbn:de:0030-drops-13350},
  doi =		{10.4230/LIPIcs.STACS.2008.1335},
  annote =	{Keywords: Kolmogorov complexity, limit complexities, limit frequencies, 2-randomness, low basis}
}

Refine by Author
2 Bienvenu, Laurent
1 Hölzl, Rupert
1 Kräling, Thorsten
1 Merkle, Wolfgang
1 Muchnik, Andrej
Show More...

Refine by Classification

Refine by Keyword
2 Kolmogorov complexity
1 2-randomness
1 Kolmogorov-Loveland randomness
1 Martin-Löf randomness
1 betting strategies
Show More...

Refine by Type
2 document

Refine by Publication Year
1 2008
1 2009

2 Search Results for "Muchnik, Andrej"

Separations of Non-monotonic Randomness Notions

Abstract

Cite as

Limit complexities revisited

Abstract

Cite as

Thanks for your feedback!

Could not send message