Skip to content

zongwu's blog

至今我们仍未得知那些平行宇宙里的小白鼠们是否懂得信息论

问题

假设现在有1000瓶药水,其中一瓶是毒药,服用后一小时发作身亡。毒药可以无限稀释,那么给定一小时你需要至少几只小白鼠来找到毒药?

一直以来,小白鼠们为生物医学科研和制药行业贡献太多。

来自电子虚拟空间的兔子们表示不服,在魔兽世界里,你触发的每一个任务,执行的每一个无指向性的法术,背后都会有一只无辜的兔子牺牲。1

收一收,回到问题上。让我们暂时把这个问题想象成思想实验。现实没有杀戮和死亡,只有 Love and Peace

题目隐含了一个条件,可以把药水任意混合,不影响测试效果。

倘若我们招聘了1000只小白鼠,每一只小白鼠服下不同的药水,一小时之后倒霉蛋就出现了,解决。

公司效益不好,我们对小白鼠裁员一半,只剩500只,工作量还是那么多,那么每一只小白鼠喝两瓶混合物?比如第一只小白鼠喝1,2;第二只喝3,4;最后一只喝999,1000。结果45号小白鼠挂掉,但是现在我们不知道到底是第22瓶还是第23瓶是毒药。那就需要原来的500只中的250只喝3瓶混合物。比如第一只喝1,2,999;第二只喝3,4,997;依次第二百五十只喝249,250,1,从第二百五十一只照旧喝两瓶。也搞定,但是不公平,为什么有的小白鼠只需要喝两瓶混合物而有的喝三瓶?感觉规则设定得太随意。

小白鼠太多,鼠浮于事,太少,拿不到结果。

如何尽可能地压榨每一只小白鼠喝下M瓶药水,然后还能计算出具体是哪一瓶。世界爱护小动物协会警告。

(啊不对,重新描述)我们至少需要多少只小白鼠冒着生命危险做实验,来告诉我们哪一瓶是毒药。

思考一下:

1000瓶药水,整齐摆在那里,我们无法仅靠肉眼观察找到那一瓶毒药,这1000瓶药水,对我们来说就是个黑箱系统。毒药可能是第一瓶,也可能是第1000瓶。

面对黑箱系统,如何达成目标?我们有 廉价的 伟大的小白鼠。

通过小白鼠与黑箱系统的交互,以及可观察的结果,我们有机会了解这个黑箱系统的某些特性。

每一只小白鼠喝下混合物,只有两种结果,生或者死。就好像一个信号灯,明或者灭。(你以为犹豫才会败北?不,生命无常,从你作为小白鼠的那一刻,就要有必死的觉悟)

一群小白鼠,依照某种规则喝下若干混合物,生生灭灭。然后我们依据所有信号灯的明灭,推断哪一瓶是毒药。

解题

怎么制定这个精巧的规则呢?目前我们还不知道。

让我们尝试把这个问题转化一下,从复杂困难转化成简单容易。我们不懂1000瓶的情况如何处理,但是我们可以从最简单的来。

转化是我们最强大的武器之一。

把药水数量定义为M。先从$M = 2$开始思考

如果有2瓶药水,我们只需要一只小白鼠就知道哪一瓶是毒药。

如果有3瓶药水,我们需要两只小白鼠。让我们给药水编号,从0开始(这会有一点点好处,后面你会看到):0,1,2。给小白鼠编号1,2,3。

编号0瓶放着,小白鼠1号喝编号1,小白鼠2号喝编号2。结果也很直观。

如果有4瓶药水,我们还是只需要2只。编号0瓶放着,小白鼠1号喝编号1,小白鼠2号喝编号2。编号3的药水怎么办?小白鼠1号、小白鼠2号都喝!最终方案是:小白鼠1号喝编号1、编号3,小白鼠2号喝编号2、编号3。

就会有很多结果:

  1. 仅小白鼠1号死了 --> 编号1是毒药
  2. 仅小白鼠2号死了--> 编号2是毒药
  3. 小白鼠1号和2号都死了--> 编号3是毒药
  4. 小白鼠都没死!--> 编号0是毒药

这么叙述太繁琐了,我们用符号简化我们的表述。对于一只小白鼠,用 0表示中毒死了,1表示活着。有两只小白鼠,于是刚才的结果可以描述成:${ 01,10,00,11 }$ 。只要结果取这里的任何一种情况,我们就知道毒药是哪一瓶。

如果有5瓶药水呢?需要3只。所有的可能结果:

  1. 仅小白鼠1号死了 --> 编号1是毒药
  2. 仅小白鼠2号死了--> 编号2是毒药
  3. 小白鼠1号和2号都死了--> 编号3是毒药
  4. 小白鼠3号死了 ---> 编号4是毒药
  5. 小白鼠都没死!--> 编号0是毒药

符号表示:${ 011,010,110,001,111 }$。

从这里我们看出了一点端倪,N只小白鼠,可取值0和1,每一只小白鼠的取值相互独立(you jump I jump?没有的事)。如果可能性集合不小于药水的个数,就能解决问题。

我们的问题可以形式化描述了,给出可计算的方程!

$2^N >= 1000$ ,N为正整数,取结果集的最小值。

N = 10

回看刚才我们从最简单的2,3,4,5瓶水的探索,N的取值分别就是1,2,2,3。

我们通过把问题从1000转化成了 2,3,4,5 找到了一个可能的答案,现在需要直面复杂问题了:$M=1000$。

为了更清晰的验证,让我们重新整理一下刚才的符号表示法。

1000 瓶药水还是从0开始编号,0,1,2,3,4 ... ,1000

