Abstract
A theorem of Ku\(\mathrm{\check{c}}\)era states that given a Martin-Löf random infinite binary sequence ω and an effectively open set A of measure less than 1, some tail of ω is not in A. We show that this result can be seen as an effective version of Birkhoff’s ergodic theorem (in a special case). We prove several results in the same spirit and generalize them via an effective ergodic theorem for bijective ergodic maps.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Gács, P.: Lecture notes on descriptional complexity and randomness (manuscript), http://www.cs.bu.edu/fac/gacs/recent-publ.html
Gács, P., Hoyrup, M., Rojas, C.: Randomness on computable probability spaces - a dynamical point of view. In: Symposium on Theoretical Aspects of Computer Science (STACS 2009). Dagstuhl Seminar Proceedings. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, vol. 9001, pp. 469–480 (2009)
Hoyrup, M., Rojas, C.: Applications of effective probability theory to Martin-löf randomness. In: Albers, S., et al. (eds.) ICALP 2009. LNCS, vol. 5555, pp. 549–561. Springer, Heidelberg (2009)
Hoyrup, M., Rojas, C.: Computability of probability measures and Martin-Löf randomness over metric spaces. Information and Computation 207(7), 2207–2222 (2009)
Kučera, A.: Measure, \(\Pi^0_1\) classes, and complete extensions of PA. In: Ebbinghaus, H.-D., Müller, G.H., Sacks, G.E. (eds.) Recursion Theory Week. Proceedings of a Conference held in Oberwolfach, West Germany, April 15-21. LNM, vol. 1141, pp. 245–259 (1985)
Miyabe, K.: An extension of van Lambalgen’s theorem to infinitely many relative 1-random reals. The Notre Dame Journal of Formal Logic (to appear)
Shiryaev, A.: Probability, 2nd edn. Springer, Heidelberg (1996)
van Lambalgen, M.: Random sequences. PhD dissertation, University of Amsterdam, Amsterdam (1987)
V’yugin, V.: Effective convergence in probability and an ergodic theorem for individual random sequences. SIAM Theory of Probability and Its Applications 42(1), 39–50 (1997)
V’yugin, V.: Ergodic theorems for individual random sequences. Theoretical Computer Science 207(2), 343–361 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bienvenu, L., Day, A., Mezhirov, I., Shen, A. (2010). Ergodic-Type Characterizations of Algorithmic Randomness. In: Ferreira, F., Löwe, B., Mayordomo, E., Mendes Gomes, L. (eds) Programs, Proofs, Processes. CiE 2010. Lecture Notes in Computer Science, vol 6158. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13962-8_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-13962-8_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-13961-1
Online ISBN: 978-3-642-13962-8
eBook Packages: Computer ScienceComputer Science (R0)