Randomness and Differentiability

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.

39 pages

References in corpus (2)

• Algorithmic aspects of Lipschitz functions
• Demuth's path to randomness

Cited by in corpus (9)

• Algorithmic randomness, reverse mathematics, and the dominated convergence theorem
• Bounded variation and the strength of Helly's selection theorem
• The descriptive theory of represented spaces
• Cryptography and Algorithmic Randomness
• Computing from projections of random points: a dense hierarchy of subideals of the $K$-trivial degrees
• On the close interaction between algorithmic randomness and constructive/computable measure theory
• The reverse mathematics of theorems of Jordan and Lebesgue
• Typical = random
• Effective Genericity and Differentiability