dc.contributor.author Gacs, Peter en_US dc.contributor.author Tromp, J.T. en_US dc.contributor.author Vitanyi, P.M.B. en_US dc.date.accessioned 2018-06-13T16:02:28Z dc.date.available 2018-06-13T16:02:28Z dc.date.issued 2001-09-01 dc.identifier http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000170717700020&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=6e74115fe3da270499c3d65c9b17d654 dc.identifier.citation P Gacs, JT Tromp, PMB Vitanyi. 2001. "Algorithmic statistics." IEEE Transactions On Information Theory, Volume 47, Issue 6, pp. 2443 - 2463 (21). dc.identifier.issn 0018-9448 dc.identifier.uri https://hdl.handle.net/2144/29381 dc.description.abstract While Kolmogorov (1965, 1983) complexity is the accepted absolute measure of information content of an individual finite object, a similarly absolute notion is needed for the relation between an individual data sample and an individual model summarizing the information in the data, for example, a finite set (or probability distribution) where the data sample typically came from. The statistical theory based on such relations between individual objects can be called algorithmic statistics, in contrast to classical statistical theory that deals with relations between probabilistic ensembles. We develop the algorithmic theory of statistic, sufficient statistic, and minimal sufficient statistic. This theory is based on two-part codes consisting of the code for the statistic (the model summarizing the regularity, the meaningful information, in the data) and the model-to-data code. In contrast to the situation in probabilistic statistical theory, the algorithmic relation of (minimal) sufficiency is an absolute relation between the individual model and the individual data sample. We distinguish implicit and explicit descriptions of the models. We give characterizations of algorithmic (Kolmogorov) minimal sufficient statistic for all data samples for both description modes-in the explicit mode under some constraints. We also strengthen and elaborate on earlier results for the "Kolmogorov structure function" and "absolutely nonstochastic objects"-those objects for which the simplest models that summarize their relevant information (minimal sufficient statistics) are at least as complex as the objects themselves. We demonstrate a close relation between the probabilistic notions and the algorithmic ones: (i) in both cases there is an "information non-increase" law; (ii) it is shown that a function is a probabilistic sufficient statistic iff it is with high probability (in an appropriate sense) an algorithmic sufficient statistic. en_US dc.format.extent p. 2443 - 2463 en_US dc.language English dc.publisher IEEE en_US dc.relation.ispartof IEEE Transactions On Information Theory dc.subject Science & technology en_US dc.subject Technology en_US dc.subject Computer science, information systems en_US dc.subject Engineering, electrical & electronic en_US dc.subject Computer science en_US dc.subject Engineering en_US dc.subject Algorithmic information theory en_US dc.subject Description format (explicit, implicit) en_US dc.subject Foundations of statistics en_US dc.subject Kolmogorov complexity en_US dc.subject Minimal sufficient statistic (algorithmic) en_US dc.subject Mutual information (algorithmic) en_US dc.subject Nonstochastic objects en_US dc.subject Sufficient statistic (algorithmic) en_US dc.subject Two-part codes en_US dc.subject Artificial intelligence and image processing en_US dc.subject Electrical and electronic engineering en_US dc.subject Communications technologies en_US dc.subject Networking & telecommunications en_US dc.title Algorithmic statistics en_US dc.type Article en_US dc.identifier.doi 10.1109/18.945257 pubs.elements-source web-of-science en_US pubs.notes Embargo: No embargo en_US pubs.organisational-group Boston University en_US pubs.organisational-group Boston University, College of Arts & Sciences en_US pubs.organisational-group Boston University, College of Arts & Sciences, Department of Computer Science en_US pubs.publication-status Published en_US
﻿