Randomness on computable probability spaces - A dynamical point of view

Peter Gacs, Mathieu Hoyrup, Cristobal Rojas

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Citations (Scopus)

Abstract

We extend the notion of randomness (in the version introduced by Schnorr) to computable Probability Spaces and compare it to a dynamical notion of randomness: typicality. Roughly, a point is typical for some dynamic, if it follows the statistical behavior of the system (Birkhoff's pointwise ergodic theorem). We prove that a point is Schnorr random if and only if it is typical for every mixing computable dynamics. To prove the result we develop some tools for the theory of computable probability spaces (for example, morphisms) that are expected to have other applications.

Original languageEnglish
Title of host publicationSTACS 2009 - 26th International Symposium on Theoretical Aspects of Computer Science
Pages469-480
Number of pages12
Volume3
Publication statusPublished - 2009
Event26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009 - Freiburg, Germany
Duration: 26 Feb 200928 Feb 2009

Other

Other26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009
CountryGermany
CityFreiburg
Period26/02/0928/02/09

Keywords

  • Birkhoff's ergodic theorem
  • Computable measures
  • Schnorr randomness

ASJC Scopus subject areas

  • Software

Cite this

Gacs, P., Hoyrup, M., & Rojas, C. (2009). Randomness on computable probability spaces - A dynamical point of view. In STACS 2009 - 26th International Symposium on Theoretical Aspects of Computer Science (Vol. 3, pp. 469-480)