Computable randomness and diferentiability on the unit interval

Get Complete Project Material File(s) Now! »

What this thesis is about

The subject of this thesis lies at the interface of computable analysis and algorithmic randomness. Computable randomness is a randomness notion defined in terms of e↵ective betting strategies. One of the main results in the paper of Brattka, Miller and Nies [BMN16] shows that computably random points on the unit interval can be characterized as points where all computable monotone real-valued functions of one variable are di↵erentiable. An analogous result for computable Lipschitz functions has been proven in the paper of Freer, Kjos-Hanssen, Nies and Stephan [FKHNS14].
Those results suggest that there are close connections between computable randomness and di↵erentiability of certain classes of objects in Euclidean spaces. In order to advance our understanding of this particular phenomenon, we pursue two directions of research. Firstly, we seek to generalize, where possible, known results to higher dimensions (that is to Rn). Secondly, we study how computable randomness and di↵erentiability interact for other classes of objects that are closely related to monotone and Lipschitz functions.

Computable analysis and algorithmic randomness

The theory of algorithmic randomness (see Nies [Nie09], Downey and Hirschfeldt [DH10]) is the area of mathematics that formalizes and studies the intuitive notion of randomness. Intuitively, an element of some space is random if it does not exhibit any exceptional properties. This approach can be formalized, utilizing measure theory and computability, by identifying exceptional properties with e↵ective null sets.
Di↵erent types of e↵ective null sets correspond to di↵erent notions of algorithmic randomness. This use of computability theory to rigorously specify which properties are exceptional, explains the word “algorithmic” in “algorithmic randomness”. Below we provide some informal examples of known randomness notions.

Computable randomness

An infinite binary sequence is said to be computably random, if no e↵ective betting strategy can make unbounded profits while betting on this sequence. This notion of randomness can be generalized to Rn by identifying elements of Rn with their binary expansions.
Weak 2-randomness An element of a computable measure space (X, μ) is said to be weakly 2-random if it does not belong to any e↵ective G! null set V ✓ X.

READ  The role of language and language planning in social transformation

Martin-L¨of randomness

Let (X, μ) be a computable measure space. A V ✓ X is a Martin-L¨of test if there is a computable sequence (Gi)i2N of e↵ectively open subsets such that V = \Gi and μ(Gj)  2−j for all j. x 2 X is said to be Martin-L¨of random if it does not belong to any Martin- L¨of test.

1 Introduction 
1.1 What this thesis is about
1.2 Computable analysis and algorithmic randomness
1.3 Randomness and “a.e. theorems” .
1.4 Randomness and di↵erentiability of real-valued functions on Rn
1.5 Non-di↵erentiability sets
1.6 Computable randomness and di↵erentiability
1.7 Summary of contributions
1.8 Structure of the thesis
2 Preliminaries 
2.1 Computable analysis
2.2 Computable metric spaces
2.3 Computable measures
2.4 Dyadic rationals and dyadic cubes in Rn
2.5 Computable randomness
2.6 Di↵erentiability of real-valued functions on Rn
2.7 Lipschitz, convex and monotone function
3 Computable randomness and di↵erentiability on the unit interval
3.1 Porosity, di↵erentiability and betting
3.2 Zahorski’s construction on the real line .
3.3 Convex functions, their derivatives and probability measures
4 Computable randomness and di↵erentiability in Rn 
4.1 E↵ective Rademacher theorem
4.2 Computable monotone Lipschitz functions preserve non-randomness .
4.3 An e↵ective version of Sard’s theorem for monotone Lipschitz functions
4.4 Di↵erentiability of monotone functions on Rn
4.5 Convex functions on Rn
4.6 Almost everywhere computable monotone functions on Rn
5 E↵ective Brenier theorem 
6 Controlling non-di↵erentiability in Rn 
Bibliography

GET THE COMPLETE PROJECT
Computable Randomness and Di↵erentiability in Rn

Related Posts