信息论与老鼠毒药问题、称球问题

作者: 古剑诛仙 | 来源:发表于2019-06-15 02:30 被阅读0次

主要内容来摘选自以下两篇文章
http://blog.sciencenet.cn/blog-677221-669159.html
https://wenku.baidu.com/view/399f82f2f61fb7360b4c6565.html

有100只一模一样的瓶子，编号1-100。其中99瓶是水，一瓶是看起来像水的毒药。只要老鼠喝下一小口毒药，一天后则死亡。现在，你有7只老鼠和一天的时间，如何检验出哪个号码瓶子里是毒药？

这儿把它叫做‘问题1’，解决此题的方法可谓二进制应用的经典：

首先，将瓶子的10进制编号数改成7位的2进制码。然后，让第1只老鼠喝所有2进制码第1位是1的瓶子中的水；让第2只老鼠喝所有2进制码第2位是1的瓶子中的水；以此类推下去。这样，每个老鼠第二天的死活情况就决定了毒水瓶子二进制码这一位的数字：老鼠死，对应1，反之为0。换言之，将7只老鼠死活情况排成一排。比如说结果是“死活死死活活死”的话，毒水瓶子的二进制标签就是：1011001，转换成10进制，得到89。

这道题可以有很多种在各个参数方向的扩张和一般化。最“通-通-通-通”的解够你研究好一阵子。比如，如果我们把题目稍加变化（问题2）：

有100只一模一样的瓶子，编号1-100。其中99瓶是水，一瓶是看起来像水的毒药。只要老鼠喝下一小口毒药，一天后则死亡。现在，给你2天的时间，请你告诉我，你至少需要多少只老鼠，才能检验出哪个号码瓶子里是毒药？

比较原来的题目，这个题目有两个变化：一是给你的时间多了一天。因为老鼠喝毒药1天之后死去，2天意味着你可以做两次实验，这给了你一个时间方向（实验次数）的空间，有可能让你用更少数目的老鼠，达到同样的目的。

第二个改变是提问的方式。这次的问题是：你‘至少’需要多少只老鼠？回答这类问题，是只要估计一个下限，对你来说，做实验的小白鼠多多益善，但你的老板要花钱买它们，他得考虑经济效益。当你还没有完全把方案想清楚之前，你好歹给老板一个交代呀。这种时候，信息论能派得上一点用场。

刚才我说‘信息论’，实际上，我们完全用不上什么信息论的任何高深理论，用的只不过是由香农定义的计算信息量的一个公式而已。牛刀杀鸡虽然太大，但用它锋利的小尖给开个小口也未尝不可。

不仅仅是这道题，还有几星期前科学网讨论热烈的“称球问题”，都是能用此‘牛刀’而有所受益的。实际上，我认为，许多问题的解决，都能和这‘牛刀’沾上边。如果从‘信息’的角度来分析某些问题，可以使你更登高望远，对问题能有更深层的理解，更容易融合各学科的间隙，达到借他山之石而攻玉的效果。

科学（不仅限于数学）上的大多数研究，说穿了就是一个处理‘信息’的过程。摈弃无用的信息，想办法得到有用而正确的信息，用以消除原来课题中的不确定性，得到更为确定的科学规律。

得到信息量的公式：

H=∑-pi log pi

如果计算中的对数log是以2为底的，那么计算出来的信息就以比特（bit）为单位。

根据香农的信息概念，信息能消除不确定性，而我们在解决数学题的时候，也是要消除不确定性，得到确定的答案。并不仅仅是老鼠问题和称球问题如此，我认为大多数问题都多少是一个‘消除不确定性’的过程。因此，我们为何不借用香农的工具，研究研究我们的问题有多少不确定性呢？也就是说，需要多少信息量才能解决这个问题？另外，根据题目所限制的手段，最多能够得到多少信息量？有无可能完全解决这个问题？等等。

具体到老鼠和毒药的问题。100瓶液体中1瓶有毒，每1瓶发生有毒的概率是1/100，这时候要确定毒药瓶所需的信息量H = -(p1logp1+p2logp2+….+p100logp100)。

