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

    Uniform test of algorithmic randomness over a general space

    Thumbnail
    Date Issued
    2005-09-05
    Publisher Version
    10.1016/j.tcs.2005.03.054
    Author(s)
    Gacs, Peter
    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/29417
    Citation (published version)
    P Gacs. 2005. "Uniform test of algorithmic randomness over a general space." Theoretical Computer Science, Volume 341, Issue 1-3, pp. 91 - 137 (47). https://doi.org/10.1016/j.tcs.2005.03.054
    Abstract
    The algorithmic theory of randomness is well developed when the underlying space is the set of finite or infinite sequences and the underlying probability distribution is the uniform distribution or a computable distribution. These restrictions seem artificial. Some progress has been made to extend the theory to arbitrary Bernoulli distributions (by Martin-Löf) and to arbitrary distributions (by Levin). We recall the main ideas and problems of Levin's theory, and report further progress in the same framework. The issues are the following: Allow non-compact spaces (like the space of continuous functions, underlying the Brownian motion). The uniform test (deficiency of randomness) (depending both on the outcome x and the measure P) should be defined in a general and natural way. See which of the old results survive: existence of universal tests, conservation of randomness, expression of tests in terms of description complexity, existence of a universal measure, expression of mutual information as “deficiency of independence”. The negative of the new randomness test is shown to be a generalization of complexity in continuous spaces; we show that the addition theorem survives. The paper's main contribution is introducing an appropriate framework for studying these questions and related ones (like statistics for a general family of distributions).
    Collections
    • BU Open Access Articles [3866]
    • CAS: Computer Science: Scholarly Papers [189]

    Related items

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

    • Thumbnail

      Contribution of leaf specular reflection to canopy reflectance under black soil case using stochastic radiative transfer model 

      Yang, Bin; Knyazikhin, Yuri; Zhao, Haimeng; Ma, Yuzhong (Elsevier Science BV, 2018-12-15)
      Numerous canopy radiative transfer models have been proposed based on the assumption of “ideal bi-Lambertian leaves” with the aim of simplifying the interactions between photons and vegetation canopies. This assumption may ...
    • Thumbnail

      Integrating archaeology and ancient DNA analysis to address invasive species colonization in the Gulf of Alaska 

      West, Catherine; Hofman, Courtney A.; Ebbert, Steve; Martin, John; Shirazi, Sabrina; Dunning, Samantha; Maldonado, Jesus E. (WILEY, 2017-10-01)
      The intentional and unintentional movement of plants and animals by humans has transformed ecosystems and landscapes globally. Assessing when and how a species was introduced are central to managing these transformed ...
    • Thumbnail

      Size-resolved aerosol fluxes above a temperate broadleaf forest 

      Petroff, A.; Murphy, J.G.; Thomas, S.C.; Geddes, Jeffrey A. (PERGAMON-ELSEVIER SCIENCE LTD, 2018-10-01)
      Aerosol fluxes were measured by eddy-correlation for 8 weeks of the summer and fall of 2011 above a temperate broadleaf forest in central Ontario, Canada. These size-resolved measurements apply to particles with optical ...

    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