abstract
algorithmic statistics has two different (and almost orthogonal) motivations. from the philosophical point of view, it tries to formalize how the
statistics works and why some statistical models are better than others. after
this notion of a “good model” is introduced, a natural question arises: it is
possible that for some piece of data there is no good model? if yes, how often
these bad (non-stochastic) data appear “in real life”?
another, more technical motivation comes from algorithmic information
theory. in this theory a notion of complexity of a finite object (=amount of
information in this object) is introduced; it assigns to every object some number, called its algorithmic complexity (or kolmogorov complexity). algorithmic
statistic provides a more fine-grained classification: for each finite object some
curve is defined that characterizes its behavior. it turns out that several different definitions give (approximately) the same curve.1
in this survey we try to provide an exposition of the main results in the field
(including full proofs for the most important ones), as well as some historical
comments. we assume that the reader is familiar with the main notions of
algorithmic information (kolmogorov complexity) theory. an exposition can
be found in [44, chapters 1, 3, 4] or [22, chapters 2, 3], see also the survey [37].
∗