Randomness and differentiability
From MaRDI portal
Algorithmic randomness and dimension (03D32) Constructive and recursive analysis (03F60) Nondifferentiability (nondifferentiable functions, points of nondifferentiability), discontinuous derivatives (26A27) Functions of bounded variation, generalizations (26A45) Monotonic functions, generalizations (26A48)
Abstract: We characterize some major algorithmic randomness notions via differentiability of effective functions. (1) As the main result we show that a real number z in [0,1] is computably random if and only if each nondecreasing computable function [0,1]->R is differentiable at z. (2) We prove that a real number z in [0,1] is weakly 2-random if and only if each almost everywhere differentiable computable function [0,1]->R is differentiable at z. (3) Recasting in classical language results dating from 1975 of the constructivist Demuth, we show that a real z is ML random if and only if every computable function of bounded variation is differentiable at z, and similarly for absolutely continuous functions. We also use our analytic methods to show that computable randomness of a real is base invariant, and to derive other preservation results for randomness notions.
Recommendations
Cites work
- A simple proof of Zahorski's description of non-differentiability sets of Lipschitz functions
- Algorithmic aspects of Lipschitz functions
- Algorithmic randomness and complexity.
- Computability and Randomness
- Computability in analysis and physics
- Demuth's path to randomness
- scientific article; zbMATH DE number 3508473 (Why is no real title available?)
- scientific article; zbMATH DE number 1022658 (Why is no real title available?)
- scientific article; zbMATH DE number 1404324 (Why is no real title available?)
- scientific article; zbMATH DE number 3099952 (Why is no real title available?)
- Measure theory. Vol. I and II
- RELATIVIZING CHAITIN'S HALTING PROBABILITY
- Schnorr randomness and the Lebesgue differentiation theorem
- Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)
Cited in
(43)- Online computability and differentiation in the Cantor space
- Schnorr randomness for noncomputable measures
- Characterization of Kurtz randomness by a differentiation theorem
- Algorithmic randomness and Fourier analysis
- Highness properties close to PA completeness
- A Church-Turing thesis for randomness?
- Pointwise complexity of the derivative of a computable function
- Martin-Löf randomness implies multiple recurrence in effectively closed sets
- Cone avoidance and randomness preservation
- Normality in non-integer bases and polynomial time randomness
- Feasible analysis, randomness, and base invariance
- Cryptography and algorithmic randomness
- Computable randomness and betting for computable probability spaces
- Schnorr randomness and the Lebesgue differentiation theorem
- Denjoy, Demuth and density
- Demuth's path to randomness
- Randomness, computation and mathematics
- The Denjoy alternative for computable functions
- Effective genericity and differentiability
- Lowness, Randomness, and Computable Analysis
- Difference randomness
- A computational approach to the Borwein-Ditor theorem
- Randomness and differentiability of convex functions
- Algorithmic information theory and its statistical mechanical interpretation
- Closure of resource-bounded randomness notions under polynomial-time permutations
- Randomness, arrays, differences and duality
- Algorithmic aspects of Lipschitz functions
- THE REVERSE MATHEMATICS OF THEOREMS OF JORDAN AND LEBESGUE
- Computable Measure Theory and Algorithmic Randomness
- LUZIN’S (N) AND RANDOMNESS REFLECTION
- Chaitin's as a continuous function
- scientific article; zbMATH DE number 7204482 (Why is no real title available?)
- Computing from projections of random points
- Continuous higher randomness
- Using almost-everywhere theorems from analysis to study randomness
- On the Weihrauch degree of the additive Ramsey theorem
- Hilbert's tenth problem for term algebras with a substitution operator
- Complemented subsets and Boolean-valued, partial functions
- Defining long words succinctly in FO and MSO
- On the first-order parts of problems in the Weihrauch degrees
- Algorithmically random series
- Computable classifications of continuous, transducer, and regular functions
- Algorithmic randomness, reverse mathematics, and the dominated convergence theorem
This page was built for publication: Randomness and differentiability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3448999)
