Schnorr randomness and the Lebesgue differentiation theorem

Pathak, Noopur; Rojas, Cristóbal; Simpson, Stephen

doi:10.1090/S0002-9939-2013-11710-7

Schnorr randomness and the Lebesgue differentiation theorem
HTML articles powered by AMS MathViewer

by Noopur Pathak, Cristóbal Rojas and Stephen G. Simpson

Proc. Amer. Math. Soc. 142 (2014), 335-349

DOI: https://doi.org/10.1090/S0002-9939-2013-11710-7

Published electronically: August 27, 2013

PDF | Request permission

Abstract:

We exhibit a close correspondence between $L_1$-computable functions and Schnorr tests. Using this correspondence, we prove that a point $x\in [0,1]^d$ is Schnorr random if and only if the Lebesgue Differentiation Theorem holds at $x$ for all $L_1$-computable functions $f\in L_1([0,1]^d)$.

References

Jeremy Avigad, Philipp Gerhardy, and Henry Towsner, Local stability of ergodic averages, Trans. Amer. Math. Soc. 362 (2010), no. 1, 261–288. MR 2550151, DOI 10.1090/S0002-9947-09-04814-4
Laurent Bienvenu, Adam R. Day, Mathieu Hoyrup, Ilya Mezhirov, and Alexander Shen, A constructive version of Birkhoff’s ergodic theorem for Martin-Löf random points, Inform. and Comput. 210 (2012), 21–30. MR 2878799, DOI 10.1016/j.ic.2011.10.006
Vasco Brattka, Joseph S. Miller, and André Nies, Randomness and differentiability, (2011), Preprint, 36 pages, submitted for publication.
Douglas K. Brown, Mariagnese Giusto, and Stephen G. Simpson, Vitali’s theorem and WWKL, Arch. Math. Logic 41 (2002), no. 2, 191–206. MR 1890192, DOI 10.1007/s001530100100
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
Johanna N. Y. Franklin, Noam Greenberg, Joseph S. Miller, and Keng Meng Ng, Martin-Löf random points satisfy Birkhoff’s ergodic theorem for effectively closed sets, Proc. Amer. Math. Soc. 140 (2012), no. 10, 3623–3628. MR 2929030, DOI 10.1090/S0002-9939-2012-11179-7
Peter Gács, Mathieu Hoyrup, and Cristóbal Rojas, Randomness on computable probability spaces—a dynamical point of view, Theory Comput. Syst. 48 (2011), no. 3, 465–485. MR 2770804, DOI 10.1007/s00224-010-9263-x
Stefano Galatolo, Mathieu Hoyrup, and Cristóbal Rojas, Computing the speed of convergence of ergodic averages and pseudorandom points in computable dynamical systems, Electronic Proceedings in Theoretical Computer Science 24 (2010), 7–18, http://arxiv.org/abs/1006.0392v1.
Stefano Galatolo, Mathieu Hoyrup, and Cristóbal Rojas, Effective symbolic dynamics, random points, statistical behavior, complexity and entropy, Inform. and Comput. 208 (2010), no. 1, 23–41. MR 2558734, DOI 10.1016/j.ic.2009.05.001
Wilfrid Hodges, Model theory, Encyclopedia of Mathematics and its Applications, vol. 42, Cambridge University Press, Cambridge, 1993. MR 1221741, DOI 10.1017/CBO9780511551574
Mathieu Hoyrup and Cristóbal Rojas, An application of Martin-Löf randomness to effective probability theory, Mathematical theory and computational practice, Lecture Notes in Comput. Sci., vol. 5635, Springer, Berlin, 2009, pp. 260–269. MR 2545900, DOI 10.1007/978-3-642-03073-4_{2}7
Mathieu Hoyrup and Cristóbal Rojas, Computability of probability measures and Martin-Löf randomness over metric spaces, Inform. and Comput. 207 (2009), no. 7, 830–847. MR 2519075, DOI 10.1016/j.ic.2008.12.009
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
Noopur Pathak, A computational aspect of the Lebesgue differentiation theorem, J. Log. Anal. 1 (2009), Paper 9, 15. MR 2534198, DOI 10.4115/jla.2009.1.9
Cristóbal Rojas, Randomness and ergodic theory: an algorithmic point of view, Ph.D. thesis, École Polytechnique, 2008.
V. V. V′yugin, Effective convergence in probability, and an ergodic theorem for individual random sequences, Teor. Veroyatnost. i Primenen. 42 (1997), no. 1, 35–50 (Russian, with Russian summary); English transl., Theory Probab. Appl. 42 (1997), no. 1, 39–50 (1998). MR 1453328, DOI 10.1137/S0040585X97975915
Richard L. Wheeden and Antoni Zygmund, Measure and integral, Pure and Applied Mathematics, Vol. 43, Marcel Dekker, Inc., New York-Basel, 1977. An introduction to real analysis. MR 0492146