论文标题
用嵌套池进行小组测试
Group testing with nested pools
论文作者
论文摘要
为了识别人口的受感染者，其样品分为同等大小的组，称为池，并对每个池进行一次实验室测试。样品属于测试阴性的池的个体被声明是健康的，而测试阳性的每个池均分为较小的，相同的池，在下一阶段进行了测试。在$（k+1）$ - 第阶段，所有剩余的样品均已测试。如果$ p <1-3^{ - 1/3} $，我们将每个人的预期测试数量最小化，这是数字$ k+1 $ avage的函数，而在第一个$ k $阶段中的池尺寸。我们表明，对于（0，1-3^{ - 1/3}）$，对于每个$ p \ in（0，1-3^}）$，最佳选择是明确描述的四个可能的方案之一。我们推测，对于每个$ p $，最佳选择是池大小$（3^k \ text {or} 3^{k-1} 4,3^{k-1}，\ dots，3^2,3）$的两个序列之一，其精确描述了$ p $的范围。猜想得到了$ p> 2^{ - 51} $的压倒性数值证据的支持。我们还表明，在方案中最好的成本$（3^k，\ dots，3）$是订单$ o \ big（p \ log（1/p）\ big）$，可与信息理论下限$ p \ log_2（1/p）+（1-p）+（1-p）\ log_2（1-p）\ log_2（1-p）$（per）
In order to identify the infected individuals of a population, their samples are divided in equally sized groups called pools and a single laboratory test is applied to each pool. Individuals whose samples belong to pools that test negative are declared healthy, while each pool that tests positive is divided into smaller, equally sized pools which are tested in the next stage. In the $(k+1)$-th stage all remaining samples are tested. If $p<1-3^{-1/3}$, we minimize the expected number of tests per individual as a function of the number $k+1$ of stages, and of the pool sizes in the first $k$ stages. We show that for each $p\in (0, 1-3^{-1/3})$ the optimal choice is one of four possible schemes, which are explicitly described. We conjecture that for each $p$, the optimal choice is one of the two sequences of pool sizes $(3^k\text{ or }3^{k-1}4,3^{k-1},\dots,3^2,3 )$, with a precise description of the range of $p$'s where each is optimal. The conjecture is supported by overwhelming numerical evidence for $p>2^{-51}$. We also show that the cost of the best among the schemes $(3^k,\dots,3)$ is of order $O\big(p\log(1/p)\big)$, comparable to the information theoretical lower bound $p\log_2(1/p)+(1-p)\log_2(1/(1-p))$, the entropy of a Bernoulli$(p)$ random variable.
