2016年四月三十日是克劳德·艾尔伍德·香农（Claude Elwood Shannon）的一百周年诞辰。虽然香农被学术届尊为信息时代之父，听说过这位科学巨人名字的想必比知道宋仲基的人少得多。不过不管你们信不信，要是没有香农，到今天咱们应该还没有见过手机或Internet，也没有用过微信或Facebook，更不能在网上看韩剧。

香农是美国数学家、信息论的创始人。1948年，香农发表了《通信的数学理论》文章，提出了信息熵的概念，并创建了信息论。这篇文章奠定了香农“信息论之父”的地位。后来，香农在1949年继续发表了《噪声下的通信》。几十年来，人类科技在数字化、智能化、网络化等的推动下经历了一波又一波通信、信息革命。数十年之后，在信息流、物质流的社会中，香农的论著依然闪烁着智慧之光，并将照耀人类社会今后的数个世纪。

在学术圈子里，人们往往对香农高山仰止。南加州大学（University of Southern California)  电子工程系教授巴特·嗑死磕（Bart Kosko）说：爱因斯坦相对论之革命性在于它颠覆了之前的牛顿力学，而香农信息论之革命性在于它前无古人—— 香农对信息的认知开人类之先河，没有什么挡在前面需要被颠覆的；香农提出了全新的数学工具，就是所谓的信息论，并用这个工具回答了人类从未思考过的问题。在这个意义上，香农的发现像牛顿的引力定律一样基本。

 

克劳德·艾尔伍德·香农（Claude Elwood Shannon ），1916年4月30日—2001年2月26日。

1948年，香农（Claude Shannon）在贝尔实验室发表论文《通信的数学理论》。文章中提出的数学工具构成了信息论的骨架。香农证明了信源编码的极限是信源的熵，信道编码的极限则是信道容量。

倚天剑一出，天下皆惊。而为达到香农预测的信道编码的极限——信道容量，人类却花费了半个世纪挣扎。本篇文章试图用最少的数学科普一下信息论里最基础的概念——熵（entropy）。

◆ ◆ ◆

“二十个问题”游戏

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

 

这个二十个问题的游戏曾经很受欢迎，还被做成过电子玩具。

这个游戏的关键是在于如何有效地问你的问题。如果你问“明天是不是下雨”，那你肯定脑子进水了，可以不用往下看了。如果你第一个问题问的是“这东西是不是 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 可以通过一个函数P(x)来描述：函数的变量 （小写的）x 的取值范围是集合{0,1}，这个集合此后记作 S；函数在0和1的取值分别为：P(1)=1/3，P(0)=2/3。

 

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

 

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

 

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

 

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

 

◆ ◆ ◆

随机变量的均值

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

 

