Randomness on Computable Probability Spaces - A Dynamical Point of View
Lists
Only you see this
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.
BibTeX
@inproceedings{gacs2011randomness,
author = {Péter Gács and Mathieu Hoyrup and Cristobal Rojas},
title = {{Randomness on Computable Probability Spaces - A Dynamical Point of View}},
booktitle = {Theory Comput. Syst},
year = {2011},
url = {https://openreview.net/forum?id=8PLVaScaDY},
}Loading related content...