算法随机性与不变性：从冯·米塞斯到现代计算理论的桥梁

《Journal of Logic and Computation》：Randomness and invariance

本文聚焦于算法随机性理论的核心问题，探讨了如何通过不变性原理将冯·米塞斯（Richard von Mises）的随机序列思想延续至现代计算理论。研究者通过泛化并整合一系列鲜为人知的结果，证明了对于一大类可计算概率测度，Schnorr随机性、Kurtz随机性和Martin-L?f随机性均可通过“在几乎处处可计算的保测变换下保持某种最小随机性属性”来刻画。这一发现不仅揭示了冯·米塞斯随机性定义与算法随机性理论之间深刻的连续性，也为理解随机性的本质提供了新的视角，相关成果发表于《Journal of Logic and Computation》。

　　

在概率论与计算理论的交叉领域，如何定义“随机性”一直是一个核心且富有挑战性的问题。早在20世纪初，理查德·冯·米塞斯就试图为无限二进制序列的随机性提供一个严格的频率主义解释。他认为，一个序列是随机的，当且仅当其中0和1的相对频率收敛于一个极限，并且这个极限频率在一类他称为“选择规则”的变换下保持不变。尽管冯·米塞斯的理论因其自身的局限性（如维勒指出的问题）而备受争议，但它无疑是算法随机性理论发展的重要催化剂。算法随机性，作为可计算性理论的一个分支，如今已成为定义数学对象随机性的标准方法。那么，冯·米塞斯的原始思想与现代算法随机性理论之间，是否存在着被忽视的深刻联系？这正是本文作者所要探讨的核心问题。

传统观点认为，冯·米塞斯的路径与算法随机性理论截然不同。然而，本文作者指出，尽管冯·米塞斯的定义存在缺陷，但其核心思想——即随机性意味着某种“最小随机性属性”在适当的变换类下能够“稳定地满足”——在算法随机性理论中得到了延续和发展。这里所谓的“稳定满足”，是指一个序列不仅自身满足某个属性，而且在该序列经过一系列特定变换后得到的序列仍然满足该属性。冯·米塞斯使用的变换类是“选择规则”，而在现代算法随机性理论中，这个角色被“几乎处处可计算的保测变换”所取代，后者可以看作是前者的一个广义推广。

为了证明这种连续性，研究人员系统性地回顾并推广了一系列已有的结果。他们的研究主要围绕三个核心的算法随机性概念展开：Schnorr随机性、Kurtz随机性和Martin-L?f随机性。这些概念在强度上形成一个层级结构，其中Martin-L?f随机性最强，Schnorr随机性次之，Kurtz随机性最弱。同时，文章也讨论了如Church随机性（对冯·米塞斯定义的一种可计算精确化）和可计算随机性等其他相关概念。

本文的研究并非依赖于复杂的实验技术，而是建立在严谨的数学证明和理论分析之上。其主要技术方法包括：

1. 1.
   可计算测度理论：在Cantor空间（无限二进制序列构成的空间）上，基于可计算、无原子、严格正的概率测度开展工作，这使得理论框架具有广泛的适用性。
2. 2.
   算法随机性的统计测试与（超）鞅刻画：利用马丁-勒夫测试（Martin-L?f tests）、施诺尔测试（Schnorr tests）等工具定义随机性，并通过（超）鞅（（super)martingales）这一博弈论概念来刻画随机序列的不可预测性。
3. 3.
   不变性分析：核心方法是构造和分析几乎处处可计算的保测变换（almost everywhere computable measure-preserving transformations），研究各类随机性概念及最小随机性属性（如强大数定律、不可计算性）在这些变换下的行为，从而建立其与不变性原理的联系。

Schnorr随机性与强大数定律的稳定满足

研究者首先将Schnorr的一个鲜为人知的结果进行了推广。Schnorr曾证明，对于均匀测度λ，一个序列是Schnorr随机的，当且仅当它在所有几乎处处可计算的λ-保测变换下，其像序列仍然满足强大数定律。本文作者将这一结论扩展到了一类更广泛的概率测度上，即那些可计算、无原子、严格正且非极端的概率测度。这意味着，Schnorr随机性可以被精确地描述为“强大数定律在几乎处处可计算保测变换下的稳定满足”。这就在形式上与冯·米塞斯用选择规则来保持极限频率不变的定义产生了直接的类比。进一步地，根据这一不变性原理，任何被Schnorr随机性所蕴含且其本身蕴含了强大数定律的统计规律（例如弱Church随机性、迭代对数定律），其稳定满足性都同样等价于Schnorr随机性。

Kurtz随机性与不可计算性/双免疫性的稳定满足

对于更弱的Kurtz随机性，研究者证明了类似的刻画。他们指出，对于一个可计算、无原子、严格正的概率测度，一个序列是Kurtz随机的，当且仅当它在所有几乎处处可计算的保测变换下的像序列都是不可计算的。换言之，Kurtz随机性等价于“不可计算性”的稳定满足。此外，对于一类更强的“强无原子”概率测度，Kurtz随机性还蕴含了“双免疫性”（即序列中不存在可计算的、全为0或全为1的无限子序列）。因此，在这类测度下，Kurtz随机性也等价于“双免疫性”的稳定满足。

稳定Church随机性与Martin-L?f随机性

文章随后探讨了“稳定Church随机性”的概念，即要求一个序列在几乎所有可计算保测变换下的像都是Church随机的。研究表明，Martin-L?f随机性必然蕴含稳定Church随机性，而稳定Church随机性又蕴含Schnorr随机性。然而，稳定Church随机性是否等同于某个已知的算法随机性概念，仍是一个开放性问题。它可能等同于Martin-L?f随机性，也可能与可计算随机性无法比较。

Martin-L?f随机性与可计算随机性的稳定满足

最后，文章讨论了一个由Rute和Petrovi?证明的重要结果：对于均匀测度，Martin-L?f随机性等价于“可计算随机性”在几乎处处可计算保测变换下的稳定满足。本文指出，这一结果可以轻松地推广到所有可计算无原子概率测度。由于可计算随机性本身不被几乎处处可计算保测变换所保持，但其稳定满足性却刻画了更强的Martin-L?f随机性，这进一步凸显了不变性原理在区分不同强度随机性概念上的强大能力。

本文的结论强调，对于一大类可计算概率测度，三种经典的算法随机性概念——Martin-L?f随机性、Schnorr随机性和Kurtz随机性——都可以通过不变性 under 几乎处处可计算保测变换来刻画。特别是，Schnorr和Kurtz随机性分别对应于某些“最小随机性属性”（如强大数定律、不可计算性）的稳定满足。这些发现揭示了冯·米塞斯随机性思想与算法随机性理论之间一种稳健的、此前未被充分认识的联系。尽管两者在形式化和技术细节上存在巨大差异，但冯·米塞斯定义中的核心成分——即通过变换下的不变性来定义随机性——在算法随机性的现代框架中得以保留和升华。这项工作不仅统一和推广了领域内的一些分散结果，也为进一步探索随机性的本质，以及将算法随机性理论应用于遍历理论和分析学等其他领域提供了新的思路和工具。