Boston University Libraries OpenBU
    JavaScript is disabled for your browser. Some features of this site may not work without it.
    View Item 
    •   OpenBU
    • BU Open Access Articles
    • BU Open Access Articles
    • View Item
    •   OpenBU
    • BU Open Access Articles
    • BU Open Access Articles
    • View Item

    Algorithmic statistics

    Thumbnail
    Date Issued
    2001-09-01
    Publisher Version
    10.1109/18.945257
    Author(s)
    Gacs, Peter
    Tromp, J.T.
    Vitanyi, P.M.B.
    Share to FacebookShare to TwitterShare by Email
    Export Citation
    Download to BibTex
    Download to EndNote/RefMan (RIS)
    Metadata
    Show full item record
    Permanent Link
    https://hdl.handle.net/2144/29381
    Citation (published version)
    P Gacs, JT Tromp, PMB Vitanyi. 2001. "Algorithmic statistics." IEEE Transactions On Information Theory, Volume 47, Issue 6, pp. 2443 - 2463 (21).
    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.
    Collections
    • CAS: Computer Science: Scholarly Papers [187]
    • BU Open Access Articles [3732]

    Related items

    Showing items related by title, author, creator and subject.

    • Thumbnail

      On distributed virtual network embedding with guarantees 

      Esposito, Flavio; Di Paola, Donato; Matta, Ibrahim (Computer Science Department, Boston University, 2014-01-10)
      To provide wide-area network services, resources from different infrastructure providers are needed. Leveraging the consensus-based resource allocation literature, we propose a general distributed auction mechanism for the ...
    • Thumbnail

      Accelerated extra-gradient descent: a novel accelerated first-order method 

      Orecchia, Lorenzo; Diakonikolas, Jelena (2018)
      We provide a novel accelerated first-order method that achieves the asymptotically optimal convergence rate for smooth functions in the first-order oracle model. To this day, Nesterov’s Accelerated Gradient Descent (agd) ...
    • Thumbnail

      Automated analysis of 16-color polychromatic flow cytometry data maps immune cell populations and reveals a distinct inhibitory receptor signature in systemic sclerosis 

      Belkina, Anna; Fleury, Michelle; Vazques Mateo, Christina; Raval, Forum; Lafyatis, Robert; Dooms, Hans; Snyder-Cappione, Jennifer (2015-06)
      Background. The phenotypic profiles of both peripheral blood and tissue-resident immune cells have been linked to the health status of individuals with infectious and autoimmune diseases, as well as cancer. In light of the ...

    Boston University
    Contact Us | Send Feedback | Help
     

     

    Browse

    All of OpenBUCommunities & CollectionsIssue DateAuthorsTitlesSubjectsThis CollectionIssue DateAuthorsTitlesSubjects

    Deposit Materials

    LoginNon-BU Registration

    Statistics

    Most Popular ItemsStatistics by CountryMost Popular Authors

    Boston University
    Contact Us | Send Feedback | Help