1*P(1)+2*P(2)+3*P(3)+ … +M*P(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上的概率分布函数 P(x, y) 来描述的。 当这个随机变量对的分布满足 P(x, y)=P(x)P(y) 的时候，俺们就称这两个随机变量是相互独立的。

 

P(0, 0) = P(0)P(0) = (2/3)(2/3)=4/9

P(0, 1) = P(0)P(1) = (2/3)(1/3)=2/9

P(1, 0) = P(1)P(0) = (1/3)(2/3)=2/9

P(1, 1) = P(1)P(1) = (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

 

◆ ◆ ◆

均值和大数定理

 

大数定理的英文是 the laws of large number, 它的中文翻译通常是“大数定律”而不是大数定理。

 

定律或是英文里的 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 相差不到 0.02，那么：

 

当 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(8)=7。

 

（对，L(8)=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= log 8. （本文中所有的对数操作均以2为底数）。

 

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

 

这个特例显然可以推广：如果神秘数字 X 的概率分布函数是在 2^K 种可能性上的均匀分布，那么“二十个问题”游戏的最优策略可以通过二分法实现；在这种策略下，不论神秘数字是什么，问出它所需要的问题数都是 K，因此所需要的平均问题数也是 K。

 

当然，这个二分法只适合于这样的特例，当神秘数字的可能性总数不是2的多少次方的时候，或者当神秘数字的分布不均匀的时候，这种问法显然不是最优的。这个问题任意形式的最优解法曾让一个叫大卫.霍夫曼（David Huffman）的年轻学生在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 个数的时候，就让你开始问问题。前面说过，这无非就是把这个老千掷硬币的结果当作一个信息源，对这个信息源做压缩。

 

因为 n 很大很大，让我们先回顾一下大数定理的情怀：

 

老千掷出的硬币序列的平均值几乎总是很接近1/3。

 

根据俺之前对这句话不辞劳苦的解释，这句话也可以换一种说法，而且这种说法很重要（重要的事情说三遍！）

 

老千掷出的序列几乎可以肯定有差不多 n/3 个1 和 2n/3 个0！

老千掷出的序列几乎可以肯定有差不多 n/3 个1 和 2n/3 个0！

老千掷出的序列几乎可以肯定有差不多 n/3 个1 和 2n/3 个0！

这个重要结论很容易推广到掷硬币之外的任意随机变量：假设随机变量 X 是通过一个在集合 S={1, 2, …, M} 上定义的概率分布函数 P(x) 描述的。那么当俺们产生 n 个相互独立的这样的随机变量的时候，如果 n 是个很大的数字而 a 是 S 中的任意一个数，那么：

 

产生的随机序列几乎可以肯定有差不多 n*P(a) 个 a ！

产生的随机序列几乎可以肯定有差不多 n*P(a) 个 a ！

产生的随机序列几乎可以肯定有差不多 n*P(a) 个 a ！

 

也就是说，虽然得到的序列本身是随机的，不确定的，但是当 n 很大的时候，这个序列的组成“几乎”是“差不多确定的”！ 而且可以想象，当 n 无穷大的时候，这里的“几乎”和“差不多”都可以删去！

 

在老千掷硬币这个例子里，如果一个硬币的序列有差不多 n/3 个1 和 2n/3 个0，那么俺就管这种序列叫“典型序列”。在更普遍的意义上，相对于一个在S 上定义的分布 P(x)，一个由 S 里的数字组成的长度为 n 的序列俺也管它叫典型序列，如果 S 里的每个数 a 在这个序列中出现了差不多 n*P(a) 次。在典型序列定义中的“差不多”是差多少？呵呵，跟前面的逻辑一样，如果 n 很大，差不多就是差一丁点，如果 n无穷大，差不多可以是“一点不差”！ 

 

那么上面重要的说了三遍的话用这个语言重新说，就是：

 

老千掷出的序列几乎可以肯定是典型的！

老千掷出的序列几乎可以肯定是典型的！

老千掷出的序列几乎可以肯定是典型的！

 

当 n 无穷大的时候，这句话里的“几乎”当然也是可以删掉的。也就是说，在 n 无穷大的时候，不典型的序列根本不会出现！那么，你问问题的时候岂不是只需要针对典型序列问问题就行了？

正是如此！

  

那咱们看看典型序列一共有多少个。把这个要算的数记作 T。

 

首先注意一下每个典型序列有多大的概率被老千掷出来。因为每个典型序列“差不多”由 n/3 个1 和 2n/3 个0 组成，而这个序列中的所有随机变量又是相互独立的，那么，每个典型序列被掷出来的概率“差不多”就是 (1/3)^(n/3)*(2/3)^(2n/3)。不知道同学们注意到没有，每个典型序列被掷出来的概率“差不多”都是这个数。同时注意到只有典型序列才可能被掷出来，也就是说，所有典型序列出现的概率之和“差不多”就是 1。这样俺们就可以得出，典型序列的数目 T “差不多”就是 1 除以每个典型序列出现的概率，也就是

 

1/((1/3)^(n/3)*(2/3)^(2n/3)) = (1/3)^(-n/3)*(2/3)(-2n/3).

 

针对这 T 个序列问问题，就“差不多”等同于俺跟你玩一次这样的“二十个问题”游戏：俺从{1, 2, …, T} 里取一个数，而且这个数服从均匀分布；然后你问俺“是不是”问题来猜这个数。那么你最少需要多少问题呢？ 现在回头找到之前让你们用红笔圈出的结论：最优解是二分法；你最少需要的问题总数是 log T！而且不管俺取的是哪个数，你都需要这么多问题！

 

认真的同学可能会叫板说，哎，这个 T 也未必是 2 的整数次方啊，二分法能用吗？！嗯，这个问题不错。但可以这样想，只要把 n 弄得足够大，总可以让 T 非常接近 2 的某个整数次方。而且，即使 T 真的不是 2 的整数次方，还可以换一个角度得到我们后面要得到的结论，比如，一定存在一个整数K 使得 T 是在 2^K 和 2^(K+1) 之间。。。。总之，当 n 无穷大的时候，凌乱的世界都变整齐了，这个问题不再是问题了。

  

这个最少问题数 log T 是用来问这个长度为 n 的硬币序列的。平均到每次掷硬币，平均需要的最少问题数就是 （log T）／n。稍微整理一下这个表达式就应该可以看到，这个数字正好等于

 

- (1/3) log(1/3)- (2/3) log (2/3)。

 

这也就是压缩这个“老千掷硬币”信息源所需要的最少比特数。

 

把这种推演用到任意信息源。如果一个信息源往外蹦的随机变量都独立而且服从同一个定义在S={1, 2, …, M} 上的分布P(x)，那么以下结论依次成立。

 

信息源里蹦出的随机序列几乎可以肯定是典型的！

 

每个典型序列出现的概率差不多就是 P(1)^(nP(1))*P(2)^(nP(2))*…*P(M)^(nP(M))!

 

典型序列的个数 T 差不多就是P(1)^(-nP(1))*P(2)^(-nP(2))*…*P(M)^(-nP(M))!

 

压缩这个信息源蹦出的每个随机变量平均所需要的最少比特数就是 (logT)/n！

 

这个数字 (logT)/n 就等于：

 

-P(1)log P(1) - P(2) log P(2) - … - P(M)log P(M).

 

这个数字，就是熵。

 

◆ ◆ ◆

熵的物理意义

从熵的表达式看，熵是通过一个概率分布函数 P(x) 来定义的。因为概率分布函数 P(x) 都对应于它所描写的随机变量 X，所以俺们也可以认为熵是对随机变量 X 的某种特性的度量，而把它记作 H(X)。从压缩的角度讲，熵值 H(X) 是对产生随机变量 X 的信息源编码所需要的平均最小比特数，或随机变量 X 中固有的平均信息量。

 

如果随机变量 X 是在 S={1, 2, …, M} 里取值，那么可以证明，熵值 H(X) 的取值必定在 0 和 logM 之间。当随机变量 X 在 S 上均匀分布的时候，H(X) 取最大值 logM；当 X 以百分之百的概率取 S 中的某个数值的时候，H(X) 取最小值 0。前者对应于“不确定性”最大的 X，而后者对应于“不确定性”最小的（即完全可以确定的）X。所以，也可以把熵值 H(X) 理解为对 随机变量 X 的“不确定性“（或“不可预测性”）的度量。

 

因此，随机变量所包含的“信息量”和它的“不确定性”其实是同一个概念。一个随机变量越难以确定，它所包含的信息量越多。这种认识对初次接触熵的人来说或许不够自然。但仔细体会一下，确实是有道理的。如果俺想告诉你的事你很容易猜到，或者说你不用问几个问题就能知道，那俺要说的话对你来说就没多少信息量。

 

在熵的定义里 －logP(a) 又是什么物理意义呢？当然这个数字可以理解为 a 编码所需要的比特数（在前面例子里，我们能看到以1/8概率出现的事件，需要用3个比特来编码）。换一个角度理解，－logP(a) 可以理解为 a 的“惊奇度”。一个出现概率极低的事件 a，比如世界末日，它一旦出现就会令人非常惊奇，所以对应的 －logP(a) 就会很大；而如果 a 出现的概率很大，它的出现就不会太令人吃惊，所以对应的 －logP(a) 就会很小。因此，熵值 H(X) 也可以理解为随机变量 X 的“平均惊奇度”。

 

用不确定性，信息量，或平均惊奇度来理解熵，都只是给它赋予一个直觉的解释。平均最小编码长度才是对熵的数学理解。但这种理解并不能体现出大数定理在熵的定义里所起的决定性作用以及“二十个问题”游戏必须攒着玩才能实现最短问题数等于熵值的深刻认识。在大数定理的情怀下，熵值 H(X)还有另一个数学解释： H(X) 是典型序列的总数随序列长度的“翻倍速率”。看，长度为 n 的典型序列总数 T 差不多是 2^(nH(X))；也就是说，每当序列长度 n 增加 1， T 就增大 2^(H(X)) 倍，或者说，翻倍翻了 H(X) 次。所以把熵理解为典型序列总数的翻倍速率才能真正体现熵的数学本质。

 

◆ ◆ ◆

香农和熵

熵，或英文里的entropy，本来源于物理中的热力学，用来描写系统的“混乱度”。香农在定义信息熵的时候借用了这个词。虽然俺经常夜观星象，也能在夜空没有雾霾的时候认出北斗星，但对宇宙、相对论，或是热力学，都一窍不通。所以俺就不试图解释物理熵和信息熵的联系了。

 

但在通信的范畴，熵是人类第一次对信息有了数学的认识。人类刚刚开始研究数字通信的时候基本就是瞎子摸象，直到1948年香农在贝尔实验室发表了那篇著名的文章，“通信的数学理论”。倚天剑一出，天下皆惊。香农一针见血地指出，通信的问题可以分解成两个的问题，即信原编码和信道编码。信原编码的目的是尽可能高效的表示信息源，即数据压缩；信道编码的目的则是尽可能高效的让数据可靠无误地通过信道。在他1948年的文章里，香农证明了信原编码的极限是信源的熵，而信道编码的极限则是个叫信道容量的东东，标注着信道可以支持的最大通信速率。（信道容量的概念是在熵的基础上的对信息论的进一步发展，故事更长，更精彩，不过俺还是不讲了吧。）香农说，只有当信源的熵低于信道的容量的时候，可靠的通信才可能实现；而且只要在这个条件下，可靠的通信就一定可以实现！香农的证明是存在性证明，就是说，他告诉俺们： 反正这事儿一定可以实现，至于怎么实现，你们自己想办法吧。

 

信源编码的问题很快被香农的追随者和逐步解决。基于算术编码(arithmetic coding)和 LZ 编码（Lampel-Ziv coding) 的信源编码方法在上世纪七八十年代已经日渐成熟，实现了香农预测的压缩极限并在实践中被广泛采纳。而香农预测的信道编码的极限，信道容量，却花费了人类半个世纪挣扎。业外人士未必了解，对信道编码的研究结晶了人类最高的智慧和前赴后继的努力。然而香农预测的信道容量直到上世纪九十年代中叶才终于被实现。今天我们的手机里也终于承载了香农在1948年的预言！

 

熵的提出是信息论起点，也是人类对信息认知的开始，而香农在他1948年文章里提出的数学工具正是信息论的骨架。在我们今天生活的信息时代，香农和信息论存在于我们的手机，我们的电脑，我们的电视，我们的蓝光播放器，我们的internet，我们的facebook，我们的韩剧 ……

 

圣经创世纪说，在世界还是一片混沌漆黑的时候，上帝说，要有光。于是世界就有了光。

 

大约七十年前，当人们还在黑暗中摸索数字通信的时候，香农说，要有熵。于是，就开启了信息时代。

◆ ◆ ◆

“香农的现代信息论永不过时”

是否有人曾质疑过，随着科技的不断发展，香农的信息论有可能无法满足现实的要求？答案是否定的。根源上讲，信息流、物质流组成了世界。只要世界的根源还是信息与物质，香农揭示的依旧是一个公理。即便发展到人工智能的今天，信息依然是一切的基础。业界来说，《通信的数学理论》是一篇20世纪少有的、对人类发展产生深远影响的科学论著，可与牛顿力学相媲美。即便百年之后，我们依旧享用着这个理论来探索未知的世界。

基于香农信息论绵延至今的技术成果:

奠定现代加密的理论基础

20世纪60年代末开始了通信与计算机相结合，通信网迅速发展，人类开始向信息化社会迈进。这就要求信息作业的标准化，加密算法当然也不能例外。标准化对于技术发展、降低成本、推广使用有重要意义。

我们都知道，美国FBI提出的数据加密标准DES，以及最新图灵奖得主斯坦福大学密码学和网络安全技术专家惠特菲尔德·迪菲（Whitfield Diffie）和马丁·赫尔曼（Martin Hellman）提出的公钥加密系统是现代密码学的标志，是现代通信的基础加密技术。不过，你也许不知道，这两种标准或体制都以香农的信息论为基本知道思想。 

1949年，香农公开发表《保密系统的通信理论》一文，开辟了用信息论来研究密码学的新思路。这篇文章基于的理论是香农在1945年为贝尔实验室所完成的一篇报告《A Mathematical Theory of Cryptography》。论文发表后，香农被美国政府聘为政府密码事务顾问。

DES

DES全称为Data Encryption Standard，即数据加密标准，是一种使用密钥加密的算法。DES设计中使用的两个分组密码设计原则：混淆（confusion）和扩散(diffusion)，其目的是抗击敌手对密码系统的统计分析。这就很好地提现了香农1949年的论文中所提出的设计强密码思想：

组合（Combine）概念：由简单易于实现的密码系统进行组合，构造较复杂的、密钥量较大的密码系统。Shannon曾给出两种组合方式，即加权和法和乘积法。

扩散（Diffusion）概念：将每一位明文及密钥尽可能迅速地散布到较多位密文数字中去，以便隐蔽明文的统计特性。

混淆（Confusion）概念：使明文和密文、密钥和密文之间的统计相关性极小化，使统计分析更为困难。

信息论是研究和评估保密和认证系统的安全的重要工具，同时熵和信息量也是研究和评估隐匿系统重要工具。

Shannon曾用揉面团来形象地比喻“扩散”和“混淆”的作用，密码算法设计中要巧妙地运用这两个概念。与揉面团不同的是，首先密码变换必须是可逆的，但并非任何“混淆”都是可逆的；二是密码变换和逆变换应当简单易于实现。分组密码的多次迭代就是一种前述的“乘积”组合，它有助于快速实现“扩散”和“混淆”。

可以说，分组密码设计中将输入分段处理、非线性变换，加上左、右交换和在密钥控制下的多次迭代，都在香农构造密码的思想下指导进行。

公钥加密系统

香农在1949年指出：

“好密码的设计问题，本质上是寻求一个困难问题的解，相对于某种其它条件，我们可以构造密码，使其在过程中的某点上等价于解某个已知数学难题。”

在此影响下，迪菲和赫尔曼提出了公钥加密系统。

迪菲和赫尔曼提出的公钥加密系统，其中的RSA、Rabin、背包、ElGamal、ECC、NTRU、多变量公钥等所有公钥算法都是基于某个数学问题求解的困难性。

迪菲和赫尔曼的可证明安全理论就是在于证明是否可以将所设计的密码算法归约为求解某个已知数学难题。

破译密码的困难性，所需的工作量，即时间复杂性和空间复杂性，与数学问题求解的困难性密切相关。计算机科学的一个新分支——计算复杂性理论与密码需的研究密切关联起来了。

扩频通信与调制解调

网络化社会的今天，我们必定离不开电子计算机和通信。下面我们用通俗易懂的方式来讲一下，我们今天孜孜以求的带宽、WiFi、蓝牙、GPS等与香农的关系吧：

根据香农（C.E.Shannon）在信息论研究中总结出的信道容量公式，即香农公式：

C=W×Log2（1+S/N）

式中：C——信息的传输速率，S——有用信号功率，W——频带宽度，N——噪声功率，也就是说：

为了提高信息的传输速率C，可以从两种途径实现，既加大带宽W或提高信噪比S/N。换句话说，当信号的传输速率C一定时，信号带宽W和信噪比S/N是可以互换的，即增加信号带宽可以降低对信噪比的要求，当带宽增加到一定程度，允许信噪比进一步降低，有用信号功率接近噪声功率甚至淹没在噪声之下也是可能的。扩频通信就是用宽带传输技术来换取信噪比上的好处。

扩频的出发点是加密，后来主要是用来减低干扰，同样是香农公式里面提到的另一个因子信噪比，也可以得到高带宽。简单来说，所谓降噪就是，带宽越宽，抗干扰能力越强。但是，带宽扩展上去了，信号功率就降低了，不符合市场经济。所以现代通信不是要无限扩大带宽，而是要找平衡点。基于这个思想，我们还在寻找这个平衡点。

信息论与机器学习

如果前面说的还是过去和当下的影响，那么接下来就不得不佩服香农的未来预示能力了。

香农是最早提出信息智能化的学者之一。信息论与人工智能之机器学习同为涉及计算机科学和应用数学等学科的分支领域，这两门交叉学科在起源和应用上有很多相似之处。不过，看起来神乎其神的机器学习，主要还是借用信息论的方法以此拓展理论研究和应用场景，比如关于分类计算上，借鉴于信息理论来创造和改进学习算法。

信息论中的一些度量也可以作为学习算法的度量。“学习就是一个熵减的过程”，学习的过程也就是使信息的干扰度下降的过程。比起传统的经验公式为基础的机器学习，以信息理论为基础的机器学习也拥有无可比拟的优势。

好吧来个具体一点的例子。上个月人机大战中的AlphaGo，其决策树算法是战胜人类的重要武器。那么，据来自于NSF博士论文《 Information Theory and its Relation to Machine Learning》所阐述，以互信息作为学习准则，例如以应用信息增益（归一化的互信息）构造最简结构决策树就是其中一种应用。这种基于信息理论为学习准则的原理就是将无序数据转变为有序数据，以信息熵差值作为测量尺度来评价转换效果。

如今也有不少研究者猜想，在机器学习中，所有学习目标的计算表征都是可以用熵函数的优化来描述或者解释的。这个猜想给了机器学习界一个很好的研究着力方向。

原文发布时间为：2016-05-01

本文来自云栖社区合作伙伴“大数据文摘”，了解相关信息可以关注“BigDataDigest”微信公众号