Computability of probability measures and Martin-Löf randomness over metric spaces

In this paper, we investigate algorithmic randomness on more general spaces than the Cantor space, namely computable metric spaces. To do this, we first develop a unified framework allowing computations with probability measures. We show that any computable metric space with a computable probability measure is isomorphic to the Cantor space in a computable and measure-theoretic sense. We show that any computable metric space admits a universal uniform randomness test (without further assumption).

• Publication year

  2007

• Venue

  Information and Computation

• Publication date

  2007-09-06

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.ic.2008.12.009arXiv 0709.0907
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Connectivity properties of dimension level sets

  2008cited by this paper
• Algorithmically random points in measure preserving systems, statistical behaviour, complexity and entropy

  2008cited by this paper
• Computability, Randomness and Ergodic Theory on Metric Spaces

  2008cited by this paper
• Dynamics of a generic Brownian motion: Recursive aspects

  2008cited by this paper
• A constructive Borel-Cantelli lemma. Constructing orbits with required statistical properties

  2007cited by this paper
• Effective symbolic dynamics, random points, statistical behavior, complexity and entropy

  2007cited by this paper
• An effective Borel-Cantelli Lemma. Constructing orbits with required statistical properties

  2007cited by this paper
• Admissible representations for probability measures

  2007cited by this paper
• Random Closed Sets

  2006cited by this paper
• Computable Analysis

  2005cited by this paper
• Gradient Flows: In Metric Spaces and in the Space of Probability Measures

  2005cited by this paper
• Random elements in effective topological spaces with measure

  2003cited by this paper
• Uniform test of algorithmic randomness over a general space

  2003influential reference
• Computability on subsets of metric spaces

  2003cited by this paper
• What Are SRB Measures, and Which Dynamical Systems Have Them?

  2002cited by this paper
• Effective metric spaces and representations of the reals

  2002cited by this paper
• Computable Versions of Baire's Category Theorem

  2001cited by this paper
• Arithmetical representations of Brownian motion I

  2000cited by this paper
• Computability on Subsets of Euclidean Space I: Closed and Compact Subsets

  1999cited by this paper
• Effective Properties of Sets and Functions in Metric Spaces with Computability Structure

  1999cited by this paper
• A Computational Model for Metric Spaces

  1998cited by this paper
• Effective Convergence in Probability and an Ergodic Theorem forIndividual Random Sequences

  1998cited by this paper
• Randomness Spaces

  1998cited by this paper
• Эффективная сходимость по вероятности и эргодическая теорема для индивидуальных случайных последовательностей@@@Effective convergence in probability and an ergodic theorem for individual random sequences

  1997cited by this paper
• Computability on the Probability Measureson the Borel Sets of the Unit Interval

  1997cited by this paper
• The Scott topology induces the weak topology

  1996cited by this paper
• Domain theory

  1995cited by this paper
• On the Empirical Validity of the Bayesian Method

  1993cited by this paper
• Computability on Computable Metric Spaces

  1993cited by this paper
• Complexity theory of real functions

  1992cited by this paper
• Degrees of random sets

  1991cited by this paper
• Algorithmic information theory

  1989cited by this paper
• Computational Complexity of Real Functions

  1985cited by this paper
• Review: P. Billingsley, Convergence of probability measures

  1971influential reference
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS

  1970cited by this paper
• Theory of Recursive Functions and Effective Computability.

  1969cited by this paper
• The Definition of Random Sequences

  1966influential reference

• Ulam Meets Turing: Constructing Quadratic Maps with Non-Computable Physical Measures

  2026cites this paper
• Computability of $\mathcal{G}$-Beroulli Measures and Measures of Maximal Entropy on Coded Shift Spaces

  2026cites this paper
• Fractal dimensions and profinite groups

  2025cites this paper
• Computable thermodynamic formalism

  2025influential citation
• Schnorr Randomness and Effective Bayesian Consistency and Inconsistency

  2025influential citation
• Bayesian Convergence for Computably Bounded Agents

  2025cites this paper
• A computable von Neumann-Morgenstern representation theorem

  2025influential citation
• Computability for Axiom A Polynomial Skew Products of $\mathbb{C}^2$

  2025cites this paper
• Irreversibility and randomness

  2025cites this paper
• Pride and Probability

  2024cites this paper
• Dynamic Probability Logic: Decidability & Computability

  2024influential citation
• Semi-Classical Subspaces, The No Synchronization Law, and More

  2024cites this paper
• Effective weak convergence and tightness of measures in computable Polish spaces

  2024influential citation
• Algorithmic Randomness and Probabilistic Laws

  2023cites this paper
• On the algorithmic descriptive complexity of attractors in topological dynamics

  2023cites this paper
• On Computability of Equilibrium States

  2023influential citation
• Computability in Dynamical Systems

  2023cites this paper
• The Randomness Deficiency Function and the Shift Operator

  2023cites this paper
• Typical = Random

  2023cites this paper
• COMPUTABLY COMPACT METRIC SPACES

  2023cites this paper
• Deterministic stream-sampling for probabilistic programming: semantics and verification

  2023cites this paper
• On the Algorithmic Information Between Probabilities

  2023cites this paper
• Uniform Tests and Algorithmic Thermodynamic Entropy

  2023influential citation
• Computable PAC Learning of Continuous Features

  2022cites this paper
• On local times of Martin-Löf random Brownian motion

  2022cites this paper
• EFFECTIVELY COMPACT SPACES

  2022cites this paper
• Computability of convergence rates in the ergodic theorem for Martin-Löf random points

  2022influential citation
• Ergodic Theorems and Converses for PSPACE Functions

  2022cites this paper
• Realizing semicomputable simplices by computable dynamical systems

  2022cites this paper
