讨论题 第二章信源熵 设有12枚同值硬币,其中有一枚为假币,且只 知道假币的重量与真币的重量不同,但不知究 竟是重还是轻。现采用天平比较左右两边轻重 的方法来测量(因无砝码)。为了在天平上称 出哪一枚是假币,试问至少必须称多少次? 2021/2/23
第二章 信源熵 2021/2/23 1 讨论题 设有12枚同值硬币，其中有一枚为假币，且只 知道假币的重量与真币的重量不同，但不知究 竟是重还是轻。现采用天平比较左右两边轻重 的方法来测量（因无砝码）。为了在天平上称 出哪一枚是假币，试问至少必须称多少次？
第二章信源熵 解答:在12枚同值硬币中,哪一枚是假币,假币的重量是比真币的 重量重还是轻,都是“无知”、“不确定的”。而用天平比较左 右两边轻重的测量方法,每测一次,能获得一定的信息量,能消 除部分不确定性,则就能确定出其中一枚假币及其重量。因此, 设“在12枚同值硬币中,某一枚为假币”这事件为,其出现的概 率为 p(a)= 又设“假币的重量比真币的重量是重或轻”这事件为,其出现 的概率为 (b) 事件a的不确定性为/(a)=-log2P(a)=log212 事件不确定性为(b)=-log2p(b)=log2 2021/2/23
第二章 信源熵 2021/2/23 2 解答：在12枚同值硬币中，哪一枚是假币，假币的重量是比真币的 重量重还是轻，都是“无知”、“不确定的”。而用天平比较左 右两边轻重的测量方法，每测一次，能获得一定的信息量，能消 除部分不确定性，则就能确定出其中一枚假币及其重量。因此， 设“在12枚同值硬币中，某一枚为假币”这事件为 ,其出现的概 率为 又设“假币的重量比真币的重量是重或轻”这事件为 ，其出现 的概率为 事件 的不确定性为 事件 的不确定性为 a 1 ( ) 12 p a = 1 ( ) 2 p b = 2 2 I a p a ( ) log ( ) log 12 = − = 2 2 I b p b ( ) log ( ) log 2 = − = b b a
第二章信源熵 要发现某假币并知其比真币重还是轻所需的信息量就 是要消除这两个事件的不确定性。因为这两个事件是 统计独立事件,所以需要获得的信息量为 1=(a)+I(b)=log212+log22=log224≈4585(bi) 而在天平上称一次能判断出三种情况:重、轻和相等, 这事件为。这三种情况是等概率的。其概率 为p(c)=1/3。 所以,天平测一次能获得的信息量(即消除的不确定 性)为2=(c)=-log2p()=log23≈158(bi) 则至少必须称的次数为 因此至少必须称三次 log24≈2(次) log, 3 2021/2/23
第二章 信源熵 2021/2/23 3 要发现某假币并知其比真币重还是轻所需的信息量就 是要消除这两个事件的不确定性。因为这两个事件是 统计独立事件，所以需要获得的信息量为 而在天平上称一次能判断出三种情况：重、轻和相等， 这事件为 。这三种情况是等概率的。其概率 为 。 所以，天平测一次能获得的信息量（即消除的不确定 性）为 则至少必须称的次数为 因此至少必须称三次 1 2 2 2 I I a I b bit = + = + = ( ) ( ) log 12 log 2 log 24 4.585( ) p c( ) 1/ 3 = c 2 2 2 I I c p c bit = = − = ( ) log ( ) log 3 1.585( ) 1 2 2 2 log 24 2.9( ) log 3 I I = 次
第二章信源熵 也可不用信息量的方法解答:两分。 首先分成3分,每分4个。称任意 如果两边相平就可以断定假币在另一份中,刚刚称过 的为标准市。把有假币的一份标记为1,2,3,4。第 二次称,取3枚标准市和1,2,3称,如果平则假币是 4。那么用1枚标准币和4称可知假币轻重。如果不平, 不妨设1,2,3重,则1,2,3中有重币,称1,2 如果平则3是偎假币,重。否则,谁重谁就是假币。轻 者,同样处理。 2021/2/23 4
第二章 信源熵 2021/2/23 4 也可不用信息量的方法解答: 首先分成3分，每分4个。称任意两分。 ◼ 如果两边相平就可以断定假币在另一份中，刚刚称过 的为标准币。把有假币的一份标记为1，2，3，4。第 二次称，取3枚标准币和1，2，3称，如果平则假币是 4。那么用1枚标准币和4称可知假币轻重。如果不平， 不妨设1，2，3重，则1，2，3中有重币，称1，2。 如果平则3是假币，重。否则，谁重谁就是假币。轻 者，同样处理
第二章信源熵 如果第一次称两边不平,则把重的标记为1,2,3,4, 轻的标记为5,6,7,8。剩下的标记为9,10,11, 12。可知9,10,11,12为标准币。第二次称1,9, 10,11和5,2,3,4。如果平,则说明6,7,8中有 个轻币,称6,7。如果平,则8是假币,轻。如果 不平,则轻者为假。好,如果第二次不平,不妨设1, 9,10,11重,则有2种可能,1重或者是5轻。第三 次只要称1和标准币就可以知道了。如果1重,则1是 假币。否则5是假币,轻。 2021/2/23
第二章 信源熵 2021/2/23 5 ◼ 如果第一次称两边不平，则把重的标记为1，2，3，4， 轻的标记为5，6，7，8。剩下的标记为9，10，11， 12。可知9，10，11，12为标准币。第二次称1，9， 10，11和5，2，3，4。如果平，则说明6，7，8中有 一个轻币，称6，7。如果平，则8是假币，轻。如果 不平，则轻者为假。好，如果第二次不平，不妨设1， 9，10，11重，则有2种可能，1重或者是5轻。第三 次只要称1和标准币就可以知道了。如果1重，则1是 假币。否则5是假币，轻
第二章信源熵 那么如果第二次不平,5,2,3,4重,则可 以说明2,3,4中有一个重币。那么第三次称 2,3。如果平,则4是重币,否则重者为假币。 至此,在3次内称出了结果。 2021/2/23
第二章 信源熵 2021/2/23 6 ◼ 那么如果第二次不平，5，2，3，4重，则可 以说明2，3，4中有一个重币。那么第三次称 2，3。如果平，则4是重币，否则重者为假币。 ◼ 至此，在3次内称出了结果
讨论 第二章信源熵 题中所问为找一种方法至少必须称多少次能够找出假 币 ■经过理论推算我们肯定有一种最优的方法可以在3次 内找出这枚假币。由理论知要找出这枚假币至少要得 到4.585比特的信息量,而若要在三次内找到这枚假 币就必须保证每次称量获得的信息量至少为1585比 特。 ■但是实际中有可能有的人只用一次就找到了假币,这 种概率很小,当然这个人只一次就获得了很大的信息量; 也有可能有人方法不当测了很多次都找不到这枚假币, 所以说由理论得出的结论只是一种最优次数。 2021/2/23
第二章 信源熵 2021/2/23 7 讨论 ◼ 题中所问为找一种方法至少必须称多少次能够找出假 币 ◼ 经过理论推算我们肯定有一种最优的方法可以在3次 内找出这枚假币。由理论知要找出这枚假币至少要得 到4.585比特的信息量，而若要在三次内找到这枚假 币就必须保证每次称量获得的信息量至少为1.585比 特。 ◼ 但是实际中有可能有的人只用一次就找到了假币，这 种概率很小,当然这个人只一次就获得了很大的信息量； 也有可能有人方法不当测了很多次都找不到这枚假币， 所以说由理论得出的结论只是一种最优次数