Randomness and differentiability
HTML articles powered by AMS MathViewer
- by Vasco Brattka, Joseph S. Miller and André Nies PDF
- Trans. Amer. Math. Soc. 368 (2016), 581-605 Request permission
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]\rightarrow \mathbb {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]\rightarrow \mathbb {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 Martin-Löf 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.
References
- V. I. Bogachev, Measure theory. Vol. I, II, Springer-Verlag, Berlin, 2007. MR 2267655, DOI 10.1007/978-3-540-34514-5
- V. Brattka, J. Miller, and A. Nies, Randomness and differentiability (long version on arxiv). http://arxiv.org/abs/1104.4465.
- N. L. Carothers, Real analysis, Cambridge University Press, Cambridge, 2000. MR 1772332, DOI 10.1017/CBO9780511814228
- O. Demut, The differentiability of constructive functions of weakly bounded variation on pseudo numbers, Comment. Math. Univ. Carolinae 16 (1975), no. 3, 583–599 (Russian). MR 476442
- Rodney G. Downey and Denis R. Hirschfeldt, Algorithmic randomness and complexity, Theory and Applications of Computability, Springer, New York, 2010. MR 2732288, DOI 10.1007/978-0-387-68441-3
- Rod Downey, Denis R. Hirschfeldt, Joseph S. Miller, and André Nies, Relativizing Chaitin’s halting probability, J. Math. Log. 5 (2005), no. 2, 167–192. MR 2188515, DOI 10.1142/S0219061305000468
- Thomas Fowler and David Preiss, A simple proof of Zahorski’s description of non-differentiability sets of Lipschitz functions, Real Anal. Exchange 34 (2009), no. 1, 127–138. MR 2527127, DOI 10.14321/realanalexch.34.1.0127
- C. Freer, B. Kjos-Hanssen, A. Nies, and F. Stephan, Effective aspects of Lipschitz functions, Computability 3 (2014), 45–61, DOI 10.3233/COM-14025.
- A. Kučera, A. Nies, and C. Porter, Demuth’s path to randomness. To appear in Bull. Symb. Logic, 2014.
- Antonín Kučera and André Nies, Demuth’s path to randomness, Computation, physics and beyond, Lecture Notes in Comput. Sci., vol. 7160, Springer, Heidelberg, 2012, pp. 159–173. MR 2965521, DOI 10.1007/978-3-642-27654-5_{1}2
- Henri Lebesgue, Sur les intégrales singulières, Ann. Fac. Sci. Toulouse Sci. Math. Sci. Phys. (3) 1 (1909), 25–117 (French). MR 1508308, DOI 10.5802/afst.257
- André Nies, Computability and randomness, Oxford Logic Guides, vol. 51, Oxford University Press, Oxford, 2009. MR 2548883, DOI 10.1093/acprof:oso/9780199230761.001.0001
- A. Nies (editor), Logic Blog 2013. Available at http://arxiv.org/abs/1403.5719, 2013.
- Noopur Pathak, Cristóbal Rojas, and Stephen G. Simpson, Schnorr randomness and the Lebesgue differentiation theorem, Proc. Amer. Math. Soc. 142 (2014), no. 1, 335–349. MR 3119207, DOI 10.1090/S0002-9939-2013-11710-7
- Marian B. Pour-El and J. Ian Richards, Computability in analysis and physics, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1989. MR 1005942, DOI 10.1007/978-3-662-21717-7
- Walter Rudin, Real and complex analysis, 3rd ed., McGraw-Hill Book Co., New York, 1987. MR 924157
- J. Rute, Algorithmic randomness, martingales, and differentiability I. In preparation, 2012.
- Claus-Peter Schnorr, Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie, Lecture Notes in Mathematics, Vol. 218, Springer-Verlag, Berlin-New York, 1971. MR 0414225, DOI 10.1007/BFb0112458
- Zygmunt Zahorski, Sur l’ensemble des points de non-dérivabilité d’une fonction continue, Bull. Soc. Math. France 74 (1946), 147–178 (French). MR 22592, DOI 10.24033/bsmf.1381
Additional Information
- Vasco Brattka
- Affiliation: Faculty of Computer Science, Universität der Bundeswehr München, 85577 Neubiberg, Germany – and – Department of Mathematics and Applied Mathematics, University of Cape Town, Rondebosch 7701, South Africa
- Email: Vasco.Brattka@cca-net.de
- Joseph S. Miller
- Affiliation: Department of Mathematics, University of Wisconsin, Madison, Wisconsin 53706-1388
- MR Author ID: 735102
- Email: jmiller@math.wisc.edu
- André Nies
- Affiliation: Department of Computer Science, University of Auckland, Private bag 92019, Auckland, New Zealand
- MR Author ID: 328692
- Email: andre@cs.auckland.ac.nz
- Received by editor(s): November 21, 2012
- Received by editor(s) in revised form: November 22, 2013
- Published electronically: May 27, 2015
- Additional Notes: The first author was supported by the National Research Foundation of South Africa
The second author was supported by the National Science Foundation under grants DMS-0945187 and DMS-0946325, the latter being part of a Focused Research Group in Algorithmic Randomness
The third author was partially supported by the Marsden Fund of New Zealand, grant no. 08-UOA-187 - © Copyright 2015 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 368 (2016), 581-605
- MSC (2010): Primary 03D32, 03F60; Secondary 26A27, 26A48, 26A45
- DOI: https://doi.org/10.1090/tran/6484
- MathSciNet review: 3413875