天平称球中的信息论

《天平称球中的信息论》由会员分享，可在线阅读，更多相关《天平称球中的信息论（11页珍藏版）》请在金锄头文库上搜索。

1、天平秤球中的信息论mjwu天平秤球过程是人们对事物认识不断深化的过程。从一开始的 一无所知，通过分盘秤球，逐步加深认识，直到最后完全了解为止。 因此，用信息论方法来描述这一过程会获得意想不到的结果。(虽然本文撰写并不要求读者掌握信息论，但先学点信息论基 础对本文的阅读与理解有帮助。)m个球中含有一个次球，通过 n次天平秤球，查寻次球并确定 其轻重。球编号为1，m。初始，球的状态用原始向量X=(xi,Xm) 来表示，Xi为0表示i号球为正品，1重球，-1轻球；仅有一个xi为1或-1。分盘秤球过程中，人们对球的估计与判定用估判向 量Y=(y1,ym)来表示，yi为0表示判定i号球为正品，1疑重 球

2、(或重球或正品)，-1疑轻球(或轻球或正品)，2待定球(或重球或轻球或正品)。统计估判向量 Y中的疑重球数z,疑轻 球数，待定球数d,正品好球数h, z+q+d+h二m。秤球过程中，估判 向量Y不断变化。从初始的 Y=(2,2), z=q=0,d=m开始，每次秤 球后，丫都有所变化，直到丫仅含有一个分量yi为1 (或-1)为止。 此时Y二X,z+q=1,d=0。为方便讨论，第i次秤球后估判向量 Y记为 丫；为简化书写长度，估判向量 Y=(yd,ym)有时写成Y=(z,q,d)。、估判向量的信息量下面考察秤球过程中估判向量 Y 信息量(即其不肯性)的变化：1 ,初始，估判向量Y()=(2,2)，

3、次球可能在1 ,，m号位 置上，其取值有 2 中可能 :1 或-1 。因此，有 2m 种可能状态，初始 Y(0) 的信息量 I(0) 为 log(2m) ，(底为 2，下同)。2 ,第i次秤球后，估判向量Y(i)的各分量有多种可能。但仅有两 种类型：一种是z=0,q=0,d0，此时，Y(i)的各分量仅为0与2，Y(i) 的信息量为log(2d);另一种是z+q0,d=0，此时，Y(i)的各分量仅为 0,1 与-1，Y(i)的信息量 I(i)为 log(z+q);3，最后，估判向量Y(n)的各分量仅有一个为1或-1，即z=1,q=0 或者 z=0,q=1 oz+q=1，丫(n)的信息量 I(n)

