Randomness on computable probability spaces - A dynamical point of view

Peter Gacs, Mathieu Hoyrup, Cristobal Rojas

Resultado de la investigación: Conference contribution

9 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
Título de la publicación alojadaSTACS 2009 - 26th International Symposium on Theoretical Aspects of Computer Science
Páginas469-480
Número de páginas12
Volumen3
EstadoPublished - 2009
Evento26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009 - Freiburg, Germany
Duración: 26 feb 200928 feb 2009

Other

Other26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009
PaísGermany
CiudadFreiburg
Período26/02/0928/02/09

ASJC Scopus subject areas

  • Software

Citar esto

Gacs, P., Hoyrup, M., & Rojas, C. (2009). Randomness on computable probability spaces - A dynamical point of view. En STACS 2009 - 26th International Symposium on Theoretical Aspects of Computer Science (Vol. 3, pp. 469-480)
Gacs, Peter ; Hoyrup, Mathieu ; Rojas, Cristobal. / Randomness on computable probability spaces - A dynamical point of view. STACS 2009 - 26th International Symposium on Theoretical Aspects of Computer Science. Vol. 3 2009. pp. 469-480
@inproceedings{b96aecd5a94847b0aa8812b76322193c,
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 Gacs and Mathieu Hoyrup and Cristobal Rojas",
year = "2009",
language = "English",
isbn = "9783939897095",
volume = "3",
pages = "469--480",
booktitle = "STACS 2009 - 26th International Symposium on Theoretical Aspects of Computer Science",

}

Gacs, P, Hoyrup, M & Rojas, C 2009, Randomness on computable probability spaces - A dynamical point of view. En STACS 2009 - 26th International Symposium on Theoretical Aspects of Computer Science. vol. 3, pp. 469-480, 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, Freiburg, Germany, 26/02/09.

Randomness on computable probability spaces - A dynamical point of view. / Gacs, Peter; Hoyrup, Mathieu; Rojas, Cristobal.

STACS 2009 - 26th International Symposium on Theoretical Aspects of Computer Science. Vol. 3 2009. p. 469-480.

Resultado de la investigación: Conference contribution

TY - GEN

T1 - Randomness on computable probability spaces - A dynamical point of view

AU - Gacs, Peter

AU - Hoyrup, Mathieu

AU - Rojas, Cristobal

PY - 2009

Y1 - 2009

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=84880198126&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84880198126

SN - 9783939897095

VL - 3

SP - 469

EP - 480

BT - STACS 2009 - 26th International Symposium on Theoretical Aspects of Computer Science

ER -

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