10 只小白鼠从右向左排列 10,9,... ,4,3,2,1

深吸一口气,让我们开始真正的艰难之旅。看看所有可能的可能性以及对应的结果:

  1. 编号1是毒药,仅小白鼠1号死了 --> 编码表示为:0000000001(10只小白鼠排排站,最右那只挂了)
  2. 编号2是毒药,仅小白鼠2号死了--> 编码表示为:0000000010 (从右起第2号挂了)
  3. 编号3是毒药,小白鼠1号和2号都死了--> 编码表示为:0000000011 (从右起1号2号挂了)
  4. 编号4是毒药,小白鼠3号死了 ---> 编码表示为:0000000100 (从右起3号挂了)
  5. 编号5是毒药,小白鼠1号和3号死了--> 编码表示为:0000000101 (从右起1号3号挂了)
  6. 编号6是毒药,小白鼠1号和4号死了--> 编码表示为:0000000110 (从右起2号3号挂了)
  7. 编号7是毒药,小白鼠1号、2号、3号死了--> 编码表示为:0000000111(从右起1号2号3号挂了)

  ...

  256. 编号256是毒药,小白鼠9号死了--> 编码表示为:0100000000 (从右起9号挂了)

  ...

  456. 编号456是毒药,小白鼠4号、7号、8号、9号死了--> 编码表示为:0111001000 (从右起4号7号8号9号挂了)

  ...

  998. 编号998是毒药,小白鼠2号、3号、6号、7号、8号、9号、10号死了--> 编码表示为:1111100110 (从右起2号3号6号7号8号9号10号挂了)

  999. 编号999是毒药,小白鼠1号、2号、3号、6号、7号、8号、9号、10号死了--> 编码表示为:1111100111 (从右起1号2号3号6号7号8号9号10号挂了)

  1000. 编号0是毒药,所有的小白鼠都没死--> 编码表示为:0000000000

1000种可能性,我们都可以通过不同的小白鼠的状态表示出来。而且是一一对应。

根据上面所有情况的列举,我们也知道了这10只小白鼠每一只都要喝哪些药水的混合物。

对所有的药水,如果刚才的编码从右边起第1位是1,比如0000000001,0000000011,00000000101等等,混合起来给1号小白鼠喝。

对所有的药水,如果刚才的编码从右边起第2位是1,比如0000000010,0000000011,0000000110 等等,混合起来给2号小白鼠喝。

...

对所有的药水,如果刚才的编码从右边起第10位是1,比如10000000000,1000000001,1000000010等,混合起来给10号小白鼠喝。

总结一下,可能性的结果的编码集是:

${ 0000000001,0000000010, 0000000011, ... ,1111111110,1111111111, 0000000000 }$

如果1前面全是0,省略掉的写法:

${1,10,11,100,101,110 ,... , 1111111110,1111111111,0 }$

对于 $M=1000$ 的任意一瓶药水,在这个结果集中都有唯一一个值对应。

也就是说,出现任意一种结果,我们都能判断哪一瓶是毒药。

这个结果集好熟悉?

这不是就是数字的二进制表示?!

BUT WHY?

我们刚才用了归纳法(不太严格)解出了谜题,而且还发现跟二进制表示法有关联,充满好奇心的我们把问题推进的再深入一点,有没有更基础的理论能解释?

让我们再次思考问题,用更精确的语言描述:

如何利用一群小白鼠的死或者生的所有可能结果唯一标识每一瓶水

我们需要一个等式,一个天平,不是用来称重量称生死,而是称可能性,称信息量。

这个可以度量信息的天平,就是香农定义的熵2

${\displaystyle H(X)=\mathbb {E} _{X}[I(x)]=\sum _{x\in {\mathcal {X}}}^{}p(x)\log _{2}({\frac {1}{p(x)}})}$

其中 ${\mathcal {X}}$ 为有限个事件 x 的集合,$X$ 是定义在 ${\mathcal {X}}$ 上的随机变量。信息熵 $H(X)$ 是对随机事件的度量。

刚才我们列举的试药的小白鼠们可能性的结果,就是随机变量$X$ 。所有的可能性结果集就是 ${\mathcal {X}}$ 。

熵公式的 $log$ 取了以2为底,实际上取 2,e ,10 或者其他值都可以,表明以哪一种进制衡量信息量,这里取2单位就是 bit。对就是那个大名鼎鼎的比特。

其实刚好合适,因为小白鼠只有生和死两种可能性。

1000瓶药水的毒药可能性是均等的,也就$p(x) = 1/1000$ ,${\mathcal {X}}$ 有1000种可能性结果。

信息熵 H(X) 将给出要编码${\mathcal {X}}$ 集合中任意一个x 需要的最少位数, 可以计算得到:

$H(X) \approx 9.965784$

取整数得到10。

到这里,我们总算为拯救无辜小白鼠的性命找到了坚实的理论依据。不再有无辜小白鼠被冒着生命危险试药。

结论

从上面这个思维实验我们还 get 到了什么?

  1. 转化是一种强大的思维武器。其实转化就是计算的本质,这是另外一个庞大的话题了。
  2. 信息熵使得定量分析研究信息的可能性成为现实。这个概念出自香农的研究生论文《A Mathematical Theory of Communication》几年后改名为《The Mathematical Theory of Communication》,你们仔细体会下一字之差背后的含义。
  3. 不要成为小白鼠! 致人而不致于人,说起来容易做起来难呐。受制于游戏规则的时候,要懂点信息论,关键时刻能救命。

1 http://news.17173.com/content/06122018/172405879.shtml

2 https://zh.wikipedia.org/wiki/%E4%BF%A1%E6%81%AF%E8%AE%BA