用信息熵解决天平称小球和赛马有关问题
用信息熵解决天平称小球和赛马问题
用天平从n个小球中找到重量与众不同的唯一的一个 至少需要使用天平多少次？
这个问题有人提出用信息熵的思路解决。
每次使用天平 可能出现等概率（1/3）的三种状态 平 左偏 右偏
根据公式 信息量I=-log(pi) 其中pi为此事件出现的概率。
所以每次使用天平可以提供-log(1/3) = log3的信息量。
而找到与众不同的那个球
同样根据I=-log(pi)
需要-log(1/2n)= log2n的信息量
所以至少需要 log(2n)/log3 次
但是当把这个理论应用于以下题时，就出了问题：
25匹赛马，5个跑道，也就是说每次有5匹马可以同时比赛。问最少比赛多少次可以知道跑得最快的5匹马
我感觉应该这样解：
每次比赛的结果有A（5,5）种，所以一次比赛可以提供的信息量为 -log(1/A(5,5))
而从25匹马中找到最快的5匹，此事件需要的信息量为-log(1/C(25,5))
所以需要次数为 log(C(25,5))/log(A(5,5)) =2.** 明显是错的
谁能纠正下？
------解决方案--------------------
啊，我把最开始那5次算成一次了。。好吧我错了
事实上，不是信息量的问题
天平问题可以这样描述：3种状态称n次，可以有3^n（注意不是3n）个叶节点，我们需要N个叶节点，所以可以那么算。只是那么算和信息量的算法一致。
而赛马问题，每次比赛是独立性的，所以不是乘方，而是乘法。n次比赛只能得到1次比赛的n倍这么多种结果，而不是n次方
自然折算到对数上就不对了
------解决方案--------------------
赛马问题我是这么算的：log(C(25,5))/log(5) =6.76
用天平从n个小球中找到重量与众不同的唯一的一个 至少需要使用天平多少次？
这个问题有人提出用信息熵的思路解决。
每次使用天平 可能出现等概率（1/3）的三种状态 平 左偏 右偏
根据公式 信息量I=-log(pi) 其中pi为此事件出现的概率。
所以每次使用天平可以提供-log(1/3) = log3的信息量。
而找到与众不同的那个球
同样根据I=-log(pi)
需要-log(1/2n)= log2n的信息量
所以至少需要 log(2n)/log3 次
但是当把这个理论应用于以下题时，就出了问题：
25匹赛马，5个跑道，也就是说每次有5匹马可以同时比赛。问最少比赛多少次可以知道跑得最快的5匹马
我感觉应该这样解：
每次比赛的结果有A（5,5）种，所以一次比赛可以提供的信息量为 -log(1/A(5,5))
而从25匹马中找到最快的5匹，此事件需要的信息量为-log(1/C(25,5))
所以需要次数为 log(C(25,5))/log(A(5,5)) =2.** 明显是错的
谁能纠正下？
------解决方案--------------------
啊，我把最开始那5次算成一次了。。好吧我错了
事实上，不是信息量的问题
天平问题可以这样描述：3种状态称n次，可以有3^n（注意不是3n）个叶节点，我们需要N个叶节点，所以可以那么算。只是那么算和信息量的算法一致。
而赛马问题，每次比赛是独立性的，所以不是乘方，而是乘法。n次比赛只能得到1次比赛的n倍这么多种结果，而不是n次方
自然折算到对数上就不对了
------解决方案--------------------
赛马问题我是这么算的：log(C(25,5))/log(5) =6.76