第四百四十一章香农的信息熵

章节错误,点此举报(免注册),举报后维护人员会在两分钟内校正章节内容,请耐心等待,并刷新页面。

当n=1000时，至少有44.4%的概率这个平均值很接近1/3。

当n=10000时，至少有94.4%的概率这个平均值很接近1/3。

当n=100000时，至少有99.4%的概率这个平均值很接近1/3。

当n=1000000时，至少有99.9%的概率这个平均值很接近1/3。

现在展开你想象的翅膀，你应该看到当n变成无穷大的时候，这个平均值就不再是“几乎总是很接近1/3”，而是“就是1/3”了！

至此同学们可能已经体会出俺极其考究、极负责任的“几乎总是很接近”了吧。这里的情怀还是让俺带你们领略一下吧。老千掷出的序列当然是随机的、不确定的、没有规律的。这个序列的平均数虽然也在1/3周围随机跳动，但却随着n的增大越发确定起来。当n很小、她就在你跟前的时候，变化多端、捉摸不定的她让你无法看清；当n增大的时候，她渐行渐远，但她在风中颤动的身影却在你记忆的相机里慢慢聚焦，越来越清晰；直到她消逝在无限的远方，她竟定格成一幅永恒而又无比真切的画面......

学霸们可能会觉得俺太矫情了：不就一个简单的大数定理吗，有必要这么忽悠吗？其实俺也觉得自己有些矫情。但看完本文之后，俺请你再回头体会一下大数定理的情怀。

“二十个问题”游戏的准确规则及特例

用概率论武装一下之后，同学们应该已经认识到，在“二十个问题”游戏中俺心里想的神秘数字其实就是一个随机变量X。我们可以假设它的取值范围S={1，2，…，M}和概率分布函数P(x)都已知。当然在实际情况下我们未必真知道P(x)，但往往可以大致估计这个函数。如果对这个分布函数我们一无所知，我们不妨认为P(x)是个均匀分布。

对于任意一个给定的问问题策略，如果俺心里的神秘数字是x，我们把所需的问题个数记作L(x)。比如M=8，而我们用前面提到的那个从1问到7的策略问问题，我们就会得到：

L(1)=1，L(2)=2，L(3)=3，L(4)=4，

