批量测试的最佳效率

KeyTo9_Fans

有$N$枚硬币，不知真假。每枚硬币是假币的概率$p$是独立的，且均为$1/100$。我们有一架天平和足够多的真币。真币都是一样重的。假币的重量参差不齐，但都比真币稍轻。所以我们把若干枚真币放在天平的一端，把相同数量的未知的硬币放在另一端。若天平平衡，说明未知的硬币全部都是真币。若天平不平衡，说明未知的硬币里面有假币。我们希望用尽可能少的称量次数$m$把$N$枚硬币的真假全部辨别出来。求$lim_{N->\infty}N/m$的最大值。可参阅http://tieba.baidu.com/f?kz=554401316此题与之基本等价。希望能把结论推广到任意的$p$值。

没——问题

每次称一组（x枚）  
若全真，称下一组，即1次辨清一组  
若有假，逐一称本组，即x+1次辨清一组  
一组全真的概率为P=0.99^x
所以辨清一组所需次数的期望为E(x)=P+(1-P)(x+1)
x最优值可求

现在估计x=10，于是E(10)=1.95....
于是lim(N/m)>5

mathe

这个题目最复杂的地方在于第一次分组测试以后，对于那些含假币的组，我们可以再次重新分组测试
而这时，重新分组以后这些硬币是否假币的分布就不是独立的了，很难分析。
我们可以先仅仅考虑一个简单一些的问题，即被分到一组以后的那些银币不会再次和其它组重新混合分组测试。
那么问题要简单很多，我们在计算过程中会遇到两种模型:
1.给定n个硬币，每枚是假币的概率为p而且独立
2.对于情况1添加了一个约束，就是至少含一枚假币。
对于情况1，相当于有$n+1$种不同的情况，分别是含0,1,...,n枚假币，其中含k枚假币的概率为${C_n^k}p^k(1-p)^{n-k}$
而对于情况2，相当于情况1中扣除了含0枚假币的情况，所以含k枚假币的概率为${C_n^kp^k(1-p)^{n-k}}/{1-(1-p)^n}(k>=1)$
我们将情况1需要的最少测量次数期望值记为$A(n,p)$,而情况2需要的次数期望值为$B(n,p)$
显然$A(0,p)=B(0,p)=0,A(1,p)=1,B(1,p)=0$
对于情况1,我们可以选择一次测量u个硬币,那么在这种情况下，这u个硬币不含假币的概率为$(1-p)^u$,而余下n-u个硬币状态为知
所以我们得出
$A(N,p)<=min{(1-p)^u*A(N-u,p)+(1-(1-p)^u)(B(u,p)+A(N-u,p))+1,1<=u<=N}=min{1+A(N-u,p)+(1-(1-p)^u)B(u,p),1<=u<=N}$
而对于情况2，我们也可以饿选择一次测量其中任意u个硬币，那么在这种情况下，
这u个硬币不含假币说明余下N-u个硬币至少含一个假币
而如果这u个硬币含假币，那么余下N-u个硬币完全独立
相当于N个硬币（假设有区分顺序的N个)中假币分布情况共$2^N-1$种不同等概率情况（去除了全部真币的情况）
其中前u个不含假币的情况的概率为${(1-p)^u(1-(1-p)^(N-u))}/{1-(1-p)^N}={(1-p)^u-(1-p)^N}/{1-(1-p)^N}$
而前u个含假币的概率为$1-{(1-p)^u-(1-p)^N}/{1-(1-p)^N}={1-(1-p)^u}/{1-(1-p)^N}$
于是我们得出
$B(N,p)<=min{{(1-p)^u-(1-p)^N}/{1-(1-p)^N}*B(N-u,p)+{1-(1-p)^u}/{1-(1-p)^N}*(B(u,p)+A(N-u,p))+1,1<=u<=N-1}$
现在我们可以使用动态规划计算出A和B的上界。
在得出A(k,p)以后，如果有充分大的N个硬币，其中假币数目期望为$Np$,而如果我们每k个分成一组，那么第一次需要测试$N/k$次，
然后平均来说，余下的组的数目期望为$(1-(1-p)^k)*N/k$组，其中每组还需要测试$B(k,p)$次，所以总测试次数为
$N/k+(1-(1-p)^k)*B(k,p)*N/k$,它同期望假币数目的比例为${kp}/{1+(1-(1-p)^k)*B(k,p)}$,于是我们需要找到这个比例最大的k
这个在k=89时取到，为0.103715.
当然这个数据还没有达到Fans的最有方案，主要就是没有考虑重新分组测试。
不过如果考虑重新分组测试，那么概率的计算就会比较麻烦，因为硬币的概率已经不再相互独立了

mathe

现在结果可以改善到0.090419157711，不过很难突破了

mathe

上面弄错了，应该是可以达到0.110157

mathe

思路是以信息熵作为标准，所以我们需要尽量让每次测量的硬币全部真币的概率尽量接近0.5
比如第一趟可以每69枚一起测量。测量结束后，余下硬币是伪币的概率要大概增加一倍。
于是下一趟大概每34枚一起测量（为了破除相关性，将第一趟不同组的硬币放在一起）
然后接下去分别17枚,8枚和4枚一起测量。
5趟平均花费大概在$1/69+1/{2*34}+1/{4*17}+1/{8*8}+1/{16*4}$次,余下大概还有$1/64$的硬币。
而余下硬币只要逐一测量就可以，（而实际上还可以根据前面的信息适量缩小）。比如我们已经知道某4个硬币中必然有一个伪币，如果其中前3个得出都是真币，那么最后一个不用测量了。

mathe

而另外一方面从信息熵角度来看，上界是0.12377

KeyTo9_Fans

我没有考虑重新分组。

我的方案如下。

假设在初始状态下，有一堆数量足够多的待测硬币。

我们从中拿出$69$枚硬币一起测量，

如果为真，则移除这$69$枚真币后又回到了初始状态；

如果有假，则去到了【状态$69$】（【状态$k$】表示我们已经确定$k$枚硬币里必有$1$枚假币）。

在【状态$69$】的操作如下。

拿前$32$枚硬币测量，

如果为真，则移除这$32$枚真币后就去到了【状态$37$】；

如果有假，则把后$37$枚硬币放回待测硬币堆里去之后就去到了【状态$32$】。

其余状态类似操作，只是分组不同。

各种状态的分组方案如下：

$69: 32,37$
$37: 16,21$
$32: 16,16$
$21: 8,13$
$16: 8,8$
$13: 5,8$
$8: 4,4$
$5: 2,3$
$4: 2,2$
$3: 1,2$
$2: 1,1$
$1: $必为假币，移除后回到初始状态

该方案的效率如下：

平均每次测量能检测出的假币数量约为$0.1233805259061832$枚；

平均需要$8.105006788189457$次测量才能检测出$1$枚假币。

与$1$楼链接里KeyTo9のFans给出的结果一致。

#####

上述分组方案就是不考虑重新分组的最佳方案了。

如果考虑重新分组，则可以获得更高的效率，

但最佳效率不可能高于$0.12377289096543269537981032191172$枚假币/次，

或者不可能低于$8.0793135895911172824866333703569$次测量/枚。

而重新分组的复杂度呈指数级增长，难以找到最佳方案。