猪喝毒水信息熵

作者: 合肥黑 | 来源:发表于2022-03-25 22:19 被阅读0次

事情的起因是有这么一道题：
25桶水其中一桶有毒，猪喝水后会在15分钟内死去，想用一个小时找到这桶毒水，至少需要几头猪？

一滴毒水足以导致一头猪的死亡
死亡时间为15分钟内不确定的某个时间点
猪的承水量无穷大，且假设饮一桶水花费时间为零
每桶水的量无穷大

看到这个题，我直接就使用了二分法，25桶直接分成12桶+12桶+1桶，然后12分6，6分3，3分1，最终计算结果是需要5头猪，反过来理解，也就是 $2^4=16,2^5=32$ ，现在就25桶水，当然答案是5头猪。然而我这个答案是错的……

百度了一下，发现是一道leecode题目，正确答案是2。解法也很容易理解，这里借用百度到的一张图来帮助理解，如果我下面的解释没看懂，也可以去看一下博主原文：[leetcode]——哪桶水有毒

image.png

如图，把25桶水分成5行5列，派两头猪，一个逐行喝(注意是一次性喝掉这一行的5桶水的混合物)，一个逐列喝。以逐列的猪为例，15分钟后死了说明毒水在第1列，如果活着就继续去喝第2列，然后分别等到30、45、60分钟观察是否死亡来锁定是哪一列，如果60分钟还没死，说明前面4列都没毒水，那么用排除法就知道毒水只能在第5列。逐行猪同理，最终只要锁定了行列数，那么交叉点必然是毒水所在位置。

可以观察到，这种解法的关键是，一头猪充分利用了15分钟的间隔，在1个小时内直接辨明了5大桶水(实际是5桶混合水)是否有毒。如果题目改成是10分钟的间隔呢，那1个小时就能辨明7桶水了。此时7的2次方是49，仍然需要2头猪。

再扩展一下，仍然是15分钟间隔，但总共是1000桶水呢？实际上，一头猪只能辨明5，两个维度只能是5乘以5，再来一头，就是5的3次方；很容易发现，问题实际变成求5的多少次方能大于1000，答案易得是5头猪。其实这时候5的5次方是3125，也就是说即使是3000桶水，5头猪也是够的。

再扩展一下，如果是15分钟间隔，但要求是15分钟搞定，而不是一个小时呢？这时候会发现，15分钟结束后，猪只有两个状态，要么死要么活。也就是每一行或每一列实际上只能放2桶水。那么问题就变成2的多少次方大于25，哎，此时的答案和我刚开始使用的二分法是完全一致的。这个时候，我才意识到，我的二分法，实际上不需要1小时，仅仅15分钟就能搞定辨明毒水的目的。因为题目中说了，每桶水是无限多的，那我可以先按二分的思路，把25桶水全部都拆好，然后一声令下，5头猪同时上去喝对应的分组，当然是15分钟后就知道结果了。

然而事情到现在，才刚刚开始……比如这个知乎3万赞的回答：
1000桶水，其中一桶有毒，猪喝毒水后会在15分钟内死去，想用一个小时找到这桶毒水，至少需要几头猪？ - 苗华栋的回答 - 知乎

作者上来就丢出信息熵的定义和公式：

image.png

然后用这公式一顿计算，把我看懵逼了。这里建议先通过别的链接，来补一下基础知识。

一、信息熵

参考信息熵是什么？ - 运筹之学的回答 - 知乎

信息熵，信息熵，怎么看怎么觉得这个“熵”字不顺眼，那就先不看。我们起码知道这个概念跟信息有关系。而它又是个数学模型里面的概念，一般而言是可以量化的。所以，第一个问题来了：信息是不是可以量化？

起码直觉上而言是可以的，不然怎么可能我们觉得有些人说的废话特别多，“没什么信息量”，有些人一语中的，一句话就传达了很大的信息量。

1.为什么有的信息量大有的信息量小？

有些事情本来不是很确定，例如明天股票是涨还是跌。如果你告诉我明天NBA决赛开始了，这两者似乎没啥关系啊，所以你的信息对明天股票是涨是跌带来的信息量很少。但是假如NBA决赛一开始，大家都不关注股票了没人坐庄股票有99%的概率会跌，那你这句话信息量就很大，因为本来不确定的事情变得十分确定。