因为所有瓶子完全相同，这是一个等概率问题，p1 = p2 =…=p100 = 1/100。

得到H=-log（1/100）。

下面计算从老鼠能得到的信息量。

首先考虑问题1，即给定时间为1天的情况。一天后，每只老鼠或死或活，因此，能够提供1比特的信息。7只老鼠则能提供7比特的信息。

再看看刚才列出的确定毒药瓶所需的信息量H的公式：H=-log（1/100）< -log（1/128）= 7比特。

因此，问题1应该可以解决。这个可能性是信息论提供给我们的。实际上，应该不仅仅是可能性，这种计算信息量比特数的方法能启发我们的思维。在解题时，学习别人解题的方法固然重要，而探讨别人是如何想到这种方法的，可能更为重要。在《大将军数学题2》的讨论中，就有博友说，如果提到2进制，此题就容易了。的确如此，如果不想到2进制，对此题往往好像有点束手无策，不知如何下手。

我们再来讨论问题2。

所需要的信息量H的计算是和问题1一样的。然而，从每只老鼠能得到的信息量的计算，却可能会有所不同。这儿我用了‘可能’两个字，是因为我们还丝毫未曾谈及如何解决这个问题2。

问题2和问题1的差别是在于老鼠可以参加接连两次实验。问题1中，只能做一次实验时，老鼠有两种状态：死或活。因此它可利用的信息量是1比特。如果能做两次实验，两次实验中都有生死的可能性，仅就逻辑而言，老鼠有四种可能情况：生生、生死、死生、死死。但其中的第三种情形：死生，是不可能发生的，因为在第一天的实验中死了的老鼠，不可能在第二次实验后又活过来。所以我们要将第一天实验中死了的老鼠，排除在第二次实验之外。所以，对问题2，老鼠有3种状态，每种状态的概率为1/3，因此，从一只老鼠得到的信息量

S=-（1/3log（1/3）+ 1/3log（1/3）+ 1/3log（1/3））= log（3）。

如果将这儿的对数取以3为底的话，可以说成，每只老鼠能得到的信息量是一个3进制位（trit）。

多少只老鼠才能使总信息量大于log（100）呢？

解方程：klog(3)>log(100) => 3*k>100，可得到k>=5。

因此，至少要5只老鼠，这便是问题2的解。

问题2直接所问的问题已经有了答案：实验至少需要用5只老鼠。况且，理论上来说，从5只老鼠能提供的最大信息量，转换到可能检验的最多瓶子数：3**5 = 243，已经大大地超过了100，余量很多，将这个数目提供给老板，问题不大。

但是无论如何，5只老鼠到底能否判定出有毒的瓶子，还需我们想出具体检验的方案才成定论。

因此，我们继续思考问题3（问题2的延伸）：在能做两次实验的条件下，如何找出有毒的瓶子？

沿着刚才信息量计算的思路，问题1最优答案用2进制有关的实验方法得到；问题2中估计老鼠数目的下界时，用到了3进制。那么，在能做两次实验的条件下，找出有毒的瓶子的最佳方案是否与3进制有关？

试试看吧。首先，将瓶子的号码转换成5位的3进制。为什么是5？5只老鼠？对，由于同样的原因，最大的号码100需要用‘5位的3进制’来表示。这100个5位3进制码列表如下：

00000，

00001，

00002，

00010，

00011，

00012，

00020，

00021，

00022，

…………

10201

然后，第一次实验：

从左到右：让第****1只老鼠喝所有3进制码第1位是2的瓶子中的水；让第2只老鼠喝所有3进制码第2位是2的瓶子中的水；以此类推下去。这样，每个老鼠第二天的死活情况就决定了毒水瓶子3进制码这一位的数字是不是2：老鼠死，2；老鼠活，1或0。

