0与1世界中的信息、比特与决策
[遇见数学翻译小组] 核心成员: L.J.C.
一名喜欢弹钢琴和睡觉的高中生
校对 | 阳纯
英文 | https://dwz.cn/RaLO2jiy
★提示: 如果文中数字/公式显示较大, 请点击右上角中"刷新"即可恢复正常.
▌用 1 个比特在二叉路口寻出一条路线
点标出),并且想要走到
点处。请注意你并不知道这个俯视全貌的图,你只知道在自己面前有一个分叉,以及做出的决定。如果你之前并没有得到关于选择哪条路的信息,那么
点的前叉就呈现两条相同可能的选择。如果我们把指令(帮助你走到
点)用二进制数来表示(0=左 1=右),那么这一个二进制数字就给你提供了 1 比特的信息,并告诉了你该选择哪条路。
到
的整个路程。想象一下你沿路漫步到了另一个分叉
。因为你还不知道该选哪条路,这次一个二进制数字(1=右)还可以为你提供 1 比特的信息从而让你选择正确的路线,也就把你带到了
点处。
点即便是你从
点出发后所有可能的临时岔路(共四个)中的一个。两个二进制数字给你提供了两比特的信息并且让你能够从四个(均等的)选项中做出选择,
.
第三个二进制数字(1=右)又给你提供了 1 比特的信息,并且可以让你再一次选择正确的道路,最终到达
点处。
从
点出发到现在位置,有了八条总共可选择的路,所以三个二进制数字(就给你提供了 3 比特的信息)足够让你从八个相同可能的选项中做出选择,
。
请注意,你一旦在
点做出决定要走哪条路,八个中就会有一半的道路无法再进行选择了。同样地,在连续的分叉口所做的决定就会让剩下可以选的终点数量缩减一半。
▌在八种结果之间选择
对上面的情况,我们来概括下。
代表分叉的次数。
代表
次分叉后终点的数量。如果你已经走过了
个分叉口,那么你就已经从
个终点中做出了选择。
个分叉口就需要
比特信息,那么你可以从
个均等的选项中做出选择。
如下图所示,我们既可以用 0 至 7 这八个十进制数字来标记八个可能的每个终点。如下表所示,这些十进制数字和二进制数字可以看成是两种相同的表示方法。用二进制数字计数可以转成成用十进制数字。
▌在
种选择之间进行决策
若想知道任何一条路线的复杂程度,既可以参考最终"可能终点"的个数,也可以参考从头到尾必经的分叉口的总个数。我们知道,当分叉口的数量增多时,"可能的终点"的个数也会随之增多。正如我们已经看到的一样,如果这里会遇到三个分叉口,那么就会有
个可能的终点。
▲ 对数度量需要决策的次数
个可能的终点,那么推测会有几个分叉口?换句话说,给定了八个终点, 2 的几次平方能开到 8?在这种情况下,我们知道答案是
,也就是以二为底求八的对数。由此,
就是八个终点所暗示的分叉口的个数。
更加概括地说,以 2 为底求
的对数就是在求需要将 2 提高到其几次幂才能等于
;也就是说,从
中解出
这件事。同等地,对于一个给定的数字
,我们想要用对数运算来直接表达
,就有:
比特的信息。
▌折半来搜索出答案
二十个问题(Twenty Questions)游戏在20世纪40年代后期逐渐流行起来,成为当时每周电视电台问答节目的流行栏目。在游戏中,一个玩家被选为应答者,他选择某个主题(或物体),但不能向其他人透露。所有其他参与者都是发问者,他们轮流问一个可以用简单的"是"或"否"回答的问题。如在 20 个问题后,仍然没人猜对,那么应答者获胜。
▲ 《20个问题》电视栏目片头
能提出一个好问题非常重要,因为每个问题应该删掉一半可能的答案。选择去问一个看起来很明知故问的问题可不是什么好主意。比如说,如果你的问题是"你说的这个物体能字典里找到吗?",那么得到的答案几乎就是"是啊!",这个答案是你早就可以预料得到的,也就不会给你提供任何额外的信息。
相反地,一个精挑细选的问题即是一个你对答案或是或非或毫无头绪的问题——答案在任何一边的概率都是一样的——50:50。在这种情况下,答案会正好给你提供 1 比特的信息。在下图中,一个简化版的"二十个问题"游戏能更清楚地说明这一点。
▲ 你心里的答案是不是哺乳动物?
之所以这种办法很简洁也很奏效是因为二十个问题可以让你从正好从
个相同可能的单词(即大约一百万个单词)中做出选择。由此,通过提问题所获得的这个 20 比特的信息就可以让你从大约一百万个的单词中找到最终那个正确的答案。
如果再去添加一个问题就会创造出一个新的游戏,叫做"21个问题",那就要从大约二百万个单词中逐步缩小范围至最后一个单词。就是说,每一个新增的问题就还得额外的 1 比特信息。理论上,游戏"40个问题"就需要 40 比特的信息,要从
个潜在答案中找出一个单词。
对照二叉树的例子中,40 比特可以让你经过 40 个分叉口并找到最终的节点答案,也就是从大约一万亿条可能的路线中找出一条路径。所以下次在经过 40 次决策而到达了目的地后,别忘了你已经成功地避开了
错误的结果。
▌信息、比特和二进制数字
尽管"比特"一词是从"二进制"中得出的,但二者之间有一个微妙却很关键的不同之处。一个二进制数字是一个二进制变量的值,这个值可以是一个 0,也可以是一个 1,但是一个二进制数字自身并不是信息。相对而言, 1 比特是一个有限的信息量。比特和二进制数字本质上不是一类东西,如果搞混了就犯了范畴错误(category mistake)。
▲ 克劳德·香农,信息论创始人
第一个极端例子是如果你已经知道了应该在岔路
点走左手边的路,接着我给你了一个二进制数字 0(=左),那么虽然你得到了一个二进制数字,但是并没有得到任何有用的信息。
可能是正确路线,然后我随后给你了一个 0,这会使刚才的提示变得更令人信服,那么这个 0 就给你提供了少于 1 比特的信息。(完)