第四百七十四章 信源编码对应二十个问题（1/1）

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

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

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

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

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

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

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

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