数学中的两种随机性

背景

本文源自 Hacker News 上的一篇数学与信息论讨论帖，作者在前一篇文章末尾抛出了一个谜题，这次专门用一整篇来回答它。谜题的核心是：两个统计上完全相同的数字序列，一个可以压缩到极致（只需三行代码就能完整传输），另一个却完全无法压缩（必须逐位发送）。这引出了一个更深层的问题：压缩的本质究竟是什么？统计冗余是否是唯一可用的压缩手段？文章围绕两种不同的压缩机制展开，并揭示了一个令人惊讶的结论。

核心内容

谜题重现

想象两个文件，每个文件都包含一百万位数字。第一个文件是纯噪声——好比掷了一百万次十面骰子，记录下每次的结果。第二个文件是圆周率 π 的前一百万位数字。现在从统计学家视角看它们：统计每个数字 0-9 出现的次数。在两个文件中，每个数字大约出现十分之一，所以频率直方图完全相同——都是平坦的无特征分布。无论运行什么样的“随机性检验”，两个文件都会通过。从所有统计指标来看，这两个文件一样：都表现为纯的、不可压缩的随机性。

然而，其中一个文件可以用三行代码发送给你——写个小程序“计算 π，打印一百万位”，然后你可以精确重新生成文件。另一个文件则完全无法缩小，要发送它必须逐位传输整个文件，因为不存在比它自身更短的描述。

问题核心

如果两个文件在统计上相同，为什么一个可以压缩，另一个不行？这个问题没有简单答案，它迫使我们重新审视“可压缩”到底意味着什么。一旦严格定义，“可压缩”实际上分裂成两个截然不同的概念。

两种压缩

整篇文章讨论的是无损压缩（不丢失任何信息，精确重建原始数据）。在这种严格限制下，事物可压缩的两种不同原因：

1. 统计原因：某些符号出现频率更高，就给常用符号短编码，罕见符号长编码，平均节省空间。这即 zip 文件和 Huffman 编码的原理，也是大多数人听到“压缩”时想的那种。

2. 过程原因：事物可能来自于一个简单规则（一个短程序），即使其符号看起来完美均匀分布。此时完全没有统计冗余可利用，但事物仍然可压缩，因为“短”存在于生成它的过程中，而非符号的频率中。

真正的问题是：统计冗余是唯一的可压缩性吗？π 告诉我们：不是。

统计压缩：熵

从预算构建熵

熵是符号源的平均惊讶程度（信息量）。如果一个源总是发出相同的符号，惊喜为零，熵为零；如果等概率发出十种不同数字，每个新符号带来最大惊喜，熵最大。大多数源介于两者之间。

熵与压缩的直接联系：惊讶正是你需要支付比特的东西。可预测的可以省略（接收方可以填充），令人惊讶的才必须实际传输。所以熵（比特/符号）是你能达到的最短平均消息长度——任何无损编码都无法突破的下限。

熵的推导

考虑用尽可能少的比特流发送符号，给每个符号分配一个码字（比特串）。常用符号应有短码字；罕见符号可以有长码字。但码字有竞争：为了无歧义解码，任何码字都不能是另一个的前缀。一个长度为 L 的码字消耗了编码空间的一个“切片”——1比特码字消耗一半空间，2比特码字消耗四分之一，以此类推。短码字是稀缺资源，给一个符号分配短码字会迫使其他码字变长。

这就像一个固定预算：每个符号必须购买一个码字，短码字更昂贵。最优策略是按符号出现概率的比例来花费预算：给概率为 p 的符号一个大小为 p 的预算切片，切片大小对应码字的成本 2^(-L)，即 p = 2^(-L)，所以 L = -log₂(p)。这就是理想码长：常见符号（p 接近1）长度接近0，罕见符号（p 很小）长度长。

平均消息长度即为每个符号的概率乘以其码长之和：H = Σ p * (-log₂ p) —— 这就是香农熵。它是任何编码能达到的最短平均消息长度。

另一种解读：熵是你需要用来隔离一个占据 p 概率空间的事物所需的“是/否”问题（二分）次数。罕见事物需要多次二分，常见事物需要少次。

