Algorithmic statistics revisited

DOI10.1007/978-3-319-21852-6_17zbMATH Open1336.62036arXiv1504.04950OpenAlexW1589181118WikidataQ57349389 ScholiaQ57349389MaRDI QIDQ2805729FDOQ2805729

Authors: A. Shen, Nikolai K. Vereshchagin 

Publication date: 13 May 2016

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

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.

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

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

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)

Cites Work

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

Cited In (12)

• Kolmogorov's Last Discovery? (Kolmogorov and Algorithmic Statistics)
• Title not available (Why is that?)
• Algorithmic statistics, prediction and machine learning
• Algorithmic statistics: normal objects and universal models
• Title not available (Why is that?)
• Title not available (Why is that?)
• Correction to "Algorithmic statistics"
• Winograd's algorithm statistically revisited: it pays to weigh than to count!
• Algorithmic statistics: forty years later
• Randomness Tests: Theory and Practice
• Inequalities for space-bounded Kolmogorov complexity
• Sophistication vs logical depth

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)