第一次实验中死去的老鼠没有白死，它的死决定了毒水瓶3进制码的这位数字是2！虽然这个老鼠为2而牺牲了，但很幸运，这一位的数字也被决定了，我们也不再需要这只老鼠。嘿嘿，我们让这个老鼠作出了它的最大贡献，要不然，就不是最优化的方案了。

第一次实验中没死的老鼠也没有白白地冒险，也为我们提供了信息：毒水瓶子3进制码的这一位的数字肯定不是2！所以，我们可以将3进制码这位是2的瓶子去除，因为它们肯定无毒。然后……

第二次实验：

让没死的老鼠喝下所有****3进制码的该位数字为1的瓶子中的水。这个老鼠一天后的死活情况便决定了毒水瓶子3进制码这一位的数字是1还是0：老鼠死，1；老鼠活，0。

这个问题可以此类推地扩展成更一般的问题：假设有n个瓶子，其中1个瓶子中的水有毒，实验的小白鼠喝了毒水1天后死去，给你i天的时间，k只老鼠。问n的最大值是多少？如何实验，才能检测出毒水瓶来。

答案：有i天的时间，你可以做i次试验，因为死了的老鼠不能继续试验，i次试验后，老鼠总共的可能状态有（i+1）个：

第1次就死去、第2次死、第3次死、……、第i次死、一直活着。

能检测的最多水瓶数n=(i+1)**k。检测方法：将所有瓶子用k位的(i+1)进制数编码，然后，遵循上面所述i=2类似的过程，i天之后，根据k个老鼠的状态，可以确定毒水瓶的(i+1)进制数值。

通过用信息论解老鼠喝毒药的这个简单练脑题，说明科学思维方法之重要性。

作为信息论应用于数学题的另一个例子，再来分析“称球”问题。

称球问题是说，用天平称k次，在n个球中找出唯一的一个重量不标准的次品球来，n最大是多少？如何找？有关这个次品球的说法，通常有3种变形：

已知次品球是更轻（或更重）；
不知次品球的轻重，找出它并确定轻重；

3、不知次品球的轻重。

利用信息熵的概念，可计算出这3种情形下n的最大值，并且帮助思考构成算法的过程：

已知次品球是更轻（或更重），这时n的最大值 = 3**k；
不知次品球的轻重，找出它并确定轻重，这时n的最大值 = （3**k-3）/2；

3、不知次品球的轻重，这时n的最大值 = （3**k-1）/2。

下面首先分析第1种问题。为解释起来更为直观，设定k=3。换言之，我们的问题是：如何用天平称3次，从27个球中找出唯一的那个稍轻的球？

27个球中只有1个球稍轻，可能发生的情形为27种，每个球为次品的概率是1/27。类似于上面所说老鼠试药的问题，要确定是‘哪一只’老鼠，所需的总信息量=log27。

在此题中的判定手段，限制了是天平。那么，天平每称一次，最多可以提供多少信息量呢？或者是说，可以为解题消除多少不确定性？

天平称一次后，有3种结果：左轻右重（A）、左重右轻（B）、平衡（C）。因此，称一次所消除的不确定性=log3。接连称3次后，所消除的不确定性=3*log3= log27。

根据刚才的分析，这个问题中，判定轻球所需的信息量与天平称3次能获得的信息量刚好相等。因此，用最佳的操作方法，有可能解决这个问题。

既然从信息论作出的估算给了我们解决问题的希望，我们就试试看吧。

天平似乎与3进制有关，我们便首先优选3进制。将27个球贴上3进制码的标签：

000、001、002、010、011、012、020、021、022、

100、101、102、110、111、112、120、121、122、

200、201、202、210、211、212、220、221、222。

将3进制码中，第1位（左）为0的9个球放天平左边，第1位为1的9个球放天平右边，称1次。如果天平平衡，则次品球3进制码第1位是2；左轻右重，第1位是0；左重右轻，第1位是1。总而言之，称这一次，确定了次品球3进制码第1位的数字。

接下去，继续称，逐次确定次品球3进制码各位的数字，问题解决了。这个第1类问题不难推广到任意k的情形。