• Ergodic theorems for algorithmically random points

  2022influential citation
• Effective aspects of Hausdorff and Fourier dimension

  2021cites this paper
• Randomness and initial segment complexity for measures

  2021cites this paper
• SOME QUESTIONS OF UNIFORMITY IN ALGORITHMIC RANDOMNESS

  2021cites this paper
• Constructing the space of valuations of a quasi-Polish space as a space of ideals

  2021cites this paper
• Computable Measure Theory and Algorithmic Randomness

  2021cites this paper
• Effective notions of weak convergence of measures on the real line

  2021cites this paper
• Effective weak and vague convergence of measures on the real line

  2021cites this paper
• On computable learning of continuous features

  2021cites this paper
• An Ergodic Theorem for PSPACE functions

  2020cites this paper
• 2020 NORTH AMERICAN ANNUAL MEETING OF THE ASSOCIATION FOR SYMBOLIC LOGIC University of California, Irvine Irvine, California, USA March 25–28, 2020

  2020cites this paper
• Algorithmic randomness and layerwise computability

  2020cites this paper
• Computable Random Variables and Conditioning

  2020cites this paper
• Randomness and Computation

  2020cites this paper
• Noncomputable Coding, Density, and Stochasticity

  2020cites this paper
• LUZIN’S (N) AND RANDOMNESS REFLECTION

  2020cites this paper
• Algorithmic barriers to representing conditional independence

  2019cites this paper
• Microscopic Reversibility and Macroscopic Irreversibility: From the Viewpoint of Algorithmic Randomness

  2019cites this paper
• Computability

  2019influential citation
• Randomized Computation of Continuous Data: Is Brownian Motion Computable?

  2019cites this paper
• Computability and Randomness

  2019cites this paper
• Randomness and Initial Segment Complexity for Probability Measures

  2019cites this paper
• A weak randomness notion for probability measures

  2019cites this paper
• On the close interaction between algorithmic randomness and constructive/computable measure theory

  2018influential citation
• Formulation of Composite Discrete Measures for Estimating Uncertainties in Probabilistic Databases

  2018cites this paper
• Effective randomness for continuous measures

  2018cites this paper
• Dugundji systems and a retract characterization of effective zero-dimensionality

  2018cites this paper
• On the computability of graphons

  2018cites this paper
• An Application of Computable Distributions to the Semantics of Probabilistic Programs

  2018influential citation
• Construction and Simulation of Composite Measures and Condensation Model for Designing Probabilistic Computational Applications

  2018cites this paper
• Effective Hausdorff Dimension in General Metric Spaces

  2018cites this paper
• On Effective Birkhoff’s Ergodic Theorem for Computable Actions of Amenable Groups

  2017cites this paper
• On the computability of rotation sets and their entropies

  2017cites this paper
• On Programming Languages for Probabilistic Modeling

  2017influential citation
• Logic Blog 2016

  2017cites this paper
• Computable Geometric Complex Analysis and Complex Dynamics

  2017cites this paper
• Martin-Löf random generalized Poisson processes

  2017cites this paper
• Effective Brenier Theorem : Applications to Computable Analysis and Algorithmic Randomness

  2016cites this paper
• Computability on measurable functions

  2016influential citation
• Schnorr randomness for noncomputable measures

  2016influential citation
• Logic Blog 2015f

  2016cites this paper
• An Application of Computable Distributions to the Semantics of Probabilistic Programming Languages

  2016cites this paper
• When does randomness come from randomness?

  2015cites this paper
• Weihrauch-completeness for layerwise computability

  2015cites this paper
• On computability and disintegration

  2015cites this paper
• An application of computable distributions to the semantics of probabilistic programs

  2015cites this paper
• Space-bounded Church-Turing thesis and computational tractability of closed systems

  2015cites this paper
• Computable randomness and monotonicity

  2015cites this paper
• The descriptive complexity of stochastic integration

  2015cites this paper
• Algorithmic Aspects of Lipschitz Functions

  2014cites this paper
• Lecture notes on descriptional complexity and randomness

  2014cites this paper
• Effective dimension in some general metric spaces

  2014cites this paper
• On the Set of Ideal Points in Computable Metric Spaces (The present situation of set-theoretic and geometric topology and its prospects)

  2014cites this paper
• Using Almost-everywhere theorems from Analysis to Study Randomness

  2014cites this paper
• On Stability Property of Probability Laws with Respect to Small Violations of Algorithmic Randomness

  2014cites this paper
• Probability, statistics and computation in dynamical systems

  2014cites this paper
• Algorithmic randomness for Doob's martingale convergence theorem in continuous time

  2014cites this paper
• Representations of measurable sets in computable measure theory

  2014cites this paper
• Kolmogorov complexity and the geometry of Brownian motion

  2014influential citation
• How constructive is constructing measures?

  2014cites this paper
• Diophantine properties of brownian motion: recursive aspects

  2014cites this paper
• Ornstein Isomorphism and Algorithmic Randomness

  2014influential citation
• Fourier spectra of measures associated with algorithmically random Brownian motion

  2014cites this paper
• Algorithmic randomness over general spaces

  2014cites this paper
• Probabilistic computability and choice

  2013cites this paper
• Schnorr randomness and the Lebesgue differentiation theorem

  2013cites this paper
• Computability of the ergodic decomposition

  2013cites this paper
• L1-Computability, Layerwise Computability and Solovay Reducibility

  2013cites this paper
• On the computability of a construction of Brownian motion†

  2013cites this paper
• Randomness for non-computable measures

  2013cites this paper
• ALGORITHMIC RANDOMNESS, MARTINGALES AND DIFFERENTIABILITY

  2013influential citation