数学中的联系：两种随机数

免责声明：没有使用人工智能来编写此内容。任何错误、尴尬的句子和奇怪的切线都是 100% 自然的、自由的和人为的。捡起我留在上一篇文章周围的一个谜题，就在最后，我扔下了一个谜题并走开了。又来了，因为这整篇文章基本上是我拒绝放手的。想象两个文件，每个文件包含一百万位数字。第一个是纯粹的噪音——想象一下我把一个十面骰子掷了一百万次并写下了结果。第二个是 π \pi π 的前百万位数字。现在以统计学家的方式来看待它们：计算从 0 0 0 到 9 9 9 的每个数字出现的频率。在这两个文件中，每个数字出现的次数大约是十分之一，因此如果绘制两个直方图，您无法区分它们——两者都是平坦的，都没有特征。你可以运行任何“这是随机的吗？”测试你喜欢的，因为两个文件都会通过。从每一个统计指标来看，这两个文件都是相同的：两者看起来都是纯粹的、不可压缩的随机性。然而。我可以将其中一份文件分三行发送给您。我给你写了一个小程序——“计算 π \pi π ，打印一百万位数字”——然后你就可以准确地重新生成文件。另一个文件我根本无法缩小，为了将其发送给您，我必须逐个数字地发送整个文件，因为没有比它本身更短的描述了。因此，这是一个问题中的整篇文章：如果两个文件在统计上是相同的，为什么我可以压缩一个而不是另一个？问题是，这个问题没有一个简单的答案，我认为这正是它有趣的地方。为了实现这一目标，我们必须小心“可压缩”这个词的实际含义——一旦我们小心了，它就会分裂成两个截然不同的想法。这篇文章的大部分内容都是关于将这两者分开，以及在第二篇文章结束时等待的惊喜：一种可压缩性，当它存在时你总是可以确认它，但当它不存在时你永远不能排除它。两种压缩我想从一开始就明确一件事：这篇文章中的所有内容都是关于无损压缩的，这意味着没有任何内容被丢弃，也没有任何内容是近似的——我向您发送了一个较短的描述，然后您从中一点一点地重建精确的原始内容。即使有这样严格的规则，我认为一个东西可以压缩确实有两个不同的原因，这篇文章主要是关于学习区分它们。第一个原因是统计上的。有些符号比其他符号出现的频率更高，因此您可以为常见的符号提供短代码，为罕见的符号提供长代码，平均而言，您可以节省空间。这就是 zip 文件和霍夫曼编码的作用，我认为这是大多数人听到这个词时想到的压缩类型。第二个原因是关于过程的。这个东西可能来自一个简单的规则——一个简短的程序——即使它的符号看起来完全均匀地分布。在这种情况下，根本没有可利用的统计冗余，但事物仍然会压缩，因为短暂性存在于生成它的过程中，而不是存在于其符号的频率中。所以这篇文章的真正问题是：统计冗余是唯一的可压缩性吗？而 π \pi π 就要说不了。统计类型：熵 从预算中构建熵 在我们说出 π \pi π 的奇怪之处之前，我们需要确定“统计压缩”所测量的是什么，并且该测量有一个名称：熵。非正式地，熵是符号源中惊喜的平均数量。如果一个源总是发出相同的符号，那么根本就没有什么奇怪的——你已经知道即将发生什么，所以每个新符号都不会告诉你什么，而且熵为零。如果一个源以相同的概率发出十个不同的数字，那么每个新符号都会尽可能令人惊讶，并且熵是最大的。大多数来源介于两者之间：有些符号很常见（小惊喜，信息少），有些符号很罕见（大惊喜，信息更多），熵是所有符号的平均值，按每个符号出现的频率进行加权。与压缩的联系是直接的：惊喜正是你必须付出代价才能得到的。任何可预测的内容你都可以省略，因为接收者可以填充它，而任何令人惊讶的内容你都必须实际传输。因此，源的熵（以每个符号的位数为单位）是您可以希望实现的最短平均消息的大小 - 这是任何无损代码都无法低于的下限。这是非正式的图片。但我不想只是陈述公式并继续前进，因为有一种方法可以实际推导它，而且我从 Chris Olah 可爱的视觉信息理论中借用了它的精神 - 下面的图片是我自己版本的他的论点。这是设置。我想使用尽可能少的位向您发送符号流，为每个符号提供一个码字（一小串位）。常用符号应采用短码字；稀有符号可以承受长符号，