而有些事情本来就很确定了，例如太阳从东边升起，你再告诉我一百遍太阳从东边升起，你的话还是丝毫没有信息量的，因为这事情不能更确定了。

所以说信息量的大小跟事情不确定性的变化有关。

2.那么，不确定性的变化跟什么有关呢？

一，跟事情的可能结果的数量有关；二，跟概率有关。

先说一。例如我们讨论太阳从哪升起。本来就只有一个结果，我们早就知道，那么无论谁传递任何信息都是没有信息量的。当可能结果数量比较大时，我们得到的新信息才有潜力拥有大信息量。

二，单看可能结果数量不够，还要看初始的概率分布。例如一开始我就知道小明在电影院的有15*15个座位的A厅看电影。小明可以坐的位置有225个，可能结果数量算多了。可是假如我们一开始就知道小明坐在第一排的最左边的可能是99%，坐其它位置的可能性微乎其微，那么在大多数情况下，你再告诉我小明的什么信息也没有多大用，因为我们几乎确定小明坐第一排的最左边了。那么，怎么衡量不确定性的变化的大小呢？怎么定义呢？这个问题不好回答，但是假设我们已经知道这个量已经存在了，不妨就叫做信息量，那么你觉得信息量起码该满足些什么特点呢？

3.信息量函数

一，起码不是个负数吧，不然说句话还偷走信息呢~
二，起码信息量和信息量之间可以相加吧！假如你告诉我的第一句话的信息量是3，在第一句话的基础上又告诉我一句话，额外信息量是4，那么两句话信息量加起来应该等于7吧！难道还能是5是9？
三，刚刚已经提过，信息量跟概率有关系，但我们应该会觉得，信息量是连续依赖于概率的吧！就是说，某一个概率变化了0.0000001，那么这个信息量不应该变化很大。
四，刚刚也提过，信息量大小跟可能结果数量有关。假如每一个可能的结果出现的概率一样，那么对于可能结果数量多的那个事件，新信息有更大的潜力具有更大的信息量，因为初始状态下不确定性更大。

那有什么函数能满足上面四个条件呢？

先揭晓一下答案，注意px就是事件的概率

负的对数函数，也就是-log（x）！底数取大于1的数保证这个函数是非负的就行。前面再随便乘个正常数也行。

a. 为什么不是正的？因为假如是正的，由于x是小于等于1的数，log（x）就小于等于0了。第一个特点满足。

这里随便找了一张函数曲线帮助理解

b. 咱们再来验证一下其他特点。三是最容易的。假如x是一个概率，那么log（x）是连续依赖于x的。donec。

四呢？假如有n个可能结果，那么出现任意一个的概率是1/n，而-log(1/n)是n的增函数，没问题。

d。最后验证二。由于-log(xy) = -log(x) -log(y)，所以也是对的。学数学的同学注意，这里的y可以是给定x的条件概率，当然也可以独立于x。By the way，这个函数是唯一的（除了还可以多乘上任意一个常数），有时间可以自己证明一下，或者查书。

ok，所以我们知道一个事件的信息量就是这个事件发生的概率的负对数。最后终于能回到信息熵。信息熵是跟所有可能性有关系的。每个可能事件的发生都有个概率。信息熵就是平均而言发生一个事件我们得到的信息量大小。所以数学上，信息熵其实是信息量的期望。（表达式参考其它答案或者看下面）

image.png

据评论里 @林杰威的说法：
熵最早是由热力学定义的一个函数，是普朗克来中国讲学的时候引入的。英文是“entropy”这个字，中文词汇中没有相关的字眼。当时是一个有名的姓胡的学者作为普朗克的翻译。因为这个熵“S”是定义为热量Q与温度的比值，所以当时他翻译是立刻创造出熵这个字，从火，从商。

二、从编码的角度来思考信息熵

参考信息熵是什么？ - D.Han的回答 - 知乎

赌马比赛里，有4匹马{A,B,C,D},获胜概率为{1/2,1/4,1/8,1/8}。接下来，让我们将哪一匹马获胜视为一个随机变量X。

