香农说，要有熵。于是开启了信息时代。（3）
“二十个问题”游戏的准确规则及特例
用概率论武装一下之后，同学们应该已经认识到，在“二十个问题”游戏中俺心里想的神秘数字其实就是一个随机变量 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年一夜成名。不过，那已经是在香农提出信息论三年之后了。
在香农独特的视角里，这个问题并不至关重要。在俺的想象中，当香农看到满屋子小朋友们叽叽喳喳地玩这个游戏的时候，他笑了笑，说：你们慢慢玩吧。然后他点起一支烟，凝视着窗外的远方。在落霞与孤鹜齐飞的秋色里，他看到了这个游戏的另一种设计。
（待续）
OTTAWAZINE特约撰稿人：学霸老张