Algorithmic tests and randomness with respect to a class of measures
Algorithmic tests and randomness with respect to a class of measures
复制标题
关于一类度量的算法测试和随机性
DOI：
10.1134/s0081543811060058
复制
发表时间：
2011
影响因子：
0.5
通讯作者：
A. Shen
中科院分区：
文献类型：
--
作者：
L. Bienvenu;P. Gács;M. Hoyrup;Cristobal Rojas;A. Shen
本文根据其他地方的结果提供了有关措施类别的随机性，以及对其上下文的教学结果。在随机性缺陷方面，以前缀复杂性表示随机性缺陷（两种形式）。考虑到复杂性）。引入了Bernoulli序列的“均匀测试”的概念，该序列允许对此结果进行定量增强BP具有重要的属性，即在BP的每个随机序列中恢复了P，在更一般的建设性度量空间的环境中，纸质研究的一些重要后果（以及上面提到的大多数问题）也是如此。
This paper offers some new results on randomness with respect to classes of measures, along with a didactic exposition of their context based on results that appeared elsewhere. We start with the reformulation of the Martin-Löf definition of randomness (with respect to computable measures) in terms of randomness deficiency functions. A formula that expresses the randomness deficiency in terms of prefix complexity is given (in two forms). Some approaches that go in another direction (from deficiency to complexity) are considered. The notion of Bernoulli randomness (independent coin tosses for an asymmetric coin with some probability p of head) is defined. It is shown that a sequence is Bernoulli if it is random with respect to some Bernoulli measure Bp. A notion of “uniform test” for Bernoulli sequences is introduced which allows a quantitative strengthening of this result. Uniform tests are then generalized to arbitrary measures. Bernoulli measures Bp have the important property that p can be recovered from each random sequence of Bp. The paper studies some important consequences of this orthogonality property (as well as most other questions mentioned above) also in the more general setting of constructive metric spaces.