License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2017.17
URN: urn:nbn:de:0030-drops-75222
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7522/
Milovanov, Alexey ;
Vereshchagin, Nikolay
Stochasticity in Algorithmic Statistics for Polynomial Time
Abstract
A fundamental notion in Algorithmic Statistics is that of a stochastic object, i.e., an object having a simple plausible explanation.
Informally, a probability distribution is a plausible explanation for x if it looks likely that x was drawn at random with respect to that distribution.
In this paper, we suggest three definitions of a plausible statistical hypothesis for Algorithmic Statistics with polynomial time bounds, which are called acceptability, plausibility and optimality. Roughly speaking, a probability distribution m is called an acceptable explanation for x, if x possesses all properties decidable by short programs in a short time and shared by almost all objects (with respect to m). Plausibility is a similar notion, however this time
we require x to possess all properties T decidable even by long programs in a short time and shared by almost all objects. To compensate the increase in program length, we strengthen the notion of `almost all' - the longer the program recognizing the property is, the more objects must share the property. Finally, a probability distribution m is called an optimal explanation for x if m(x) is large.
Almost all our results hold under some plausible complexity theoretic assumptions. Our main result states that for acceptability and plausibility there are infinitely many non-stochastic objects, i.e. objects that do not have simple plausible (acceptable) explanations. Using the same techniques, we show that the distinguishing complexity of a string x can be super-logarithmically less than the conditional complexity of x with condition r for almost all r (for polynomial time bounded programs). Finally, we study relationships between the introduced notions.
BibTeX - Entry
@InProceedings{milovanov_et_al:LIPIcs:2017:7522,
author = {Alexey Milovanov and Nikolay Vereshchagin},
title = {{Stochasticity in Algorithmic Statistics for Polynomial Time}},
booktitle = {32nd Computational Complexity Conference (CCC 2017)},
pages = {17:1--17:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-040-8},
ISSN = {1868-8969},
year = {2017},
volume = {79},
editor = {Ryan O'Donnell},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7522},
URN = {urn:nbn:de:0030-drops-75222},
doi = {10.4230/LIPIcs.CCC.2017.17},
annote = {Keywords: Algorithmic Statistics, Kolmogorov complexity, elusive set, distinguishing complexity}
}
|
Keywords: |
|
Algorithmic Statistics, Kolmogorov complexity, elusive set, distinguishing complexity |
|
Collection: |
|
32nd Computational Complexity Conference (CCC 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
01.08.2017 |