4、为 log(z+q)=log(1)=0。此表明， 不肯定性完全消失，查寻完成。综上所述，对于所有的第 i次秤球后，估判向量丫的信息量I(i)=log(z+q+2d) 。例1。设m=10,X=(0,0,1,0)，即第9号球为重球。初始，Y(0)=(2,2),其信息量l()=log(2*10)=log(20)。第一次秤球时，左盘 1-3 号球，右盘 4-6 球，不放盘 7-10 号球。秤球结果：平衡。估判向 量 Y 变 为 Y(1)=(0,0,0,0,0,0,2,2,2,2) ; z=0,q=0,d=4 ; 其 信 息 量 l(1)=log(2*4)=log(8) 。例2, m=14,X=(1,0

5、,0),即第1号球为重球。第一次秤球时， 左盘 1-5 号球，右盘 5-10 球，不放盘 11-14 号球。秤球结果：左重 右轻。估判向量 Y 变为 Y(1)=(1,1,1,1,1 , -1 , -1, -1, -1,-1,0,0,0,0) ; z=5,q=5,d=0 ;其信息量 l(1)=log(5+5)=log(10) 。二、秤球的互信息对于第 i 次秤球一次而言， 估判向量 Y 从原先的 Y(i-1) 变成 Y(i) 。 其信息量从I(M)变成，信息量减少了。所减少的信息量l(i-1)-l(i)是第 i 次秤球所提供的信息量，称为秤球的互信息，记为H(i)：H(i)=l (i-1)-l(

6、i)H(i)表示第i次秤球所生成的不肯定性下降量。如在例 1 中， H(1)= l (0)-l (1 ) =log(20)-log(8)=log(2.5)=1.3219 。在例 2 中， H(1)= l(0)-l(1)=log(20)-log(10)=log(2)=1 。秤球的过程是不肯定性不断减少的过程，也即估判向量 Y 的信 息量不断减少的过程。 通过秤球所提供的互信息， 使得原先的不肯定 性下降到0为止。于是，通过n次秤球可判定次球及其轻重，其初始 的不肯定性 l (0)可分解为I(0)= H(1)+ H(2)+ + H( n)事实上，|(0)=( |(0)-|(1)+ ( |(1)-|

7、(2)+ +( |(n-1)-|(n)+ |(n)，而 I(n) =0。三、用信息论探讨秤球的分盘方法下面对天平秤球作遍历性讨论。 n 次秤球的遍历实际是一个三叉 树。对于第 i 次天平秤球， 有三种结果： 平衡，左重右轻， 左轻右重 其生成的互信息记为H(i), Hi(i), H-i(i)。因此，其加权平均为H(i)=p0*H0(i)+p1*H1(i)+p-1*H-1(i)其中， p0 ,p1 ,p-1 分别表示在平衡，左重右轻，左轻右重时形成 估判向量中所包含的球状态数的百分比。 (参见下例 m=13 的第一次 分盘秤球)。1， 均匀分盘及其秤球所生成的互信息对于第 i 次分盘而言，其原先

8、的估判向量 Y(i-1) 。当 z=0,q=0,d0 ， d是3的倍数，或者d=0,z+q1,z与q都是3的倍数时，可进行均匀 分盘，即放在左盘、右盘及不放盘的球数相等。如 d=da+db+dc0 ， da=db=dc=d/3 ，分别表示放在左盘、右盘 及不放盘的球数。此时，原先估判向量Y(i-1)的信息量l(i-1)=log(2d),而秤球时，如天平平衡，估判向量Y(i)的信息量I(i)=log(2d/3)，本次秤 球所生成的互信息 H0(i)= l(0)-l(1)= log(2d)-log(2d/3)=log(3) ；如天平左 重右轻，估判向量 Y(i)的信息量I(i)=log(da+db

9、)=log(2d/3)，本次秤球 所生成的互信息 H1(i)= I(0)-I(1)= log(2d)-log(2d/3)=log(3) ；如天平左轻 右重，同样的所生成的互信息H-i(i)=log(3)。故，其平均，H(i)=log(3)。如 d=0,z=za+zb+zc=z/30 ， q=qa+qb+qc=q/3 ，并分别表示放在 左盘、右盘及不放盘的球数。此时，原先估判向量Y( i-1)的信息量l(i-1)=log(z+q)，而秤球时，如天平平衡，估判向量Y(i)的信息量I(i)=log(zc+qc), 所生成的互信息 H0(i)= I(0)-I(1)=log(3); 同理， H1(i)=

10、 H-1(i)= log(3) 。故，其平均， H(i)=log(3) 。结论：均匀分盘秤球所生成的互信息 H(i)=log(3) 。根据最大熵原 理，均匀分盘秤球的互信息 H(i)的互信息H(i)最大，其他不等量分盘 一次秤球所生成的互信息均 log(3) 。2， 最佳分盘法及其秤球所生成的互信息在分盘秤球时， 不可能都做到均匀分盘。 如 m=3k+1,3k+2 ，z=q+1 等等。不等量分盘秤球中有一种特别有效的能生成较大互信息的准等 分分盘法，称为最佳分盘法，也叫做孔楼三分法；它包含楼氏三分法 与孔氏三分法。楼氏三分法用于第一次秤球。楼先生在讨论作者编制的“天平秤 球智力游戏”软件时，认

11、为第一次秤球因无参考正品球，应使左盘球 数二右盘球数。设球数m。分解m为整三等分m/3,将其赋予ma,mb,mc; 它们分别表示放在左盘，或右盘，或不放盘的球数； 如多余 1，则 mc+1;如多余 2,贝卩 ma+1,mb+1。m=ma+mb+mc。如，6=2+2+2; 7=2+2+3； 8=3+3+2； 9=3+3+3。而孔氏三分法贝用于非第一次的全部秤球，是孔先生考察查寻次球过程的归纳算法时考虑的一种想法。设待处理球数 p (或为d,或 为乙q)，将p整三等分赋予pa,pb,pc,它们分别表示放在左盘，或右 盘，或不放盘的球数；如多余 1，则pa+1;如多余2，则pa+1, pc+1。 p

12、=pa+pb+pc。如，6=2+2+2； 7=3+2+2； 8=3+2+3； 9=3+3+3。下面通过实例来观察孔楼三分法秤球时的信息与互信息的变化。以m=13,n=4为例。秤球的估判向量Y简记为(z,q,d)。采用孔楼 三分法分盘。 (读者可试画秤球过程估判向量三叉图：以初始估判向 量(0,0,13)为根，三分叉表示平衡， 左重右轻，左轻右重三种情况。 每个节点都是估判向量，终止节点是( 1,0,0)或( 0,1,0)。初始， Y=(0,0,13), I (0)=log(26)=4.70844 。第一次秤球， d=4+4+5 。当左右平衡时， Y=(0,0,5) ，信息量 I=log(10)

13、;当左重右轻或左重右轻时， Y=(4,4,0) ，信息量 I=log(8) ； 第一次秤球的平均信息量：I(1)=( 8*log(8)+8*log(8)+10*log(10)/26 =8/13*log(8)+5/13*log(10)=3.12818;第二次秤球，1， 对于 Y=(0,0,5) 而言， d=2+1+2 。当左右平衡时， Y=(0,0,2) ，信息量 I=log(4); 当左重右轻或左重右轻时， Y=(2,1,0) ，信息量 I=log(3) ； 此平均信息量 =3/5*log(3)+2/5*log(4);2， 对于 Y=(4,4,0) 而言， z=2+1+1,q=2+1+1 。当

14、左右平衡时， Y=(1,1,0) ，信息量 I=log(2); 当左重右轻或左重右轻时， Y=(2,1,0) ，信息量 I=log(3) ； 此平均信息量 =6/8*log(3)+2/8*log(2);第 2 次秤球的平均信息量：I(2) =8/13*(6/8*log(3)+2/8*log(2)+5/13*(3/5*log(3)+2/5*log(4) =(9*log(3)+6*log(2)/13=1.55882;第三次秤球后， Y 只有一项为 (0,0,1 )，其余的均为(1,0,0 ) 或( 0,1,0 )。第 3 次秤球的平均信息量：I(3) =1/13*log(2)=0.07692;第四

15、次秤球后，查寻完毕 第 4 次秤球的平均信息量：I(4)=log(1)=0 。由此，可得每次秤球所生成的互信息：H(1)=1.50826;H(2)=1.56936;H(3)=1.48190;H(4)=0.07692;分析与实验表明： 孔楼三分法秤球不仅能生成比其他任何非均匀 分盘所生成的互信息都大， 而且能减少查寻次球的次数。 除均匀分盘 秤球外，孔楼三分法是最佳分盘法。例如， m=13 的第一次分盘 d=5+5+3 ，则其 I(1)=(10*log(10)+3*log(6)/13=3.151859 ，大于最佳 分盘法的 I(1)= 3.12818 ；即，孔楼三分法所生成的互信息为最大。四、两个关于天平秤球的整数函数1, 给定n通过天平n次秤球能实现查寻次球并判定其轻重的最 大球数m,记为M(n),m=M(n)=(3八n-3)/2(八表示 n 次方).(1)女口 n=3,m=12;n=5,m=120;2, 给定m,要实现查寻次球并判定其轻重的天平秤球最小次数n,记为 N(m),n=N(m)=【log(2m+3)/log3】(此处【x】为进位取整函数：即当x为整数时，【X】二X；当x不 为整数时，【X =x+1，即X有小数点位时进1。X的进位取整 是不小于 x 的最小整数 )。如 m=39,n=4；m=40,n=5。简要证明：一次天平秤球有 3 种