Layerwise Computability and Image Randomness
Layerwise Computability and Image Randomness
复制标题
分层可计算性和图像随机性
DOI：
--
复制
发表时间：
2016
影响因子：
0.5
通讯作者：
A. Shen
中科院分区：
文献类型：
--
作者：
L. Bienvenu;M. Hoyrup;A. Shen
数学随机性理论始于一个单独的随机对象的概念。为了合理，这个概念应该有一些自然的性质;特别是，一个对象应该是随机的关于图像分布F（P）（对于某个分布P和某个映射F），当且仅当它有一个P-随机F-原像。这个结果（对于可计算分布和映射，以及Martin-Löf随机性）在很长一段时间内都是已知的（民间传说）;对于分层可计算映射，它在Hoyrup和Rojas（2009，命题5）中被提到（甚至对于更一般的可计算度量空间）。本文给出了一个证明，并讨论了有关的定量结果和应用。
Algorithmic randomness theory starts with a notion of an individual random object. To be reasonable, this notion should have some natural properties; in particular, an object should be random with respect to the image distribution F(P) (for some distribution P and some mapping F) if and only if it has a P-random F-preimage. This result (for computable distributions and mappings, and Martin-Löf randomness) was known for a long time (folklore); for layerwise computable mappings it was mentioned in Hoyrup and Rojas (2009, Proposition 5) (even for more general case of computable metric spaces). In this paper we provide a proof and discuss the related quantitative results and applications.