区块测试

据说“区块”这个词现在比较热，我来蹭个热度，标题借用一下，实际上我们要讲的是病毒群测。当然也不是完全离谱，区块与群有时候是可以互换的。

前几天在微博转了一个群测病毒的贴（见下图），并提了一个问题，每次测多少最佳？这个其实是很常用的方法，算法也很简单。不少人问具体算法，因为比较有趣，回答别人的时候写得多了一些，干脆凑在一起算一篇文章。

这次新冠病毒抗疫工作做得比较好的国家总结出来的经验是，全面跟踪确诊者以及确诊者接触过的人。但是，这个经验要实施，必须要检测度跟上去。美国在川普的拖延下，错过最好时机，后来检测跟不上了。在现有情况下，提高检测效率就成了当务之急。有人提出了群检的方法

这个方法翻译过来就是，每次把五个人的采样混在一起，同时测，如果是阴性，则全部通过过，如果是阳性，再每人分测。这个想法不错，但操作不容易。另外，这个方法要有效，必须假设很低的阳性率，如果阳性率大于20%，就几乎不划算了。

现在假设我们已经解决了操作问题，单纯从效率上来考虑这个问题。给定一个已知的阳性率（比如10%），每次检测多少个才能有最大效率。上面英文建议是每次五个，但是在阳性率是10%的情况下，五个是最好的选择吗？我们就来算一下。

在算这个题目以前，我们先来看一个很经典的找次品问题。

有一批金币里有一些分量不足的次品，次品率是1%，也就是说平均每100个金币里有一个次品（分量不足）。现在让你用秤来找出这些次品。怎样秤效率最高？（假设你已经有很多标准金币）。

比如，假设有100个金币。一个一个地秤，需要秤100次。两个两个地秤，需要先秤50次。如果有些组发现有次品，还需对有次品的那些组每一个再秤一次。如果次品率是1%的话，50组里平均有一组会有次品，也就是说还得再秤两次，总共52次，这样的秤法立马就几乎把效率提高了一倍。当然，两次不是最佳选择，多少次是最佳选择呢？

我们把这个问题一般化，假设次品率是p，每次秤k 个，这样平均需要秤几次？用统计语言来说，就是需要算检测次数的期望值。

期望值的算法是把每一种可能发生的情况的概率乘以其所对应的数值然后加起来。比如你花3块钱买彩票。为了增加变数，你买了三张不同种类的彩票。第一张奖额是10块，中奖率是1/20. 第二张奖额是100块，中奖率是1/300. 第三张奖额是10000块，中奖率是1/60000. 那么，三张彩票你期望得到的钱是10* 1/20 + 100* 1/300 + 10000 * 1/60000 = 1/2+1/3+1/6 = 1。你花三块钱买了一个1块钱的期望值，另外两块钱交了愚人税。一般来说买彩票的人都是买同一种彩票，期望值算法更简单，交愚人税的本质是一样的。

把这个期望值算法应用到我们这个题目。一次秤 k 个金币，都正常的概率是 (1-p)^k，这种情况全过关，只需秤一次。有假币的概率是 1 - (1-p)^k，这种情况，必须每个再秤，多秤 k 次，总共 k+1 次。期望值就是

(1-p)^k + (1 - (1-p)^k)*(k+1) = 1 + (1 - (1-p)^k)*k

算效率的话，把这个期望值除以 k （一个一个地秤需要 k 次）。如果商小于一，说明效率提高了。如果商大于一，说明效率降低了。要求最大效率，就是要求这个商的最小值。

上面的等式除以 k 得到期望效率为

1/k + 1 - (1-p)^k

学过微积分的都知道，极值发生在导数为0处。所以，问题变成求导数函数的零点。上面式子对 k 的导数是：

-1/k^2 - (1-p)^k*log(1-p)

因为有对数和指数，它的零点用手算不容易。如果用数学软件则很容易。

考虑到通常 p 值很小，我们可以通过近似方法来找到不用数学软件的解法。把上面的期望效率展开为p的多项式并省略高阶项，我们得到 1/k +k*p , 对这个式子求导解极值就很容易了。p - 1/k^2 = 0 ==> k = 1/sqrt(p)。这个虽然是近似值，但因为结果很漂亮，简单好记，是粗估最佳解的好公式。比如，当 p = 1%时，最佳解大概是 10.

下图是根据不同的p 值算出的最大效率 k 值。蓝线是精确解，红线是近似解。可以看出，因为省略了高阶项，近似解比精确解略小，但很接近。把近似解朝上取整就与精确解差不多了。

回到病毒检测问题。从数学上来说，与找假币是完全相同的问题。不过，实际操作起来，病毒检测要复杂的多。而且还有时间问题。有些检测方法需要三天以后看结果，群测需要再测的话就要等六天，病情已经加重了。所以，群测问题还要考虑到随之引起的操作复杂度，出错可能性的增加以及其它问题。从上图看到，如果阳性率超过20%，最佳群测个数已经要小于3了。其提高的效率与增加的复杂性就需要一个权衡。单纯从数字上来说，第一图建议的五人一组，需要阳性率在5%左右才是最优解。现实中，去检测的都是怀疑自己有可能中招的人，所以阳性率绝对在5%以上。有数据说全美检测的阳性率大于10%，纽约大于20%。这么高的阳性率，这个群测方法的实际意义就需要考虑了。

好消息是，新的更简易，更快的检测方法已经出来了，已经没有群测的必要。对我们来说，利用这个机会结合实际做一个简单的趣味数学题目，学习一个新知识，也算隔离期间的一个收获。