论文标题
Martin-Löf随机数的中央限制定理
Central Limit Theorems for Martin-Löf Random Numbers
论文作者
论文摘要
我们证明了与Martin-Löf随机（MLR）序列的中心极限定理（CLT）相关的两个定理。 Martin-Löf随机性试图捕获一系列“真正的随机”的含义。相比之下，CLT并没有对单个随机序列的行为做出断言，而仅在一系列随机变量的分布行为上。从语义上讲，我们通常将CLT解释为关于无限多序列的集体行为的断言。但是，我们的直觉是，如果一系列位是“真正的随机”，那么它应该提供“随机性来源”，以使CLT型结果应保持。我们通过使用采样方案来解决这一困难，该方案从单个二进制序列中生成无限数量的样品。我们表明，当我们将该方案应用于马丁 - 洛夫随机序列时，这些样品的经验矩和累积密度函数（CDF）趋向于它们的相应对应物以进行正态分布。我们还证明了众所周知的几乎确定的中心限制定理（ASCLT），该定理提供了一种替代性，尽管直观较低，但对此问题的答案不太直观。两种结果也概括为Schnorr随机序列。
We prove two theorems related to the Central Limit Theorem (CLT) for Martin-Löf Random (MLR) sequences. Martin-Löf randomness attempts to capture what it means for a sequence of bits to be "truly random". By contrast, CLTs do not make assertions about the behavior of a single random sequence, but only on the distributional behavior of a sequence of random variables. Semantically, we usually interpret CLTs as assertions about the collective behavior of infinitely many sequences. Yet, our intuition is that if a sequence of bits is "truly random", then it should provide a "source of randomness" for which CLT-type results should hold. We tackle this difficulty by using a sampling scheme that generates an infinite number of samples from a single binary sequence. We show that when we apply this scheme to a Martin-Löf random sequence, the empirical moments and cumulative density functions (CDF) of these samples tend to their corresponding counterparts for the normal distribution. We also prove the well known almost sure central limit theorem (ASCLT), which provides an alternative, albeit less intuitive, answer to this question. Both results are also generalized for Schnorr random sequences.
