Randomness on Computable Probability Spaces - A Dynamical Point of View

Authors Peter Gacs, Mathieu Hoyrup, Cristobal Rojas



PDF
Thumbnail PDF

File

LIPIcs.STACS.2009.1828.pdf
  • Filesize: 215 kB
  • 12 pages

Document Identifiers

Author Details

Peter Gacs
Mathieu Hoyrup
Cristobal Rojas

Cite AsGet BibTex

Peter Gacs, Mathieu Hoyrup, and Cristobal Rojas. Randomness on Computable Probability Spaces - A Dynamical Point of View. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 469-480, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
https://doi.org/10.4230/LIPIcs.STACS.2009.1828

Abstract

We extend the notion of randomness (in the version introduced by Schnorr) to computable Probability Spaces and compare it to a \emph{dynamical} notion of randomness: typicality. Roughly, a point is \emph{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 \emph{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.
Keywords
  • Schnorr randomness
  • Birkhoff's ergodic theorem
  • Computable measures

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail