Randomness and invariance

Floris Persiau

doi:10.1093/logcom/exae083

2025-12-01

PRE

Floris Persiau *

Francesca Zaffora Blando

DOI：10.1093/logcom/exae083

原文链接

原文求助

摘要

En 中文

理查德·冯·米塞斯首次为无限二进制序列提供了随机性的严格定义，这些序列被用来表示无限长的实验结果序列或无限大（有序）的总体样本。根据冯·米塞斯的观点，如果一个序列在其内部，0和1的相对频率各自收敛于一个有限极限，并且这些极限相对频率在被他称为选择规则的某一类变换下保持不变，那么该序列就是随机的。尽管冯·米塞斯所定义的随机性概念已知存在一些严重局限性，但他的理论对于算法随机性的发展至关重要：算法随机性是可计算性理论的一个分支，它为定义单个数学对象的随机性提供了当前标准的途径。本文旨在引起人们注意，尽管存在缺陷，冯·米塞斯关于随机性论述背后的一个核心思想也构成了算法随机性理论的大部分基础。具体而言，我们将一些鲜为人知的结果汇集并加以推广，证明对于一大类概率测度，几个标准的算法随机性概念可以通过不变性来刻画，即通过在被视为冯·米塞斯选择规则一般化的某一类变换下对各种自然属性的保持或稳定满足来刻画。许多相关属性通常被描述为“最小随机性属性”：它们本身不足以保证随机性，但通常被认为是随机性的必要（或至少是可取的）条件。从这一视角来看，我们的结果表明算法随机性与各种最小随机性属性的稳定满足（包括冯·米塞斯原始论述中的极限相对频率的存在）是一致的。

Keyword:

Algorithmic randomness

von Mises' definition of randomness

invariance

measure-preserving transformations

computable measure theory

Church stochasticity