数学中的联系：两种随机

# 数学中的关联：两种随机性 来源：https://stillthinking.net/posts/connections-in-math-two-kinds-of-random/ 免责声明：本文未使用任何人工智能辅助写作。任何错误、别扭的句子以及奇怪的偏离，都是100%有机、散养、人工制造的。 ## 捡起我丢在一旁的一个谜题 上次那篇文章的结尾，我丢下一个谜题然后走开了。现在再提一遍，因为整篇文章基本上就是我不肯放过它。 想象两个文件，每个文件有一百万个数字。第一个文件是纯噪声——想象我投掷一枚十面骰子一百万次，并记录下结果。第二个文件是π的第一百万个数字。 现在像统计学家那样审视它们：统计数字0到9每个出现的次数。在两个文件中，每个数字大约出现十分之一的时间，所以如果你绘制两个直方图，你无法区分它们——两者都是平坦、毫无特征的。你可以运行任何"这是随机的吗？"测试，因为两个文件都会通过。根据每一个统计指标，这两个文件是相同的：两者看起来都是纯粹的、不可压缩的随机性。 相同的直方图两次。从统计上看，噪声和π是无法区分的——两者都是平坦的、不可压缩的。 然而。 其中一个文件我可以用三行文字发送给你。我写一个很小的程序——"计算π，打印一百万位数字"——你就能精确地重新生成这个文件。另一个文件我根本无法压缩，要发送给你，我必须一个数字一个数字地发送整个文件，因为没有比它本身更短的描述了。 所以整篇文章浓缩成一个问题： > 如果两个文件在统计上完全相同，为什么我可以压缩其中一个而不能压缩另一个？ 关键在于，这个问题没有简单的答案，而且我认为这正是它有趣的地方。要深入探讨它，我们必须仔细思考"可压缩"这个词究竟意味着什么——一旦我们仔细分析，它就会分裂成两个截然不同的概念。本文的大部分内容就是关于如何区分这两个概念，以及第二个概念末尾的一个惊喜：存在一种可压缩性，当它存在时你总是可以确认，但当它不存在时你永远无法排除。 ## 两种压缩 一开始我想明确一点：本文讨论的都是**无损**压缩，这意味着不丢弃任何东西，也不进行任何近似——我发送给你一个较短的描述，你用它精确地重建出原始内容，一位不差。 即使有如此严格的规则，我认为一个事物可压缩的原因实际上有两种，而本文主要就是学习如何区分它们。 第一种原因是**统计性**的。某些符号出现得比其他符号更频繁，所以你可以给常见符号分配短编码，给罕见符号分配长编码，平均下来就能节省空间。这就是zip文件和哈夫曼编码所做的，我认为这是大多数人听到"压缩"这个词时想到的那种压缩。 第二种原因与**过程**有关。这个事物可能源于一个简单的规则——一个短程序——即使它的符号看起来完美均匀分布。在这种情况下，完全没有统计冗余可以利用，但事物仍然可以被压缩，因为简短性存在于生成它的过程中，而不是其符号的频率中。 所以本文真正的问题是：统计冗余是唯一一种可压缩性吗？而π即将给出否定答案。 ## 统计类型：熵 ### 从预算中构建熵 在我们能说明π的奇特之处之前，我们需要明确"统计压缩"究竟衡量什么，这个衡量指标有一个名字：**熵**。 非正式地说，熵是一个符号源中平均惊讶程度的度量。如果一个源总是发出相同的符号，那就没有任何惊讶——你已经知道接下来是什么，所以每个新符号没有告诉你任何信息，熵为零。如果一个源以等概率发出十个不同的数字，那么每个新符号都尽可能地令人惊讶，熵达到最大值。大多数源介于两者之间：有些符号常见（惊讶很少，信息很少），有些符号罕见（惊讶很大，信息很多），熵是所有符号的加权平均，权重是每个符号出现的频率。 与压缩的联系是直接的：惊讶正是你必须用比特来支付的东西。任何可预测的东西都可以省略，因为接收者可以填补它，而任何令人惊讶的东西你都必须实际传输。因此，一个源的熵（以比特每符号为单位）是你能希望达到的最短平均消息的长度——它是任何无损编码都无法突破的下限。 这就是非正式的画面。但我不想仅仅陈述公式就继续，因为有一种方式可以实际推导它，我借鉴了Chris Olah的《Visual Information Theory》（https://colah.github.io/posts/2015-09-Visual-Information/）的精神——下面的图片是我对他论证的演绎。 设定是这样的。我想用尽可能少的比特向你发送一串符号，方法是给每个符号分配一个**码字**——一小串比特。常见符号应该获得短码字；罕见符号可以承受长码字，因为我很少发送它们。这就是整个直观，并且显然是正确的。真正的问题是：对于一个以概率p出现的符号，它究竟*多*短？ 这里有一个转折，把它变成了一个真正的问题。码字之间存在竞争。为了能无歧义地解码一个流，没有一个码字可以是另一个码字的前缀——如果`0`是一个码字，那么其他任何码字都不能以`0`开头。因此，分配一个短码字是**昂贵的**：它会消耗掉剩余码字空间的一大块。精确地说，一个长度为L的码字会消耗该空间的1/2^L份额——一个1比特的码字烧掉一半的空间，一个2比特的码字烧掉四分之一，以此类推。短码字是一种稀缺资源，在某个码字上支出会迫使其他码字变长。 > 将其视为一个固定预算。每个符号都必须购买一个码字，而短码字更贵。 那么，如何在整个符号集合上分配这个固定预算呢？自然的做法——事实证明也是*最优*的做法——是根据每个符号使用的频率来分配：给一个概率为p的符号分配一块大小为p的预算。大小为p的预算可以购买一个成本为p的码字，即 1/2^L = p，这意味着 L = log₂(1/p)。 就是这样——不是断言的，而是推导出来的。一个概率为p的符号的理想码字长度是log₂(1/p)比特，所以常见符号（p接近1）的长度接近零，而罕见符号（p很小）则获得长码字。这与我们最初的直观完全一致，但现在有了量化数值。 我最喜欢的部分是：你可以将平均消息长度视为一个**面积**。将每个符号的概率放在一个轴上，其码字长度log₂(1/p)放在另一个轴上，这样每个符号就变成了一个面积为 p · log₂(1/p) 的矩形，总面积就是每符号的平均比特数： H = ∑ᵢ pᵢ log₂(1/pᵢ) = −∑ᵢ pᵢ log₂ pᵢ。 这就是香农熵，它是最小的**可能面积**——对于该分布，任何编码所能达到的最短平均消息。如果你给一个常见符号分配一个长码字，就会增加很多面积，而预算规则正好消除了这种浪费。 平均消息长度作为一个面积。每个符号是一个矩形：宽度是其码字长度，高度是其概率。笨拙的定长码（左）比最优预算码（右）堆积了更多的面积。熵是任何编码能达到的最小面积。 （还有另一种解读log₂(1/p)的方式，值得记住：它是将某个占据p比例可能性的东西隔离出来所需的"是/否"问题——二分——的次数。罕见事物需要多次二分，常见事物需要很少。同一个数字，两个视角。） 为了在一个干净的案例中感受它，考虑四个符号，概率分别为 1/2, 1/4, 1/8, 1/8。公式给出理想长度 1, 2, 3, 3，而且你实际上可以构建这些码字：`0`, `10`, `110`, `111`，没有前缀冲突。平均长度为 (1/2)(1) + (1/4)(2) + (1/8)(3) + (1/8)(3) = 1.75 比特，正好等于 H。最常见的符号获得了1比特的码字，罕见的符号付出了长度代价，预算完美平衡。 而我们的谜题需要的关键事实是：当所有可能性等概率时，熵最大。十个数字的均匀分布最大值为 log₂10 ≈ 3.32 比特每数字，因为没有频繁的符号可以购买廉价码字。我们的两个文件都是均匀的，所以两者都具有最大熵，这意味着在统计上，两者都和其他东西一样不可压缩。 ### 熵的盲点 现在我要小心，因为这里有一个容易搞错的微妙之处。熵实际上是*源*——一个以特定概率发射符号的过程——的性质，而不是单个固定序列的性质。严格来说，不存在"π的熵"这种东西；π只是一个序列，单独的序列并不附带概率。 那么，当我们"测量"其中一个文件的熵时，我们实际上在做什么？我们统计每个数字出现的次数，将这些频率视为来自一个独立发射符号的源，然后计算该源的熵。而这正是盲点进入的地方：当我们用一个序列的频率来概括它时，我们就抛弃了它的顺序，因此任何具有相同数字频率的序列在我们看来都是一样的——有序的和无序的都一样。π和噪声文件给出相同的频率，所以这种基于频率的估计认为它们同样随机，尽管其中一个是由一个极其简单的规则生成的。 这个规则并非对*所有*统计学都不可见——如果你知道正确的源，你可以描述π的过程，它的熵会非常小。这里的观点更狭窄：当我们手上只有一个序列，除了它的频率之外什么都没有时，生成规则不会留下任何痕迹。我们需要的是一个针对*单个对象*定义的度量，一个根本不需要源的度量。这正是柯尔莫哥洛夫复杂度的作用。 ## 过程类型：柯尔莫哥洛夫复杂度 这就是它，而且非常简单： > 一个字符串的**柯尔莫哥洛夫复杂度** K(x) 是输出该字符串的最短程序的长度。 不是任何东西的平均，不是分布——一个字符串，一个最短程序。 一个十亿个零的字符串具有极小的复杂度，因为"打印'0'十亿次"是一个非常短的程序。一个长度为n的真正随机字符串的复杂度大约为n，因为没有描述比字符串本身更短，所以"程序"基本上就是"打印整个东西"。而π？极小——几百个比特，因为一个小程序就能永远输出其数字。 所以谜题解开了，答案是我们当时拿着两把不同的尺子： - **香农熵**是统计的。它关乎一个*总体*——一个源、一个分布、长期运行——它只看到频率，别的都不看。 - **柯尔莫哥洛夫复杂度**是结构性的。它关乎*一个对象*，它看到规则、结构、生成过程。 π是一个使两把尺子尽可能大声地不一致的对象：**最大熵，最小复杂度**。统计学说"随机，无法压缩"，而柯尔莫哥洛夫说"微不足道，这是一个五行程序"。两者都对，因为它们回答的是不同的问题。 同一对象上的两把尺子：统计尺看到平坦直方图，说"随机"；算法尺看到微小的生成器，说"微不足道"。π是它们不一致的地方。 不过，两者之间有一座桥梁：对于一个真正随机的源，其输出的*期望*柯尔莫哥洛夫复杂度等于香农熵，相差一个小的常数。所以从**平均**来看，在整个分布上，两把尺子是一致的，我喜欢把统计学看作是算法结构在只观察总体时投下的影子。两者只在*个体*的、隐藏了生成规则的*特殊*对象上才会分开，而π是一个极端例子。但大多数对象根本不特殊——这就是下一件事，因为它也是这里唯一可以**证明**的事。 ## 几乎任何东西都无法被压缩 这里有一个听起来很难但实际上只是一个减法运算的论断： > 几乎每个字符串都是其自身的最短描述。大多数事物完全无法被压缩。 看。固定一个长度n，问：恰好长度为n的字符串有多少个？每个位置有2种选择，n个位置，所以有2^n个。 现在问：有多少个可能的**描述**比n短——即长度为0, 1, 2, ..., n−1的程序？把它们加起来得到 1 + 2 + 4 + ... + 2^(n−1) = 2^n − 1, 这比字符串总数少一个。 这整个论证。有2^n个字符串，只有2^n−1个更短的描述，所以即使在最慷慨的想象世界中——每个短描述都被使用，并且每个都指向不同的字符串——你最多只能覆盖其中2^n−1个，这意味着**至少有一个长度为n的字符串没有比自身更短的描述**。 再把这个计数稍微推进一点，情况会变得更糟。假设你想要真正的压缩，一个至少短c比特的描述。只有大约2^(n−c)个那么短的描述，所以最多只有所有字符串的**2^{−c}比例**能被压缩c比特。如果你想节省10比特，那么最多千分之一的字符串能做到；如果你想节省20比特，就降到百万分之一。所以深度压缩不仅罕见——你要求得越多，它就变得指数级更罕见。 我想指出这个论证的形状，因为它稍后会再次出现：我们刚刚证明了不可压缩的字符串几乎占据全部，**却从未命名过任何一个单独的字符串**。这就像数门和数钥匙，然后发现钥匙不够多——我们知道有些门必然锁着，但这个计数从未告诉我们哪扇门，因为我们从未实际打开过任何一扇。 计数中还隐藏着一个动作，值得明说出来：**程序本身就是一个字符串。**这是唯一能让我们把"字符串数量"和"程序数量"放在一起相减的原因，因为它们是同一类对象，用相同的比特来衡量。我认为这个简单事实是本文其余部分的基础，所以请记住它。 这个计数还解决了一件事。当我第一次理解这个论证时，我想耍小聪明避开它。如果我不存储字符串本身，而是存储它在所有字符串列表中的*索引*呢？或者如果我写一个短程序，从一个种子生成许多字符串，而我只存储种子呢？事实证明，每一种这样的方案都以相同的方式失败，原因总是相同的： > 要从一个大小为N的族中**选择**一个特定的事物，你需要一个能区分N个事物的名字，而一个能区分N个可能性的名字大约需要log₂N比特。 一个指向2^n个字符串的索引是一个需要n比特才能写下的数字，所以没有节省。一个从2^k个输出中挑选一个的种子需要k比特，这意味着种子只不过是指针的另一个名字。枚举一切都很便宜，直到你必须说出你指的是*哪个*项目时为止，而说出是哪一个需要完整的地址。**选择是不可约的**。