假定我们需要用尽可能少的二元问题来确定随机变量 X 的取值。例如：问题1：A获胜了吗？问题2：B获胜了吗？问题3：C获胜了吗？最后我们可以通过最多3个二元问题，来确定X的取值，即哪一匹马赢了比赛。

如果X=A,那么需要问1次（问题1：是不是A？），概率为1/2
如果X=B,那么需要问2次（问题1：是不是A？问题2：是不是B？），概率为1/4
如果X=C,那么需要问3次（问题1，问题2，问题3），概率为1/8
如果X=D,那么同样需要问3次（问题1，问题2，问题3），概率为1/8

那么很容易计算，在这种问法下，为确定X取值

image.png

当我们使用上述的信息熵公式，是这样的：
-1/2*log(1/2) + -1/4*log(1/4) + -1/8*log(1/8) + -1/8*log(1/8)
这里很容易计算结果，比如：-1/2*log(1/2) = -1/2 * (log1 - log2) = 1/2 * log2 = 1/2，最终结果就是：
1/2+1/2+3/8+3/8 = 7/4

可以发现，信息熵公式计算结果与之前计算是一致的。在二进制计算机中，一个比特为0或1，其实就代表了一个二元问题的回答。也就是说，在计算机中，我们给哪一匹马夺冠这个事件进行编码，所需要的平均码长为1.75个比特。

很显然，为了尽可能减少码长，我们要给发生概率较大的事件，分配较短的码长。这个问题深入讨论，可以得出霍夫曼编码的概念。

扩展阅读可以参考H264系列九热力学熵信息熵哈夫曼编码哥伦布编码，在这篇文章里，也有一个很有意思的例子：

我要抛一次骰子，在观测到结果之前，骰子六个面向上都有可能，而且概率完全一样（都是1/6).这时，这一事件的信息熵为 $-log_2\cfrac{1}{6}=log_26$ 。这个结果用之前的信息熵公式也很好计算，相当于累加6次-1/6*log(1/6)，即-log(1/6)=-(log1-log6)=log6，注意这个算法在之后算猪喝毒水时也会用到。

现在万能的女神给了我一个提示，这次骰子的结果一定是偶数，于是可能的结果由6种降低为3种，事件的熵也就变成了 $log_23$ 。也就是说，当我得到提示后，对于事件结果的不确定性降低了。我们把信息熵降低的量规定为信息量I。上面那条提示对我的信息量是 $I=log_26-log_23=log_22=1$ ，正好是1比特，相当于对一个完全未知的命题做一次是非判断需要的信息量。而如果我要得到唯一确定的结果，P(x)就必须等于1，此时的信息熵为零。我们需要得到的信息量就是原本的熵 $log_26$ 。

看到这里，聪明的你一定已经可以自己总结出另一个金光闪闪的结论：信息就是负熵。需要特别注意的是，这句话里的“熵”指而且仅指信息熵，试图将这个结论扩大到热力学熵的解释往往都缺乏足够的事实基础，并且含义也经常是含混的。

三、使用信息熵的公式来解决猪喝毒水

是时候回到知乎3万赞的回答了：1000桶水，其中一桶有毒，猪喝毒水后会在15分钟内死去，想用一个小时找到这桶毒水，至少需要几头猪？ - 苗华栋的回答 - 知乎

1.第一个问题

1000桶水，其中一桶有毒，猪喝毒水后会在15分钟内死去，想用15分钟内找到这桶毒水，至少需要几头猪？

首先，”1000桶水其中有一桶有毒“这个随机变量X的信息熵为：-(1/1000)*log(1/1000)累加1千次。这个很容易理解吧，毒水出现在任意一桶之中是个等概率事件，累加起来的结果就是：
-log(1/1000) = log 1000 约等于9.966

1只猪喝水以后的要么活着，要么死去，一共有两种状态，所以”1只猪喝完水以后的状态“这个随机变量Y的信息熵为

image.png

n只猪喝完水会有2的n次方种状态，即"n只猪喝完水以后的状态"这个随机变量Y的信息熵为

image.png

