第441章香农的信息熵（1 / 2）

一张高清电视分辨率的照片，如果没有经过压缩，要占用600万个字节的计算机内存(6MB，1个字节是8个比特)。

可是如果这张照片照的是一面单色的墙的话，它所含的信息量就很小，只要用三个字节就可以描写整张照片(3个字节描写红绿蓝三种颜色的深浅)。

所以单色墙的照片的文件大小，可以从600万个字节压缩到3个字节，大大减少了占用计算机内存的空间和传输照片所需的时间。

但一般一张照片的信息量要比三个字节大很多，那么如何量化照片所含的信息量？照片的压缩最多能有多少倍？

香农是量化信息的第一人。

有趣的是，他量化信息的公式早就出现在了玻尔兹曼的墓碑上。

当然玻尔兹曼得到这个公式，不是为了研究信息，而是为了研究热力学中的混乱度(所以玻尔兹曼的公式和香农的公式差了一个负号)。

热力学的一个中心概念——温度，就是混乱度随着能量的增加而增加的速率。我们的世界真是处处相通。

南加州大学（University of Southern California)电子工程系教授巴特·磕死磕（Bart Kosko）说：“爱因斯坦相对论之革命性在于它颠覆了之前的牛顿力学，而香农信息论之革命性在于它前无古人。”

香农当年创建信息论的时候是为了探讨信息的本质和通信的理论极限问题，比如什么是信息，怎样从数学上定义衡量信息，数据压缩和数据传输可达到的极限在哪里，等等。

但信息论的应用远不止于通信领域。在香农之后，信息论被当作一套通用的数学工具，在很多信息科学领域都有应用。

比如信息论可以用来做统计分析，可以用来开发人工智能，可以用来优化投资策略等。

先从一个貌似不相干的西方曾经流行的游戏“二十个问题”说起。游戏是这样的：俺心里想一样东西，你可以问俺二十个问题，然后猜俺心里想的东西。你的问题必须是“是不是”这种形式的。比如，这个东西是不是可以放进冰箱里？这个东西是不是活的？这个东西是不是能吃？诸如此类。对于你问的每一个问题，俺必须如实地回答“是”或者“不是”。你在二十个问题之内猜到了我想的东西就算赢。

这个游戏的关键是在于如何有效地问你的问题。如果你问“明天是不是下雨”，那你肯定脑子进水了，可以不用往下看了。如果你第一个问题问的是“这东西是不是 iPhone 6”，这样的问法显然也效率不高，因为俺一旦说“NO”，你只从大量的可能性中排除了一种可能，还是要面对剩下巨大的猜测空间。

这个游戏可以大致等价于这样一个数字游戏。假设M是个大于1的正整数，俺俩在玩游戏之前就商议确定好。俺在1到M之间任意想一个整数，你的任务是用最少的“是不是”形式的问题问出这个数是多少。

对于这个数字版的“二十个问题”游戏，聪明的宝宝都会发现类似这样的结论：M的数值越大，需要的问题越多。但爱钻研的同学可能会想到另一个问题：对于一个给定的问问题策略，所需问题的“多”或“少”又是用什么来衡量的呢？比方说，M=8，而你的问法是依次问如下问题：“这个数是不是1”，“这个数是不是2”，“这个数是不是3”，一直到“这个数是不是7”（如果问完“这个数是不是7”你觉得还需要问“这个数是不是8”的话，那请你去看韩剧吧）。在这种情况下，如果俺想的数字是1，你只需要一个问题就可以知道答案；而如果俺想的数字是8，你必须在问完7个问题之后才能知道答案。换句话说，即使问问题的策略确定，因为俺心里那个神秘数字的不确定性，你所需要的问题数目也是不确定的。因此我们需要把这个数字版“二十个问题”游戏更准确地描述出来，或者说，把在什么意义上“最少”定义出来。

让俺先喘口气，喝口水，扯点概率论，回头再看这个问题。

咱们也别讲究数学的严谨了吧，直接讲这个叫随机变量的东东。

随机变量描述的是一个随机实验可能出现的结果以及每种可能结果的可能性，也就是概率。先看一个例子。

例［老千掷硬币］：假设某老千每次投掷硬币的结果有1/3可能性出正面，2/3的可能性出反面。那么掷一次硬币就是一个随机实验，掷硬币的结果就是一个随机变量，我们这里记作大写的 X。如果把正面记作1，反面记作0，那么这个随机变量 X 可以通过一个函数来描述：函数的变量（小写的）x的取值范围是集合{0，1}，这个集合此后记作 S；函数在0和1的取值分别为：=1/3，=2/3。

从这个例子可以看出，一个随机变量 X 无非是通过在某个集合S上定义的一个函数来描述的，而这个函数不能取负值，而且必须在对其变量 x 求和的时候结果为1（在老千掷硬币的例子中即：+=1)。这个函数通常被称为随机变量X的概率分布。

当然，同样是掷硬币，可以定义出很多不同的随机变量（即不同的概率分布函数）来。普通人掷硬币对应的随机变量基本就是==1/2。赌神掷硬币对应的随机变量可能是=1， =0。

生活中的随机变量比比皆是。比如，在掷骰子的时候，骰子掷出的结果这个随机变量对应于一个定义在S={1，2，...，6}上的概率分布函数 ，通常认为==...==1/6。再比如明天会不会下雨（天气预报不准的啦），会有几个人给俺这篇吐血之作点赞或转发（不晓得多少人更喜欢韩剧的啦）这些不确定的事情里都可以定义出随机变量来。记得不知道哪一位伟人曾经说过，“随机变量是到处都有的。对于我们的脑袋，不是缺少随机变量，而是缺少发现。”

