Using almost-everywhere theorems from analysis to study randomness

DOI10.1017/BSL.2016.10MaRDI QIDQ5346702zbMATH OpenOpenAlexFDO

Authors Kenshi Miyabe, André Nies, Jing Zhang

Publication date 26 May 2017

Published in The Bulletin of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.0732

zbMATH Keywords

almost-everywhere theoremergodic theoryLebesgue densityrandomness

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Applications of computability and recursion theory (03D80) Ergodicity, mixing, rates of mixing (37A25) Ergodic theorems, spectral theory, Markov operators (37A30) Martingales with continuous parameter (60G44)

Abstract: We study algorithmic randomness notions via effective versions of almost-everywhere theorems from analysis and ergodic theory. The effectivization is in terms of objects described by a computably enumerable set, such as lower semicomputable functions. The corresponding randomness notions are slightly stronger than ML (ML) randomness. We establish several equivalences. Given a ML-random real $z$, the additional randomness strengths needed for the following are equivalent.

(1) all effectively closed classes containing $z$ have density $1$ at $z$. 
(2) all nondecreasing functions with uniformly left-c.e. increments are differentiable at $z$. 

(3) $z$ is a Lebesgue point of each lower semicomputable integrable function. We also consider convergence of left-c.e. martingales, and convergence in the sense of Birkhoff's pointwise ergodic theorem. Lastly we study randomness notions for density of $P{i}_n^0$ and $Sigm{a}_1^1$ classes.

Recommendations

• Randomness and differentiability
• Lebesgue density and \(\Pi _1^0\) classes
• Denjoy, Demuth and density
• The Denjoy alternative for computable functions
• Schnorr randomness and the Lebesgue differentiation theorem

Cites work

• A constructive version of Birkhoff's ergodic theorem for Martin-Löf random points
• Algorithmic aspects of Lipschitz functions
• Algorithmic randomness and complexity.
• Characterization of Kurtz randomness by a differentiation theorem
• Computability and randomness
• Computability of probability measures and Martin-Löf randomness over metric spaces
• Computuing K-trivial sets by incomplete random sets
• Counting the changes of random _2⁰ sets
• Cupping with random sets
• Denjoy, Demuth and density
• Density, forcing, and the covering problem
• Differentiability of polynomial time computable functions
• Ergodic theorems for individual random sequences
• scientific article; zbMATH DE number 42077 (Why is no real title available?)
• scientific article; zbMATH DE number 3508473 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 1022658 (Why is no real title available?)
• scientific article; zbMATH DE number 1460545 (Why is no real title available?)
• scientific article; zbMATH DE number 1404324 (Why is no real title available?)
• Lowness and nullsets
• Martin-Löf random points satisfy Birkhoff's ergodic theorem for effectively closed sets
• Martingale proof of the existence of Lebesgue points
• Measure theory. Vol. I and II
• Probability. Theory and examples.
• Randomness and Computability: Open Questions
• Randomness and differentiability
• Randomness and non-ergodic systems
• Randomness on computable probability spaces -- a dynamical point of view
• Schnorr randomness and the Lebesgue differentiation theorem
• Subadditive mean ergodic theorems
• The mean ergodic theorem
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)

Cited in

(15)

• Randomness and initial segment complexity for measures
• Martin-Löf randomness implies multiple recurrence in effectively closed sets
• Lebesgue density and \(\Pi _1^0\) classes
• Denjoy, Demuth and density
• The Denjoy alternative for computable functions
• Algorithmic randomness for Doob's martingale convergence theorem in continuous time
• Lowness, Randomness, and Computable Analysis
• A computational approach to the Borwein-Ditor theorem
• Lightface ^0_3-completeness of density sets under effective Wadge reducibility
• Randomness and differentiability
• Computable Measure Theory and Algorithmic Randomness
• A NOTE ON THE LEARNING-THEORETIC CHARACTERIZATIONS OF RANDOMNESS AND CONVERGENCE
• Randomness notions and reverse mathematics
• Chaitin's as a continuous function
• A variant of Chaitin's Omega function

This page was built for publication: Using almost-everywhere theorems from analysis to study randomness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5346702)