Randomness on Computable Probability Spaces-A Dynamical Point of View

Peter Gács, Mathieu Hoyrup, Cristóbal Rojas

Resultado de la investigación: Article

22 Citas (Scopus)

Resumen

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.

Idioma originalEnglish
Páginas (desde-hasta)465-485
Número de páginas21
PublicaciónTheory of Computing Systems
Volumen48
N.º3
DOI
EstadoPublished - 1 abr 2011

Huella dactilar

Probability Space
Randomness
Ergodic Theorem
Morphisms
If and only if

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics

Citar esto

Gács, Peter ; Hoyrup, Mathieu ; Rojas, Cristóbal. / Randomness on Computable Probability Spaces-A Dynamical Point of View. En: Theory of Computing Systems. 2011 ; Vol. 48, N.º 3. pp. 465-485.
@article{f95a0766f2814d38a6f6582bc0ba37ed,
title = "Randomness on Computable Probability Spaces-A Dynamical Point of View",
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.",
keywords = "Birkhoff's ergodic theorem, Computable measures, Schnorr randomness",
author = "Peter G{\'a}cs and Mathieu Hoyrup and Crist{\'o}bal Rojas",
year = "2011",
month = "4",
day = "1",
doi = "10.1007/s00224-010-9263-x",
language = "English",
volume = "48",
pages = "465--485",
journal = "Theory of Computing Systems",
issn = "1432-4350",
publisher = "Springer New York",
number = "3",

}

Randomness on Computable Probability Spaces-A Dynamical Point of View. / Gács, Peter; Hoyrup, Mathieu; Rojas, Cristóbal.

En: Theory of Computing Systems, Vol. 48, N.º 3, 01.04.2011, p. 465-485.

Resultado de la investigación: Article

TY - JOUR

T1 - Randomness on Computable Probability Spaces-A Dynamical Point of View

AU - Gács, Peter

AU - Hoyrup, Mathieu

AU - Rojas, Cristóbal

PY - 2011/4/1

Y1 - 2011/4/1

N2 - 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.

AB - 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.

KW - Birkhoff's ergodic theorem

KW - Computable measures

KW - Schnorr randomness

UR - http://www.scopus.com/inward/record.url?scp=79751535074&partnerID=8YFLogxK

U2 - 10.1007/s00224-010-9263-x

DO - 10.1007/s00224-010-9263-x

M3 - Article

AN - SCOPUS:79751535074

VL - 48

SP - 465

EP - 485

JO - Theory of Computing Systems

JF - Theory of Computing Systems

SN - 1432-4350

IS - 3

ER -