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 nonstochastic 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 superlogarithmically 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:117:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770408},
ISSN = {18688969},
year = {2017},
volume = {79},
editor = {Ryan O'Donnell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7522},
URN = {urn:nbn:de:0030drops75222},
doi = {10.4230/LIPIcs.CCC.2017.17},
annote = {Keywords: Algorithmic Statistics, Kolmogorov complexity, elusive set, distinguishing complexity}
}
2017
Keywords: 

Algorithmic Statistics, Kolmogorov complexity, elusive set, distinguishing complexity 
Seminar: 

32nd Computational Complexity Conference (CCC 2017)

Issue date: 

2017 
Date of publication: 

2017 