下面再分析第2类称球问题：次品球不知轻重，最后需确定轻重的情况，具体来说就是，天平称3次，要找出12个球中那个唯一的又‘不知轻重’的次品球。

将两个问题对比一下，共同之处是都用天平，因此，天平称3次能提供的最大信息量仍然是log27。不同之处是如何计算找出次品球所需要的信息量。

因为现在要找出的次品球‘不知轻重’，因此，对每个球来说，不确定性增多了，这也是能判定的球的数目大大减少了（从27变到12）的原因。

现在，考虑这12个球，其中一个是或轻或重的次品的各种可能性。如果这个球是‘轻’的次品，记为-，‘重’的次品，记为+，因此，可能的次品分布情况：

1+、1-、2+、2-、……、12+、12-。

共24种情形，所需要的信息量则为log24。这个值小于天平称3次所能提供的最大值，所以，可能有解，那我们就试试看吧。有人说，你用什么信息论扯了半天，最后还是要一个一个地列举，那你这信息论不是多余的吗？科学定律是客观的，但各人的观点却是见仁见智的，我不需要去强人所难，也并非想比较解称球问题各种方法孰好孰坏，孰优孰劣，只是想将信息论用于分析此题，如此而已。

将12个球作如下编码：

（000+，000-）、（001+，001-）、（010+，010-）、（011+，011-）、

（100+，100-）、（101+，101-）、（110+，110-）、（111+，111-）、

（200+，200-）、（201+，201-）、（210+，210-）、（211+，211-）、

这儿，除了抽取了部分3进制的编码之外，还对每个球都给贴上了（+、-）两个标签，以表明此球‘或轻或重’而成为次品的两种可能性，也可等效于另一层编码。

然后，将第1位为0的4个球（第1行）放天平左边，第1位为1的4个球（第2行）放天平右边，称第1次。

1 如果天平左轻右重，这也许是第1行中的某个球轻了、或是第2行中某球重了而造成的：

000-、001-、010-、011-、100+、101+、110+、111+。

2 反之，如果天平左重右轻，也许是第1行中的某个球重、或是第2行中某球轻而造成的：

000+、001+、010+、011+、100-、101-、110-、111-。

3 如果天平平衡，则次品球在第3行的‘毫不知轻重’的4个球（200、201、210、211）中。虽然是4个球，仍然有8种可能性：

200+、200-、201+、201-、210+、210-、211+、211-。

前面两种情形类似，都是将次品球限制到了 ‘半知轻重’的8个球中。所谓半知轻重，是因为该球有一个已经确定的附加标签（+或-）。

比如说，编码为（000-）的球是个‘半知轻重’的球，而编码为（000）的球是个‘毫不知轻重’的球。对（000-）来说，尽管尚未确定此球是否是次品，但有一点是明确的：如果它是次品的话，它只能是更轻的次品。而球（000）则有‘轻重’两种次品的可能性。

因此，‘半知轻重’球比‘毫不知轻重’球少了一半的不确定性。判定所需的信息量也成为一半。

天平不平衡的情形，问题成为，“称2次从这4个半知的‘轻球’，及4个半知的‘重球’中找出次品球”的问题。

为此，取2个轻球加1个重球放天平的一边，另2个轻球加1个重球放天平的另一边。称第2次之后便将问题归为称1次从3个半知轻重球中找出次品的问题。

这个问题在David J.C. MacKay信息论的书中有叙述，借他的图表贴在下面。其中称球的过程看得很清楚，所以不再赘述。

指出一点：在天平平衡的情形，称第2次时，需要用到称第1次后确定的标准球，即天平上的8个球。标准球是能够提供信息的，每个标准球在每次称量中最多能提供1比特的信息。

image

下面再对第3类称球问题稍加分析，就是，天平称3次，要找出13个球中那个唯一的又‘不知轻重’的次品球的问题。

类似于第2类问题，将13个球作如下编码：

（000+，000-）、（001+，001-）、（010+，010-）、（011+，011-）、

