Given a computable probability measure P over natural numbers or infinite binary sequences, there is no computable, randomized method that can produce an arbitrarily large sample such that none of its members are outliers of P.
Information conservation laws were introduced and studied in @cite_15 @cite_8 . Information asymmetry and the complexity of complexity were studied in @cite_0 . A history of the origin of the mutual information of a string with the halting sequence can be found in @cite_23 .
@cite_0 @cite_15 @cite_23 @cite_8
2170025089 123681027 2104359186 2041517255
We say that the mutual information of a triple of binary strings a, b, c can be extracted if there exists a string d such that a, b, and c are independent given d, and d is simple conditional to each of the strings a, b, c. This is an analog of the well-known Gacs-Korner (1973) definition of extrability of the mutual information for a pair of binary strings. We prove that (in contrast to the case of two strings) there exists a criterion of extrability of the mutual information for a triple a, b, c in terms of complexities involving a, b, c. Roughly speaking, the mutual information between a, b, c can be extracted if and only if the conditional mutual informations I(a:b|c), I(a:c|b), I(b:c|a) are negligible. Our proof of the main result is based on a nonShannon-type information inequality, which is a generalization of the recently discovered Zhang-Yeung inequality. In 1974, Kolmogorov proposed a nonprobabilistic approach to statistics and model selection. Let data be finite binary strings and models be finite sets of binary strings. Consider model classes consisting of models of given maximal (Kolmogorov) complexity. The "structure function" of the given data expresses the relation between the complexity level constraint on a model class and the least log-cardinality of a model in the class containing the data. We show that the structure function determines all stochastic properties of the data: for every constrained model class it determines the individual best fitting model in the class irrespective of whether the "true" model is in the model class considered or not. In this setting, this happens with certainty, rather than with high probability as is in the classical case. We precisely quantify the goodness-of-fit of an individual model with respect to individual data. We show that-within the obvious constraints-every graph is realized by the structure function of some data. We determine the (un)computability properties of the various functions contemplated and of the "algorithmic minimal sufficient statistic.". The article further develops Kolmogorov's algorithmic complexity theory. The definition of randomness is modified to satisfy strong invariance properties (conservation inequalities). This allows definitions of concepts such as mutual information in individual infinite sequences. Applications to several areas, like probability theory, theory of algorithms, intuitionistic logic are considered. These theories are simplified substantially with the postulate that the objects they consider are independent of (have small mutual information with) any sequence specified by a mathematical property.