所以，按照题目要求，如果至少需要n头猪能够找到这桶毒水，那么随机变量Y的信息熵必须要大于随机变量X的信息熵，也就是H(Y) >= H(X) ，也就是 n >= 9.966，即 n = 10

当我们用信息熵算出来了n的最小值以后，我们就可以坚信，理论上n=10一定是最优解，任何想方设法想找到小于10的值都是徒劳的。

其实，上面的信息熵计算的简化版本可以写成如下更好理解的形式 $2^n>=1000$ ，同样可以解得 n = 10 ，虽然形式简单，但我们一定要记住它背后的原理是信息熵。

至于到底采用什么方案，这涉及到术的层面，即使我们暂时想不到，我们也会有努力的方向，并且知道努力的边界在哪里，不会做类似寻找永动机的事情。

注：这里判定2的n次方大于等于1000，正是我们之前二分法和画图得到的结论，现在作者用信息熵的方式给出了解释。至于具体方案，可以参考作者原文。

2.第二个问题

1000桶水，其中一桶有毒，猪喝毒水后会在15分钟内死去，想用一个小时找到这桶毒水，至少需要几头猪？

1000桶水其中有一桶有毒，和第一个问题相同，仍然是9.966。但是，猪的信息熵不同了。我们可以想象一下，一只猪在一个小时内会有几种状态？

在第0分钟的时候喝了一桶水以后，第15分钟死去。
第15分钟依然活着，喝了一桶水以后，第30分钟死去。
第30分钟依然活着，喝了一桶水以后，第45分钟死去。
第45分钟依然活着，喝了一桶水以后，第60分钟死去。
第45分钟依然活着，喝了一桶水以后，第60分钟依然活着。

可见，1只猪1个小时以后会有5种状态，所以”1只猪1个小时后的状态“这个随机变量Z的信息熵为

image.png

n只猪1个小时后会有 5的n次方种状态，即"n只猪1个小时以后的状态"这个随机变量Y的信息熵为

image.png

所以，按照题目要求，如果至少需要n头猪能够找到这桶毒水，那么随机变量Y的信息熵必须要大于随机变
量X的信息熵，也就是H(Y) >= H(X) ，也就是 n >= 9.966 / 2.3219 = 4.292，即 n = 5

事实上，对于 n = 5来说，不仅可以检测1000桶水，甚至检测3000桶水都是没有问题的。有兴趣的童鞋
可以试着计算一下。

到此，香农给了我们一个理论极限，但是具体的方案还是需要我们自己进行构造。得出n=5是依靠我们的
理论功底，而得出具体的方案就是我们的工程水平了。

注：这里具体的方案参考作者原文。

四、天平称球问题

还是知乎3万赞的作者，参考香农的信息论究竟牛在哪里？ - 苗华栋的回答 - 知乎，老习惯，这里只介绍思路，具体方案看作者原文。

1.第一个问题

12个外表相同的球中有1个坏球，它的重量比其它11个好球要轻，现在有一台没有砝码的天平，问至少称几次能确保找出这个坏球？

我们可以思考一下，一个天平称量1次后会有3种结果：

左轻右重
左重右轻
左右一样重

所以“天平称量1次后的结果”这个随机变量Z的信息熵是

image.png
天平称量n次会有

3^n

种状态，所以“天平称量n次后的结果”这个随机变量Y的信息熵是

image.png
而“12个外表相同的球中确定1个轻球”这个随机变量X的信息熵为

image.png
按照题目要求，至少称几次能保证找出这个轻球。翻译成数学语言也就是，随机变量Y的信息熵要大于等于随机变量X的信息熵。即H(Y) >= H(X) ，即 n >= 2.262，即 n = 3

如果将上述式子简化，即 $3^n>=12$

2.第二个问题

12个外表相同的球中有1个坏球，它的重量和其它11个球不同，现在有一台没有砝码的天平，问至少称几次能确保找出这个坏球？

这个问题和前面那个问题的不同之处在于不知道这个坏球的轻重。这对信息熵来说跟前面的已知坏球是轻的相比有什么影响呢？

