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

DOI10.1016/j.ic.2008.12.009zbMath1167.68023OpenAlexW2101900964MaRDI QIDQ2389335

Publication date: 15 July 2009

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2008.12.009

zbMATH Keywords

computability algorithmic randomness Kolmogorov-Chaitin complexity computable metric space universal test almost computable function computable probability measure enumerative lattice

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Applications of computability and recursion theory (03D80)

Related Items

On stability of probability laws with respect to small violations of algorithmic randomness ⋮ Computability of convergence rates in the ergodic theorem for Martin-Löf random points ⋮ When does randomness come from randomness? ⋮ UNIVERSAL CODING AND PREDICTION ON ERGODIC RANDOM POINTS ⋮ Computability and Dynamical Systems ⋮ Effective aspects of Hausdorff and Fourier dimension ⋮ Statistical properties of dynamical systems -- Simulation and abstract computation ⋮ LUZIN’S (N) AND RANDOMNESS REFLECTION ⋮ USING ALMOST-EVERYWHERE THEOREMS FROM ANALYSIS TO STUDY RANDOMNESS ⋮ Schnorr randomness for noncomputable measures ⋮ Realizing semicomputable simplices by computable dynamical systems ⋮ On local times of Martin-Löf random Brownian motion ⋮ On computability and disintegration ⋮ Ergodic theorems and converses for PSPACE functions ⋮ Effective weak and vague convergence of measures on the real line ⋮ Martin-Löf random generalized Poisson processes ⋮ A constructive version of Birkhoff's ergodic theorem for Martin-Löf random points ⋮ COMPUTABLY COMPACT METRIC SPACES ⋮ Computability on measurable functions ⋮ Characterization of Kurtz randomness by a differentiation theorem ⋮ Independence, relative randomness, and PA degrees ⋮ Computability of Brolin-Lyubich measure ⋮ The descriptive complexity of stochastic integration ⋮ On the computability of a construction of Brownian motion ⋮ An Application of Martin-Löf Randomness to Effective Probability Theory ⋮ Algorithmic randomness over general spaces ⋮ Randomness on computable probability spaces -- a dynamical point of view ⋮ Uncomputably noisy ergodic limits ⋮ Probability, statistics and computation in dynamical systems ⋮ Kolmogorov complexity and the geometry of Brownian motion ⋮ Algorithmic randomness, reverse mathematics, and the dominated convergence theorem ⋮ On effective Birkhoff's ergodic theorem for computable actions of amenable groups ⋮ Effective Hausdorff dimension in general metric spaces ⋮ Microscopic reversibility and macroscopic irreversibility: from the viewpoint of algorithmic randomness ⋮ Algorithmic tests and randomness with respect to a class of measures ⋮ An Application of Computable Distributions to the Semantics of Probabilistic Programming Languages ⋮ On the computability of rotation sets and their entropies ⋮ A constructive Borel-Cantelli lemma. Constructing orbits with required statistical properties ⋮ Randomness and the Ergodic Decomposition ⋮ Computability of the Radon-Nikodym Derivative ⋮ Randomness and initial segment complexity for measures ⋮ Computable randomness and betting for computable probability spaces ⋮ Martin-Löf random points satisfy Birkhoff’s ergodic theorem for effectively closed sets ⋮ Randomness for non-computable measures ⋮ Measures and their random reals ⋮ Effective symbolic dynamics, random points, statistical behavior, complexity and entropy ⋮ Schnorr randomness and the Lebesgue differentiation theorem ⋮ Probabilistic computability and choice ⋮ Unnamed Item ⋮ SOME QUESTIONS OF UNIFORMITY IN ALGORITHMIC RANDOMNESS ⋮ Computable Geometric Complex Analysis and Complex Dynamics ⋮ Computable Measure Theory and Algorithmic Randomness ⋮ Effective notions of weak convergence of measures on the real line ⋮ A Church-Turing thesis for randomness?

Cites Work