Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-27T17:50:36.381Z Has data issue: false hasContentIssue false
  • English
  • Français

Probabilistic Algorithmic Randomness

Published online by Cambridge University Press:  12 March 2014

Sam Buss  and
Mia Minnes
Sam Buss
Affiliation:
Department of Mathematics, University of California, San Diego, La Jolla, CA 92093-0112, USA, E-mail:[email protected], E-mail:[email protected]
Mia Minnes
Affiliation:
Department of Mathematics, University of California, San Diego, La Jolla, CA 92093-0112, USA, E-mail:[email protected], E-mail:[email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We introduce martingales defined by probabilistic strategies, in which randomness is used to decide whether to bet. We show that different criteria for the success of computable probabilistic strategies can be used to characterize ML-randomness, computable randomness, and partial computable randomness. Our characterization of ML-randomness partially addresses a critique of Schnorr by formulating ML randomness in terms of a computable process rather than a computably enumerable function.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 78 , Issue 2 , June 2013 , pp. 579 - 601
Copyright
Copyright © Association for Symbolic Logic 2013

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Ambos-Spies, Klaus, Algorithmic randomness revisited, Language, logic, and formalization of knowledge (McGuinness, B., editor), Bibliotheca, 1998, pp. 33–52.Google Scholar
[2] Ambos-Spies, Klaus and Kučera, Antonín, Randomness in computability theory, Computability theory and its applications (Cholak, Peter A., Lempp, Steffen, Lerman, Manuel, and Shore, Richard A., editors), American Mathematics Society, 2000, pp. 1–14.Google Scholar
[3] Arora, Sanjeev and Barak, Boaz, Computational complexity: A modern approach, Cambridge University Press, 2009.CrossRefGoogle Scholar
[4] Downey, Rodney G. and Hirschfeldt, Denis, Algorithmic randomness and complexity. Springer, 2010.CrossRefGoogle Scholar
[5] Goldreich, Oded, Computational complexity: A conceptual perspective, Cambridge University Press, 2008.CrossRefGoogle Scholar
[6] Hitchcock, John M. and Lutz, Jack H., Why computable complexity requires stricter martingales. Theory of Computing Systems, vol. 39 (2006), pp. 277–296.CrossRefGoogle Scholar
[7] Kastermans, Bart and Lempp, Steffen, Comparing notions of randomness. Theoretical Computer Science, vol. 411 (2010), no. 3, pp. 602–616.CrossRefGoogle Scholar
[8] Levin, Leonid, On the notion of a random sequence, Soviet Mathematics Doklady, vol. 14 (1973), pp. 1413–1416.Google Scholar
[9] Li, Ming and Vitányi, Paul, An introduction to Kolmogorov complexity and its applications, third ed., Springer, 2008.CrossRefGoogle Scholar
[10] Martin-Löf, Per, The definition of random sequences, Information and Control, vol. 9 (1966), no. 6, pp. 602–619.CrossRefGoogle Scholar
[11] Merkle, Wolfgang, Mihailović, Nenad, and Slaman, Theodore A., Some results on effective randomness. Theory of Computing Systems, vol. 39 (2006), pp. 707–721.CrossRefGoogle Scholar
[12] Merkle, Wolfgang, Miller, Joseph S., Nies, André, Reimann, Jan, and Stephan, Frank, Kolmogorov–Loveland randomness and stochasticity, Annals of Pure and Applied Logic, vol. 103 (2006), pp. 183–210.CrossRefGoogle Scholar
[13] Muchnik, Andrei A., Semenov, Alexei L., and Uspensky, Vladimir, Mathematical metaphysics of randomness, Theoretical Computer Science, vol. 207 (1998), pp. 263–317.CrossRefGoogle Scholar
[14] Nies, Andre, Computability and randomness, Oxford University Press, 2009.CrossRefGoogle Scholar
[15] Schnorr, Claus P., A unified approach to the definition of random sequences, Mathematical Systems Theory, vol. 5 (1971), pp. 246–258.CrossRefGoogle Scholar
[16] Schnorr, Claus P., Zufälligkeit und Wahrscheinlichkeit: Eine algorithmische Begründung der Wahrschein-lichkeitstheorie, Lecture Notes in Computer Science, vol. 218, Springer Verlag, 1971.CrossRefGoogle Scholar
[17] Schnorr, Claus P., Process complexity and effective random tests, Journal of Computer and System Sciences, vol. 5 (1973), no. 3, pp. 378–388.Google Scholar