Show simple item record

dc.contributor.authorGacs, Peteren_US
dc.contributor.authorTromp, J.T.en_US
dc.contributor.authorVitanyi, P.M.B.en_US
dc.date.accessioned2018-06-13T16:02:28Z
dc.date.available2018-06-13T16:02:28Z
dc.date.issued2001-09-01
dc.identifierhttp://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.citationP Gacs, JT Tromp, PMB Vitanyi. 2001. "Algorithmic statistics." IEEE Transactions On Information Theory, Volume 47, Issue 6, pp. 2443 - 2463 (21).
dc.identifier.issn0018-9448
dc.identifier.urihttps://hdl.handle.net/2144/29381
dc.description.abstractWhile 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.extentp. 2443 - 2463en_US
dc.languageEnglish
dc.publisherIEEEen_US
dc.relation.ispartofIEEE Transactions On Information Theory
dc.subjectScience & technologyen_US
dc.subjectTechnologyen_US
dc.subjectComputer science, information systemsen_US
dc.subjectEngineering, electrical & electronicen_US
dc.subjectComputer scienceen_US
dc.subjectEngineeringen_US
dc.subjectAlgorithmic information theoryen_US
dc.subjectDescription format (explicit, implicit)en_US
dc.subjectFoundations of statisticsen_US
dc.subjectKolmogorov complexityen_US
dc.subjectMinimal sufficient statistic (algorithmic)en_US
dc.subjectMutual information (algorithmic)en_US
dc.subjectNonstochastic objectsen_US
dc.subjectSufficient statistic (algorithmic)en_US
dc.subjectTwo-part codesen_US
dc.subjectArtificial intelligence and image processingen_US
dc.subjectElectrical and electronic engineeringen_US
dc.subjectCommunications technologiesen_US
dc.subjectNetworking & telecommunicationsen_US
dc.titleAlgorithmic statisticsen_US
dc.typeArticleen_US
dc.identifier.doi10.1109/18.945257
pubs.elements-sourceweb-of-scienceen_US
pubs.notesEmbargo: No embargoen_US
pubs.organisational-groupBoston Universityen_US
pubs.organisational-groupBoston University, College of Arts & Sciencesen_US
pubs.organisational-groupBoston University, College of Arts & Sciences, Department of Computer Scienceen_US
pubs.publication-statusPublisheden_US


This item appears in the following Collection(s)

Show simple item record