Source-linked AI summary
Computability of probability measures and Martin-Lof randomness over metric spaces
Mathieu Hoyrup, Cristobal Rojas
TL;DR
The paper asks how algorithmic randomness and probability-measure computability can be extended beyond Cantor space to computable metric spaces. It develops a unified framework and binary representations, showing that computable probability spaces can be related to Cantor space and that universal uniform randomness tests exist without extra conditions.
Problem
Algorithmic randomness was well established on Cantor space, but extending it to general spaces requires a computability theory for probability measures.
Method
The paper develops computability tools for probability measures and introduces binary representations for computable metric spaces with computable measures.
Results
Every computable probability space has a binary representation, and universal randomness tests exist without further conditions.
Takeaways & Limitations
The binary representation transfers algorithmic-randomness results from Cantor space, including randomness and Kolmogorov-complexity characterizations.
Takeaways & Limitations
The function-space framework does not generally extend partial constructive functions to total constructive ones, and the binary representation uses a dense full-measure set of points with unique expansions.
Abstract
from arXiv · showhide
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).
1 Introduction
The paper extends algorithmic randomness beyond Cantor space by developing computability tools for probability measures on computable metric spaces. It introduces binary representations that transfer randomness results and establishes universal randomness tests without additional conditions.
- Motivation: Algorithmic randomness is extended from Cantor space to computable metric spaces by first addressing computability of probability measures.The paper presents this as necessary for extending randomness to more general infinite objects.
- Randomness tests: Uniformity and non-uniformity do not essentially differ, and a universal randomness test exists without further conditions.These results apply when working in computable metric spaces with any probability measure.
- Binary representations: Every computable metric space with a computable probability measure admits a binary representation.This representation generalizes the base-two numeral system and supports a computable measure-theoretic identification with Cantor space.
- Binary representations: A point is random if and only if it has a unique random binary expansion.The binary representation also transfers the characterization of randomness through Kolmogorov complexity, including in non-compact spaces.
- Framework: The paper develops a unified framework for computability on measures, computable metric spaces, and enumerative lattices.Its structure covers computability foundations, enumerative lattices, probability measures, binary representations, and randomness.
2 Basic definitions
The paper fixes computational representations for sequences, represented spaces, and computable metric spaces, then derives the associated notions of constructive points, functions, and metric-space computation.
- Computational representations: Recursion-theoretic computation on sequences can be formalized through domain theory, oracle Turing machines, or type-two Turing machines.The paper treats these as alternative formalisms for computation on infinite sequences.
- Computational representations: A representation is a surjective partial map from infinite sequences to a set, and constructive elements are represented by recursive sequences.Constructive functions are realized by recursive transformations that commute with the representations.
- Computational representations: An algorithm is extensional on x when all names of x produce the same output, allowing it to x-describe an element of the target space.This local extensionality underlies computation on represented spaces.
- Computable metric spaces: A computable metric space consists of a separable complete metric space, a computable dense set of ideal points, and its Cauchy representation.Ideal balls provide a numbered basis for the topology, while products inherit a canonical computable metric structure.
- Computable metric spaces: The distance function is computable, and computable points admit equivalent characterizations using ideal-point distances and fast Cauchy descriptions.The canonical representation uses fast sequences of ideal points converging to the represented point.
3 Enumerative Lattices
Enumerative lattices provide a canonical representation for complete lattices generated by numbered basic elements, supporting uniform enumeration and constructive computation of functions from computable metric spaces.
- Enumerative lattices: An enumerative lattice is a complete lattice whose every element is the supremum of a subset of numbered basic elements.The canonical representation describes elements by sequences of basic elements, including the least element via an empty sequence.
- Examples: The framework applies to lower semi-computable reals and recursively enumerable sets as basic examples.These arise from the lattices of extended reals and subsets ordered by inclusion.
- Enumerative lattices: All constructive elements of an enumerative lattice can be enumerated uniformly.This uniform enumeration follows by enumerating recursively enumerable subsets of the numbered basic elements.
- Functions: For functions from a computable metric space to an enumerative lattice, constructive elements of the function space are exactly total constructive functions.The equivalence is constructive: evaluation and conversion between function descriptions and evaluating algorithms are both effective.
- Functions: A partial constructive function cannot generally be extended to a total constructive function.This is identified as a limitation specific to the enumerative-lattice structure.
- Open subsets: Semi-decidable subsets of a computable metric space are exactly recursively enumerable open sets.The corresponding enumerative lattices are constructively isomorphic.
4 Computing with probability measures
The paper equips probability measures on computable metric spaces with computable metric structures and characterizes computability through measures of effectively presented sets and integrals. For bounded spaces, Prokhorov and Wasserstein effectivizations are computably equivalent.
- Computable measures: The space of finitely supported rational measures forms a dense ideal basis for probability measures over a computable metric space.Computable measures are defined as constructive points in the resulting computable metric space.
- Metric structures: The Prokhorov metric metrizes weak convergence, and (M(X), D, ρ) is a computable metric space.Its computability follows from uniform computability of distances between ideal measures.
- Metric structures: For bounded X, the Prokhorov and Wasserstein metrics are computably equivalent, with computable identity maps in both directions.The Wasserstein effectivization is therefore also a computable metric space.
- Measures as valuations: Open-set measures are lower semi-computable from a Cauchy description, and this valuation property characterizes computability of the measure.The characterization applies equivalently to finite unions of ideal balls.
- Measures as valuations: A probability measure is computable exactly when measures of cylinders, rational open intervals, or suitable finite unions are uniformly lower semi-computable in the corresponding settings.For atomless measures, rational intervals have uniformly computable measures.
- Integration: Computability of a measure is also characterized by lower semi-computability of integrals of lower semi-computable functions and finite suprema of such functions.This extends the valuation characterization from sets to functionals.
5 Computable Probability Spaces
The paper defines computable probability spaces as computable metric spaces equipped with computable Borel probability measures, then generalizes binary expansions to them. Every such space admits a measure-theoretic computable representation by Cantor space on a dense full-measure domain.
- Definitions: A computable probability space is a computable metric space paired with a computable Borel probability measure.Morphisms are computable measure-preserving functions defined on full-measure domains.
- Generalized binary representations: Binary representations transfer Cantor-space coding to general computable probability spaces without requiring every binary sequence to represent a point.The latter requirement would force the space to be compact.
- Generalized binary representations: A dense full-measure Π0_2 set of points has unique binary expansions, while preimages of cylinders are clopen and decidable on the representation domain.Outside that domain, the corresponding sets are almost decidable rather than generally decidable.
- Generalized binary representations: Every computable probability space has a binary representation.The representation uses a computable measure on Cantor space and a surjective measure-preserving morphism.
- Almost decidability: Uniformly almost decidable balls can be chosen as a basis using a uniformly computable dense sequence of radii.The construction avoids radii whose spheres carry problematic boundary mass or coincide with ideal-point distances.
- Characterizing computability: Computability of a measure is equivalent to having a constructively equivalent basis of uniformly almost decidable open sets whose finite unions have uniformly computable measures.This supplies an alternative basis-based characterization.
6 Algorithmic randomness
The section develops uniform Martin-Löf randomness tests over computable metric spaces and establishes their universality, equivalence with measure-specific tests, and compatibility with computable probability-space morphisms and binary representations.
- Uniform tests: A uniform randomness test assigns a test to every probability measure, and each such test induces a measure-specific test.The framework treats tests as constructive functions from probability measures to lower-semi-computable functions on the space.
- Uniform tests: The two notions of uniform and non-uniform randomness tests are equivalent on any computable metric space.Every test for a fixed measure can be extended to a uniform test that agrees with it at that measure.
- Universal test: A universal uniform randomness test exists on every computable metric space, without the additional recognizable-Boolean-inclusion assumption used in earlier work.Earlier universality results required an extra computability property on the basis of ideal balls.
- Universal test: The universal test is constructed by effectively enumerating uniform tests and combining them with decreasing weights, while preserving the required integral bound.The construction uses a computable integration operator for finite suprema of basic functions and weights the tests by 2^-i−1.
- Random points: A point is µ-random exactly when it avoids the maximal µ-effective null set, equivalently when the universal test is finite at that point.The section also recovers the Martin-Löf presentation through threshold sets of lower-semi-computable tests.
- Computable probability spaces: Morphisms of computable probability spaces preserve randomness, and isomorphisms induce total computable bijections between the corresponding random-point sets.Binary representations likewise preserve the randomness notion and yield a Kolmogorov-complexity characterization via prefix complexity.
- Computable probability spaces: Every random point belongs to every recursively enumerable open set of full measure.The complement of such an open set can be converted into a Martin-Löf test, forcing random points to lie inside the original set.
Aknowledgments
The authors thank Stefano Galatolo, Peter Gács, and Giuseppe Longo for useful comments and remarks.
- Acknowledgments: The acknowledgments express thanks to Stefano Galatolo.
- Acknowledgments: The acknowledgments express thanks to Peter Gács.
- Acknowledgments: The acknowledgments express thanks to Giuseppe Longo for useful comments and remarks.