Computable Measure Theory and Algorithmic Randomness

DOI10.1007/978-3-030-59234-9_7OpenAlexW3085512952MaRDI QIDQ5024573

Jason Rute, Mathieu Hoyrup

Publication date: 26 January 2022

Published in: Theory and Applications of Computability (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/hal-02938919/file/Chapter_HR.pdf

Mathematics Subject Classification ID

Computation over the reals, computable analysis (03D78)

Cites Work

• Randomness on computable probability spaces - A dynamical point of view
• On the computability of a construction of Brownian motion
• Algorithmic randomness over general spaces
• The Law of the Iterated Logarithm for Algorithmically Random Brownian Motion
• Algorithmic Randomness of Closed Sets
• A constructive view on ergodic theorems
• MARTIN-LÖF RANDOMNESS IN SPACES OF CLOSED SETS
• The definition of random sequences
• Van Lambalgen's theorem for uniformly relative Schnorr and computable randomness
• Kolmogorov complexity and the geometry of Brownian motion
• An introduction to Kolmogorov complexity and its applications
• An example of a computable absolutely normal number
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• When does randomness come from randomness?
• A constructive version of Birkhoff's ergodic theorem for Martin-Löf random points
• Conditional measure and the violation of van Lambalgen's theorem for Martin-Löf randomness
• Randomness on computable probability spaces -- a dynamical point of view
• Algorithmic randomness and monotone complexity on product space
• Dynamics and abstract computability: computing invariant measures
• Algorithmic randomness, reverse mathematics, and the dominated convergence theorem
• Computable de Finetti measures
• Computability of measurable sets via effective topologies
• Are unbounded linear operators computable on the average for Gaussian measures?
• Upcrossing inequalities for stationary sequences and applications
• On a definition of random sequences with respect to conditional probability
• Infinite subsets of random sets of integers
• A constructive Borel-Cantelli lemma. Constructing orbits with required statistical properties
• A computable approach to measure and integration theory
• Effective symbolic dynamics, random points, statistical behavior, complexity and entropy
• The computational complexity of maximization and integration
• Use of the Kolmogorov complexity in analyzing control system dynamics
• The speed of convergence in the ergodic theorem
• Ergodic theorems for individual random sequences
• Computability on random variables
• Computability on the probability measures on the Borel sets of the unit interval
• Nonrobustness property of the individual ergodic theorem
• Random elements in effective topological spaces with measure.
• The descriptive complexity of Brownian motion
• Schnorr randomness for noncomputable measures
• Uncomputably noisy ergodic limits
• The Borel-Cantelli lemmas, probability laws and Kolmogorov complexity
• Computability of the ergodic decomposition
• Probabilistic computability and choice
• Universality, optimality, and randomness deficiency
• Computability of probability measures and Martin-Löf randomness over metric spaces
• Statistical properties of dynamical systems -- Simulation and abstract computation
• Dynamics of a generic Brownian motion: Recursive aspects
• A computable version of the Daniell-Stone theorem on integration and linear functionals
• Algorithmic tests and randomness with respect to a class of measures
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)
• Uniform test of algorithmic randomness over a general space
• Randomness and Non-ergodic Systems
• Computable randomness and betting for computable probability spaces
• Martin-Löf random points satisfy Birkhoff’s ergodic theorem for effectively closed sets
• L1-Computability, Layerwise Computability and Solovay Reducibility
• Schnorr randomness and the Lebesgue differentiation theorem
• Representations of measurable sets in computable measure theory
• The difference between optimality and universality
• The dimension of ergodic random sequences
• Fourier spectra of measures associated with algorithmically random Brownian motion
• Probabilistic Constructions of Computable Objects and a Computable Version of Lovász Local Lemma
• Algorithmic randomness for Doob's martingale convergence theorem in continuous time
• On zeros of Martin-Löf random Brownian motion
• Complexity Theory for Operators in Analysis
• Las Vegas Computability and Algorithmic Randomness
• Computability on measurable functions
• Differentiability of polynomial time computable functions
• Von Neumann's Biased Coin Revisited
• Randomness and the Ergodic Decomposition
• Computability of the Radon-Nikodym Derivative
• The probability distribution as a computational resource for randomness testing
• Algorithmic Randomness and Complexity
• L p -Computability in Recursive Analysis
• Local stability of ergodic averages
• Randomness and differentiability
• Members of Random Closed Sets
• Fractals Generated by Algorithmically Random Brownian Motion
• Computable Exchangeable Sequences Have Computable de Finetti Measures
• An Application of Martin-Löf Randomness to Effective Probability Theory
• Ergodic-Type Characterizations of Algorithmic Randomness
• Applications of Effective Probability Theory to Martin-Löf Randomness
• Von Mises' definition of random sequences reconsidered
• The Law of the Iterated Logarithm for Random Kolmogorov, or Chaotic, Sequences
• Эффективная сходимость по вероятности и эргодическая теорема для индивидуальных случайных последовательностей
• On computability and disintegration
• L^p‐Computability
• Introduction to Dynamical Systems
• On the Convergence of Fourier Series of Computable Lebesgue Integrable Functions
• Effective Randomness for Computable Probability Measures
• Random Continuous Functions
• Arithmetical representations of Brownian motion I
• Algorithmic Aspects of Lipschitz Functions
• Computable Riesz representation for the dual of C [0; 1]
• Admissible representations for probability measures
• USING ALMOST-EVERYWHERE THEOREMS FROM ANALYSIS TO STUDY RANDOMNESS

This page was built for publication: Computable Measure Theory and Algorithmic Randomness