如果有2个球放在天平两侧。如果已知坏球比较轻，当天平不平衡时，我就可以立刻知道坏球是轻的那一侧。而当不知道坏球是轻还是重时，如果天平不平衡，我无法判断坏球是重的那一侧还是轻的那一侧，我只能够知道坏球要么是轻的那一个，要么是重的那一个。所以，在不知道坏球是轻还是重时，每次测量多了一个坏球是轻还是重的不确定性。在上题的基础上，在最高位增加一位表示球的轻重。其中0表示轻，1表示重，如下表所示。于是虽然12个球，但是因为多了一个轻重的不确定性，所以变成24种状态。

image.png

于是“12个外表相同的球中确定1个不知轻重的球”这个随机变量X的信息熵为

image.png

而“天平称量n次后的结果”这个随机变量Y的信息熵没有变，因为天平每次还是只能确定三种状态，所以

image.png

同样，H(Y) >= H(X) ，即 n >= 2.893，即 n = 3可见，前面那道题并没有充分发挥天平的信息优势，3次还能测出不知轻重的坏球。这就是理论武装头脑的好处，先找到答案，再去想方案。这种自顶向下的思考方式的好处就是我们在思考方案之前有了目标，也有了努力的方向，而不是无头苍蝇一样。

如果看了文章开头1000桶水找毒药那道题的童鞋可能会发现，这道题的解题思路几乎是照搬那道题的解题思路，虽然表面上是不同类型的题目，但我们要像香农祖师爷学习，透过题目的表象直穿本质。

这两道题目的底层逻辑都是信息熵，当我们掌握了理论工具以后，人之间的差距就在于是否有足够的能力将现实问题抽象成数学或者其他问题，然后用我们熟知的理论工具去解决它。在这一点上，就和解方程式是一样的。解方程本身非常简单，难点是如何将现实的问题抽象成表达式，定义变量，列出方程式。关于这一点详细的陈述在我的另一篇文章《数学思维在生活中有多大用处？》中有更详细的描述。

五、关于算法导论中的排序算法

参考 1000桶水，其中一桶有毒，猪喝毒水后会在15分钟内死去，想用一个小时找到这桶毒水，至少需要几头猪？ - PlanarG的回答 - 知乎

考虑这样一个过程：假设现在给你两个数a,b，只允许你进行一次比较，将这两个数从小到大排序。你心想这个问题不是非常简单吗，直接拿这两个数比较一次，哪个数小哪个就排在前面。

我们来分析一下这个看似简单的问题的本质是什么。

如果我们只能进行一次比较，那么根据这一次比较，我们能够得到的信息实际上只有两种：要么第一个数较小，要么第二个数较小。而两个数最终从小到大的关系也只有两种情况：要么是 a,b ，要么是b,a 。也就是说，我们能够根据这一次比较的结果建立一个结果-最终排列的双射关系，每一种比较的结果都唯一地对应最终的一种大小关系。

现在考虑上面那个问题的升级版：如果现在给你四个数a,b,c,d 能否通过 4 次比较给它们从小到大排序？答案是否定的。因为通过四次比较我们能得到的信息最多只有2的4次方，即16种。而这4个数的排列一共有4！=24种。因此不可能将询问的结果与最终排列一一对应，我们就证明了 4 不可能是答案的下界。

我们再升级一次，考虑给n个数排序的情况。如果我们在最终的方案中使用了k次比较，那么可能得到的信息有2的k次方种，而n个数的排列有n!种。要建立结果-最终排列的双射关系，必须满足 $2^k >= n!$ 即：

image.png
这就是信息论的牛逼之处：你不需要构造一个具体的方案，但却可以求出答案的理论下界。

现在让我们用信息论的角度思考一下原问题。 1000桶水，只有一桶有毒，换言之，可能的答案只有 1000种。

每头猪在中毒之后 15分钟内死去，那么我们可以从每头猪获得的信息一共有5种：在[0,15) [15,30) [30,45) [45,60)中的哪一个时间段死去，或者最终存活下来。如果最终有k只猪，我们能获得的信息就有 $5^k$ 种，换言之，k需要满足 $5^k >= 1000$ ，即 $k>=log_51000 = 4.292$ ，因此 k的下界为 5。