Algorithmic statistics revisited

DOI10.1007/978-3-319-21852-6_17MaRDI QIDQ2805729zbMATHOpenAlexWikidataFDO

Authors A. Shen, Nikolai K. Vereshchagin

Publication date 13 May 2016

Published in Measures of Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.04950

Mathematics Subject Classification ID

Statistical aspects of information-theoretic topics (62B10) Foundations and philosophical topics in statistics (62A01) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: The mission of statistics is to provide adequate statistical hypotheses (models) for observed data. But what is an "adequate" model? To answer this question, one needs to use the notions of algorithmic information theory. It turns out that for every data string $x$ one can naturally define "stochasticity profile", a curve that represents a trade-off between complexity of a model and its adequacy. This curve has four different equivalent definitions in terms of (1)~randomness deficiency, (2)~minimal description length, (3)~position in the lists of simple strings and (4)~Kolmogorov complexity with decompression time bounded by busy beaver function. We present a survey of the corresponding definitions and results relating them to each other.

Recommendations

• Algorithmic statistics: forty years later
• Algorithmic statistics
• scientific article; zbMATH DE number 2080439
• Algorithmic statistics, prediction and machine learning
• Algorithmic statistics: normal objects and universal models

Cites work

• scientific article; zbMATH DE number 3860059 (Why is no real title available?)
• A universal prior for integers and estimation by minimum description length
• Algorithmic Information Theory
• Algorithmic minimal sufficient statistic revisited
• An introduction to Kolmogorov complexity and its applications
• Combinatorial interpretation of Kolmogorov complexity
• Computational depth: Concept and applications
• Does snooping help?
• Inequalities for Shannon entropy and Kolmogorov complexity
• Kolmogorov's Structure Functions and Model Selection
• Mathematical metaphysics of randomness
• Nonstochastic estimates
• Randomness conservation inequalities; information and independence in mathematical theories
• Rate Distortion and Denoising of Individual Data Using Kolmogorov Complexity
• Stability of properties of Kolmogorov complexity under relativization

Cited in

(12)

• Kolmogorov's Last Discovery? (Kolmogorov and Algorithmic Statistics)
• scientific article; zbMATH DE number 194187 (Why is no real title available?)
• scientific article; zbMATH DE number 194221 (Why is no real title available?)
• scientific article; zbMATH DE number 3896283 (Why is no real title available?)
• Inequalities for space-bounded Kolmogorov complexity
• Correction to "Algorithmic statistics"
• Algorithmic statistics, prediction and machine learning
• Sophistication vs logical depth
• Winograd's algorithm statistically revisited: it pays to weigh than to count!
• Algorithmic statistics: normal objects and universal models
• Randomness Tests: Theory and Practice
• Algorithmic statistics: forty years later

This page was built for publication: Algorithmic statistics revisited

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2805729)