在前面说的那个数字版“二十个问题”游戏中，俺心里想的神秘数字对你来说也是一个随机变量，它的概率分布是定义在S={1，2，...，M}上的函数。如果我选数字是“完全随机的”，那么，这个函数就是==...==1/M。这种分布通常被称为均匀分布。当然，取决于俺按什么偏好选数字，这个函数也可以取其他形式：如果俺就是喜欢2，也许俺会以更高的概率取2。

假设有个随机变量 X，它的取值范围 S={1， 2，…， M}，它的概率分布函数是某个定义在S上的函数 。那么这个随机变量的均值（更文化点的说法叫数学期望值）就是这样一个东东：

1*+2*+3*+…+M*.

在上面老千掷硬币的例子中，随机变量 X 的均值就是 1*(1/3)+0*(2/3)=1/3。简单吧。

很多同学可能都有直觉的认识，能感觉到如果把产生这个随机变量 X 的随机实验做很多次，把得到的数字取平均，那么这个平均数差不多就是 X 的均值。这个概念，叫做大数定理，跟俺要讲的熵有着本质的联系，俺这里不敢唐突，稍后会带同学们仔细品味。

很多时候俺们关心的不止一个随机变量，而是很多随机变量。比如，俺们同时关心两个随机变量 X 和 Y，X 的取值范围是{1， 2}， Y 的取值范围是{1， 2， 3}。那么俺们可以把这两个随机变量看作一个随机变量对，写作（X， Y），而把它的取值范围理解为所有可能的（X，Y）取值的组合，也就是{(1， 1)，(1， 2)，(1， 3)，(2， 1)，(2， 2)，(2， 3)}。把这个集合叫作S，那么这对随机变量就是通过一个定义在S上的概率分布函数 来描述的。当这个随机变量对的分布满足 =的时候，俺们就称这两个随机变量是相互独立的。

= =(2/3)(2/3)=4/9

= =(2/3)(1/3)=2/9

= =(1/3)(2/3)=2/9

= =(1/3)(1/3)=1/9

独立随机变量的概念当然可以推广到更多的随机变量上。如果有 n 个随机变量，它们的取值无非就对应了一个长度为 n 的序列。所有这样序列的集合就是这组随机变量的取值范围。如果这些随机变量是相互独立的，那么每个序列出现的概率无非就是把这个序列中每个数出现的概率乘在一起。比如，上面的老千连续掷了10次硬币，那么出现1101011110的概率就是：

(1/3)(1/3)(2/3)(1/3)(2/3)(1/3)(1/3)(1/3)(1/3)(2/3)=(1/3)^7 *(2/3)^3.

哎，累死俺了，这个也要讲，学霸们可能要打瞌睡了。不好意思，俺怕讲得太快，有的同学要去看韩剧了。哎，致敬也是体力活啊！

大数定理的英文是，它的中文翻译通常是“大数定律”而不是大数定理。但俺却偏要叫它大数定理！

定律或是英文里的 law 都是指不需要证明但可以被验证的理论假设。比如牛顿的万有引力定律。从数学上说，不需要证明就被接受的假设被认为是公理。但是这个大数定理并非公理，它是被严格证明出来的（证明也不复杂，只要用马尔可夫不等式或切比晒夫不等式就行了），因此准确的数学语言应该叫它“定理”。管他叫“定律”会让人以为这个东东就是假设出来的公理，从而产生歧义，当年也不知道谁这么没涵养管它叫“law”。所以，不管你们服不服，俺都要管它叫大数定理。

大数定理大概说了这样一个意思。假设有某个随机实验会产生一个随机变量 X。如果你重复做这个随机实验 n 次，你就会得到一个随机变量序列 X1， X2， X3，…， Xn。这里假定这些随机变量相互独立（即这些随机实验互不影响）而且 n 是个很大的数（比如，一万，十万，百万），那么把这 n 个数加起来除以 n （即取平均），得到的数（即(X1+X2+…+Xn)/n ）几乎总是很接近随机变量 X 的均值。同学们注意一下俺这里“几乎总是”和“很接近”的用词哈。虽然俺是个马虎的人，这里的遣词造句是极其考究，极负责任，极具情怀的。

咱们用老千掷硬币的例子先看看大数定理到底说了些啥子嘛。假设那个老千掷了 n 次硬币，那么他就得到了 n 个在{0， 1}里取值的数。因为这 n 个数都是随机的，这 n 个数的均值当然也是个随机变量，就是说也有一个概率分布函数，有一定的不确定性。大数定理告诉俺们，当 n 很大的时候，这 n 个数的平均值“几乎总是很接近”1/3。“几乎总是”和“很接近”是可以在数学上严格定义的，不过当俺讲完它们的定义的时候，估保守，但俺码字已经快要吐血，正在后悔俺为什么要揽下这么个差事，所以就随便套了一下切比晒夫不等式得出下面这些“至少有”的结论）：

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

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

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

如果把“很接近1/3”理解为跟 1/3 相差不到 ，那么：

当 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}和概率分布函数 都已知。当然在实际情况下我们未必真知道 ，但往往可以大致估计这个函数。如果对这个分布函数我们一无所知，我们不妨认为 是个均匀分布。

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

=1， =2， =3， =4，

=5， =6， =7， =7。

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

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

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

*+*+…+*.

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

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

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

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

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

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