（100+，100-）、（101+，101-）、（110+，110-）、（111+，111-）、

（200+，200-）、（201+，201-）、（210+，210-）、（211+，211-）、（222+，222-）、

与第2类问题不同的是天平平衡的情况。这时需要从5个球，10种状态中找出次品：

（200+，200-）、（201+，201-）、（210+，210-）、（211+，211-）、（222+，222-）

将5球中的3个放在天平一边，3个标准球放另一边。天平不平衡情形的最后一次称法与第2类问题同，不同的又是天平平衡时的情形。

天平平衡的情形，留下了2个不知轻重的球。因为我们有标准球可用，取2个待定球中的任何一个与标准球比较，如果不平衡，此球则为次品，并知其轻重；如果平衡，另1球为次品，但不能判定其轻重。

读者可能注意到了，在上面两个用信息熵方法解数学题的例子中，我们经常说：“使用最佳方案”，只有使用最优化的操作方法，才能达到信息论所预期的上限。这儿所说的最佳方案，与信息论中的“最大信息熵原理”有关。

什么是最大信息熵原理？它来自于热力学及统计物理中的熵增加原理。要讲清楚这个问题需要太多篇幅，在此只简单地科普一下。

用通俗的话来说，最大信息熵原理就是当你对一个随机过程不够了解时，你对概率分布的猜测要使得信息熵最大。熵最大就是事物可能的状态数最多，复杂程度最大。换句话说，对随机事件的预测要在满足全部约束条件下，保留各种可能性。

比如，你的女朋友叫你猜猜她的生日是哪一个月？如果你曾经看过她出生不久的照片，是秋天，那你可以猜测她生日是夏季的几率比较大；如果你对此完全没有概念，你就最好是对一年中的每一个月都一视同仁，给予相同的可能性。

另一个例子是买股票投资的时候，专家会建议你买各种类型的不同股票。

“不要把鸡蛋放在一个篮子里！”投资专家说。这句话的意思，其实就是警告你要遵循最大熵原理，对难以预测的股票市场，最好的策略是尽可能多地保留各种可能性，才能降低预测的风险。

在本文中所举的老鼠毒药问题中，尽量让每个老鼠试喝相等数目瓶子的水；在称球问题中，尽可能使天平‘左、右、下’的球的数目相等，这都是考虑最大信息熵原理而选择的最优策略。

参考资料：

David J.C. MacKay book：“Information Theory, Inference, and Learning Algorithms”
12个乒乓球，有一个和其他的质量不同（不知轻重），如何用天平称三次称出来？（如果还要确定轻重呢？）
推广：N个小球，有一个和其他的质量不同（不知轻重），最少用多少次天平确定？（如果还要确定轻重呢？）
这道题也是很常见的一道题目了，以下将从几个角度分析：
1.信息论找出最下界（不一定可达）
每一次称量都有3种结果（左边重、右边重、一样重）。此时的信息量为：
$H(P)=-\sum_{i=1}^{n}P(i)\log_2P(i)$
在保证这三种结果概率都为 $1/3$ 的情况下，可以计算出 $H(P)=-\log_2(1/3)=\log_23\approx 1.58 bit$
而在不需要知道异常小球轻重的情况下，有12种情况，所需要的信息量为
$H(T)=-\sum_{i=1}^{n}P(i)\log_2P(i)=-\log_2(1/12)=\log_212\approx 3.58 bit$
所以需要的次数就是（向上取整）：
$\frac{H(T)}{H(P)}\approx3$
在需要知道异常小球轻重的情况下，有24种情况，所需要信息量为 $H(T)=-\sum_{i=1}^{n}P(i)\log_2P(i)=-\log_2(1/24)=\log_224\approx 4.58 bit$
依旧是需要3次。
但注意这是要求最理想的情况，也就说每次进行比较都会取到信息量最大的方式，在具体算法设计时，必须将概率平均做到最好。不然如果信息量不够，是达不成最少需要的次数的。
这里给出更精确的定义：