Abstract
Classical probability theory considers probability distributions that assign probabilities to all events (at least in the finite case). However, there are natural situations where only part of the process is controlled by some probability distribution while for the other part we know only the set of possibilities without any probabilities assigned.
We adapt the notions of algorithmic information theory (complexity, algorithmic randomness, martingales, a priori probability) to this framework and show that many classical results are still valid.
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, http://www.cs.bu.edu/faculty/gacs/papers/ait-notes.pdf
Levin, L.A.: Uniform tests of randomness. Soviet Math. Dokl. 17(2), 337–340 (1976)
Li, M., Vitányi, P.: An Introduction to Kolmogorov Complexity and Its Applications, 2nd edn. Springer, New York (1997)
Muchnik An, A., Chernov, A., Shen, A.: Algorithmic randomness and splitting of supermartingales, arxiv.org:0807.3156
Shen, A.: Algorithmic information theory and Kolmogorov complexity, Technical Report 2000-034. Uppsala Universitet publication, http://www.it.uu.se/research/publications/reports/2000-034
Uspensky, V.A., Semenov, A.L., Shen, A.: Can an individual sequence of zeros and ones be random? Russian Mathematics Surveys 45, 121–189 (1990)
Shafer, G., Vovk, V.: Probability and Finance: It’s Only a Game. Wiley, New York (2001)
Vovk, V., Shen, A.: Prequential randomness. In: Freund, Y., Györfi, L., Turán, G., Zeugmann, T. (eds.) ALT 2008. LNCS(LNAI), vol. 5254, pp. 154–168. Springer, Heidelberg (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chernov, A., Shen, A., Vereshchagin, N., Vovk, V. (2008). On-Line Probability, Complexity and Randomness. In: Freund, Y., Györfi, L., Turán, G., Zeugmann, T. (eds) Algorithmic Learning Theory. ALT 2008. Lecture Notes in Computer Science(), vol 5254. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-87987-9_15
Download citation
DOI: https://doi.org/10.1007/978-3-540-87987-9_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-87986-2
Online ISBN: 978-3-540-87987-9
eBook Packages: Computer ScienceComputer Science (R0)