均匀分布的最大熵

当所有符号等概率时熵最大。十个数字均匀分布时，熵为 log₂(10) ≈ 3.32 比特/数字，因为没有频繁符号可以分配便宜码字。我们的两个文件都是均匀分布，所以都具有最大熵——从统计角度看，两者都像理论上最不可压缩的东西。

熵的盲点

现在展示熵看不到什么。π 的数字在统计上是均匀的，因此统计压缩（如熵编码）对 π 无效。然而π有一个极短的生成程序——计算 π 的算法只占几行代码。这说明虽然 π 的符号分布没有统计冗余，但它具有过程冗余：它来自一个简单规则。这就是两种压缩的根本区别。

第二种压缩：过程/算法压缩

过程压缩不是看符号的频率，而是看能否用一个短程序描述整个序列。π 的十进制展开就是这样一个序列：它由一条简单规则生成（例如用莱布尼茨级数或更高效的算法），因此可以用一个短程序完全定义。而真正的随机噪声，其最小程序描述就是它本身（除非恰好有某种巧合模式）。这就是算法信息论（Algorithmic Information Theory）中的柯尔莫哥洛夫复杂度（Kolmogorov Complexity）：一个对象的最短程序长度比它的长度小多少。

关键区别：统计压缩衡量的是“相对于概率分布的期望最短描述”，而算法压缩衡量的是“绝对的最短描述（不考虑概率模型）”。π 在统计上不可压缩（因为没有概率偏差），但在算法上可压缩（因为存在短程序）。统计压缩依赖于分布，算法压缩依赖于对象的内部结构。

意外：你永远无法确认“不可压缩”

对于统计压缩，你可以确认它是不是最优的——只要找到任何更短的编码，就说明可压缩。对于算法压缩，情况截然不同：当你找到一个短程序时，你确实知道它是可压缩的；但当你找不到短程序时，你永远无法确定它不存在。因为有可能存在一个你还没发现的非常聪明的短程序。也就是说，算法可压缩性是一个半可判定性质：你可以证实它（当存在时），但无法证伪它（当不存在时）。这源于图灵停机问题——判断一个任意程序是否输出给定序列是不可判定的。

这正是答案的关键：π 的可压缩性属于第二种，而随机噪声的可压缩性（如果存在）我们永远无法排除。我们的直觉之所以困惑，是因为我们把两种压缩混为一谈。

关键要点

• 两种随机性：统计随机性（均匀分布）和算法随机性（无短程序描述）是两个不同概念。π 展示了统计上随机但算法上非随机的情况。
• 两种压缩：统计压缩（利用符号频率偏差）和过程压缩（利用生成规则的简短性）基于完全不同的原理。
• 熵的局限性：熵只度量统计冗余，无法捕捉过程冗余。统计上均匀的序列仍可能有卓越的压缩潜力。
• 柯尔莫哥洛夫复杂度：对象最短程序长度是其固有复杂度，但该长度不可计算——我们无法通过算法确定。
• 不可压缩性的不可证明性：对于任意序列，你永远无法断言“它不存在短程序”，因为总可能有尚未发现的巧妙规律。这使算法信息论具有深刻的哲学与实践意义。

意义与影响

这篇文章巧妙地将香农信息论与柯尔莫哥洛夫复杂度联系起来，揭示了“随机性”定义的多层次性。在人工智能和机器学习领域，这种区分非常关键：许多生成模型（如 LLM）实际上是在学习数据的“过程”（即潜在规律），而非仅仅拟合符号分布。π 的例子表明，一个高度规则的结构可能表面看起来完全随机，这正是深度学习能够从看似无规律的文本中提取意义的原因。

在密码学与伪随机数生成中，算法的简短性决定了其可预测性——高质量伪随机生成器必须让输出的任何短程序都无法简单描述（即通过所有统计检验，同时算法上看似不可压缩）。本文还指向一个更深层的结论：数据压缩的终极界限不是熵，而是柯尔莫哥洛夫复杂度——但后者无法计算，为我们留下了永恒的未知领域。

最后，作者留下的“意外”——你永远无法确认