L(5)=5，L(6)=6，L(7)=7，L(=7。

（对，L(=7，俺没敲错。）

因为俺心里想的是个随机变量X，在这个策略下所需要的问题数目L(X)就也是个随机变量。这个随机变量L(X)也有一个分布，在知道P(x)的前提下，如果想算也是可以算出来的。但是俺懒得算它。

既然L(X)是个随机变量，一个最自然的方式定义这个策略所需要的问题个数就是用这个随机变量的均值，或者说用平均所需要的问题个数。如果你的数字直觉好，应该可以看到，即使不求L(X)的分布，这个随机变量的均值其实就是

L(1)*P(1)+L(2)*P(2)+…+L(M)*P(M).

用L(X)的均值定义一个问问题策略所需要的问题个数除了“自然”，还有什么物理意义吗？当然！前面的大数定理告诉咱们，如果你用这个策略玩这个游戏很多次，你所用问题个数的平均值“几乎总是很接近”L(X)的均值。而当你玩了这个游戏无数次之后，你平均每次用的问题数就正好是这个L(X)的均值。

由此可见，如果俺们准备玩这个游戏很多次，那么用L(X)的均值定义所需要问题的个数，用金星老师的话说就是一个动作两个字：完美。

至此，俺们已经确定这个“二十个问题”游戏的准确规则，即：你要设计一种问问题的策略，当用这个策略跟俺玩很多次（更准确的说，无数次）这个游戏之后，平均每次用的问题个数要越少越好！换句话说，我们希望寻找一个最好的问问题策略，同时确定最少需要多少个问题（平均意义上）。

其实在一些特殊的情况下，确定最优的问问题策略和最少需要的问题个数并不困难。

考虑这样一个特例：俺心里的神秘数字X的取值范围是S={1，2，…，8}，而且X的概率分布函数是个均匀分布。那么最优的问问题方法就是所谓的“二分法”：每问一个问题要把这个神秘数字的可能范围缩减一半。比如这样的问法：

问题1:把集合{1，2，…，8}分成左右两份，左边的是{1，2，3，4}，右边的是{5，6，7，8}。然后问：你想的数是不是在左边啊？

问题2:根据俺的答案，你可以确定这个神秘数字只剩下四种选择。你再类似地把四种选择分成左右两份，然后问：你想的数是不是在左边啊？

问题3:根据俺的答案，你现在可以确定这个神秘数字只有两种选择，再把它们一个放左边，一个放右边。你再问：你想的数是不是在左边啊？

如此问完三个问题，你一定知道了俺的神秘数字。相信你的直觉也应该告诉你，这就是最优问法！那么在这个例子里，所需的最少问题个数就是3。从咱们用每个问题把猜测空间一切两半的问法，同学们应该也已经认识到，这里得出的最少问题数3正是因为8=2^3，或者说，2=log8.（本文中所有的对数操作均以2为底数）。

在这个例子中有个现象也值得注意一下：不管俺心里想的是个什么数字，使用二分法所需的问题数字都是3，一个完全确定，毫无随机性的数字。

这个特例显然可以推广：如果神秘数字X的概率分布函数是在2^K种可能性上的均匀分布，那么“二十个问题”游戏的最优策略可以通过二分法实现；在这种策略下，不论神秘数字是什么，问出它所需要的问题数都是K，因此所需要的平均问题数也是K。同学们请用红笔圈下这个结论（小心别把手机触摸屏划坏了），咱么晚点要用到这个结论。

当然，这个二分法只适合于这样的特例，当神秘数字的可能性总数不是2的多少次方的时候，或者当神秘数字的分布不均匀的时候，这种问法显然不是最优的。这个问题任意形式的最优解法曾让一个叫大卫·霍夫曼（DavidHuffman）的年轻学生在1951年一夜成名。不过，那已经是在香农提出信息论三年之后了。

在香农独特的视角里，这个问题并不至关重要。在俺的想象中，当香农看到满屋子小朋友们叽叽喳喳地玩这个游戏的时候，他笑了笑，说：你们慢慢玩吧。然后他点起一支烟，凝视着窗外的远方。在落霞与孤鹜齐飞的秋色里，他看到了这个游戏的另一种设计。

既然用L(X)的均值定义所需要问题的个数依赖于把这“二十个问题”游戏玩很多次，那么考虑一下这个游戏的一个变种，就是把这很多次游戏攒起来一起玩：俺拿出一张很长很长的纸条，然后随机想n个相互独立的神秘数字，X1，X2，…，Xn（每个数字的分布都是同一个定义在S={1，2，…，M}上的概率分布函数，P(x)）。俺把这些数字一个一个地写到纸条上。这里n很大很大，所以纸条很长很长。然后你再来问俺“是不是”台或一百台电脑来。你问俺的问题要是计算太复杂，俺也可以去搬电脑来算。总之，咱们不用管计算有多复杂，俺俩都有无限的计算能力。在这个攒着玩的“二十个问题”游戏中，怎样的问问题策略才最优呢？最优的策略所需要的平均问题数目又是多少呢？

暂且先不讨论这个问题的答案，咱们先审视一下这个新的游戏设计的应用意义吧。

想象一下，俺写在纸条上的序列其实是俺刚写好的长篇小说（俺写下的每一个数其实对应于新华字典里的一个字），又或者俺写在纸条上的序列其实对应于俺长期夜观星象的结果，记录了不为人知的宇宙奥秘（俺写的每个数字都是对观测到的宇宙状态的描述）。在你问俺问题的时候，俺的回答将是一个长长的由Yes/No组成的序列。如果把Yes记作1，No记作0，俺的回答其实就是一个0/1组成的序列。

一个可以取0/1两个值的变量，或者一个可以储存0/1两种不同状态的存储单元，就是人们常说的比特（bit）。所以俺的回答其实就是一个比特序列。你希望用最少的问题就等同于要求这个比特序列最短，或者说要求用最少的比特数表示俺纸条上的内容。这个问题其实就是通信中的数据压缩问题！

数据压缩，又叫“信源编码”，大约是干这样一件事。假设有个信息源，就是一个能不停往外蹦信息的东西，比如一直在想神秘数字的俺，夜观星象的俺，写小说的俺，等等等等。信息源产生的信息从数学上说就是一个随机变量序列（更有文化的说法叫随机过程）。这个随机变量序列可以有很多种形式，最简单形式就是其中的随机变量都相互独立而且服从相同的分布。对这个信息源进行数据压缩包括了两个环节，编码和解码。编码就是把从信息源蹦出来的随机序列表示成比特序列，而且越短越好；解码就是从比特序列中还原出信息源蹦出来的随机序列。数据压缩可以大幅度降低数据存储和通讯需要的资源，已经是现代通信技术的一个重要组成部分。

现在回到“二十个问题”游戏。如果这个游戏一个一个分开玩，其实就是在数据压缩的时候，对信息源里蹦出的每个随机变量单独做压缩。如果这个游戏攒n个一起玩，其实就是对随机序列中的n个随机变量同时进行压缩。显然，对每个随机变量单独进行压缩一定不会比对整个随机序列同时做压缩效率更高（这里的效率是用平均每个随机变量压缩后的比特数来衡量的，比特数越低，效率越高）。这里的道理是这样的：比如俺俩攒n个“二十个问题”游戏一起玩，但你设计问题的时候，每个问题只是针对序列中的一个随机变量，而不是针对整个序列。这样的问问题策略显然等同于把每个游戏分开玩。也就是说，这个游戏一个一个分别玩可以认为是攒起来一起玩的一种特例。因而分别玩能达到的效率，攒起来玩也可以达到。因为同样的道理，如果这个游戏攒2n个一起玩，其效率也一定不比攒n个一起玩低。也就是说，为了提高效率，n应该越大越好。

那么攒起来玩的效率到底最高可以达到多少呢？或者说，对一个给定的信息源，平均每个蹦出来的随机变量最少需要多少个比特来表示呢？这个数字通常跟序列的长度n相关，而且对于任意一个给定的n，即使俺们能够确定最优的压缩方法，精确地确定这个数字也是一件很棘手的事。不过既然俺们已经认识到n越大越好，那不妨考虑n取无穷大吧。

当n取无穷大时，如果俺们能够计算出信息源里平均每个蹦出的随机变量最少需要多少比特来表示，这个数字不仅标记了最优的压缩效率，它同时还有着更深刻的物理意义：它跟序列的长度n无关，也跟编码方法无关；换言之，这个比特数只取决于信息源本身（即随机变量X或其分布P(x)）。因为这个比特数是由最优编码／解码方法实现的，它同时说明了两件事：

1.只要解码端接收到的平均比特数不到这个数字（平均到每个随机变量上），不论用什么编码／解码方法都一定无法重建信息源里蹦出的随机序列。

2.只要解码端接收到的平均比特数超过这个数字，就一定有一种编码／解码方法可以使解码端重建这个序列。

这就是说，在平均意义上，你一定需要这么多比特来表达信息源里蹦出的每一个随机变量，而且只要这么多比特就够了！因此，这个比特数实际上就标注了这个信息源在以什么样的“速率”释放“信息”，或者说标注了这个信息源里蹦出的每个随机变量平均包涵了多少“信息”！

下面俺们就来看看是否可以导出这个最小比特数。

嗯，没错，终于要掀开她的红盖头了。等不及了吧。

最小比特数

还是二十个问题攒着玩吧。不过这次俺也不去想什么随机数了。俺就把之前例子里的那个老千找来，让他躲在俺身后不停地掷硬币。俺就把他掷出的0/1结果写在纸条上。等俺写完n个数的时候，就让你开始问问题。前面说过，这无非就是把这个老千掷硬币的结果当作一个信息源，对这个信息源做压缩。

八哥电影

第四百四十一章 香农的信息熵

第四百四十一章香农的信息熵