Randomness on Computable Probability Spaces—A Dynamical Point of View
Randomness on Computable Probability Spaces—A Dynamical Point of View
复制标题
可计算概率空间上的随机性——动态观点
DOI：
10.1007/s00224-010-9263-x
复制
发表时间：
2009
影响因子：
0.5
通讯作者：
Cristobal Rojas
中科院分区：
文献类型：
--
作者：
P. Gács;M. Hoyrup;Cristobal Rojas
我们将随机性的概念（在Schnorr介绍的版本中）扩展到可计算概率空间，并将其与随机性的adjacenticalnotion：typicality进行比较。粗略地说，一个点对于某些动态是典型的，如果它遵循系统的统计行为（Birkhoff点态遍历定理）。我们证明了一个点是Schnorr随机的当且仅当它是典型的每一个mixingcomputable动力学。为了证明这一结果，我们开发了一些工具，用于可计算概率空间的理论（例如，态射），这些工具预计会有其他应用。
We extend the notion of randomness (in the version introduced by Schnorr) to computable probability spaces and compare it to adynamicalnotion of randomness: typicality. Roughly, a point istypicalfor 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 everymixingcomputable 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.