发帖
雷达卡
摘要翻译：
组测试的问题是通过“池中至少包含一个缺陷吗？”形式的池查询从一组对象中识别有缺陷的项。其目的当然是以尽可能少的查询进行检测，这一问题在分子生物学和计算机科学等不同领域都有相关的实际应用。在此，我们研究了概率环境下的GT，重点是在小缺陷概率和大量对象的情况下，$p\to0$，$n\to\infty$。我们构造并分析了一个阶段的算法，对于这些算法，我们建立了一个非检测/检测相变的发生，从而导致了一个尖锐的阈值，$\bar m$，对于测试的数量。通过优化池设计，构造了检测门限遵循最优缩放$\bar M\propto NP\log P$的算法。然后，我们考虑了两阶段算法，并分析了它们在第一阶段池的不同选择下的性能。特别地，通过适当的随机选择池，我们构造算法，使完全检测所需的平均测试数达到最优值（以前在文献[16]中确定）。最后讨论了有限P$情形下的最优池设计。
---
英文标题：
《Group testing with Random Pools: Phase Transitions and Optimal Strategy》
---
作者：
M. M\'ezard, M.Tarzia, C. Toninelli
---
最新提交年份：
2007
---
分类信息：
一级分类：Physics 物理学
二级分类：Statistical Mechanics 统计力学
分类描述：Phase transitions, thermodynamics, field theory, non-equilibrium phenomena, renormalization group and scaling, integrable models, turbulence
相变，热力学，场论，非平衡现象，重整化群和标度，可积模型，湍流
--
---
英文摘要：
The problem of Group Testing is to identify defective items out of a set of objects by means of pool queries of the form "Does the pool contain at least a defective?". The aim is of course to perform detection with the fewest possible queries, a problem which has relevant practical applications in different fields including molecular biology and computer science. Here we study GT in the probabilistic setting focusing on the regime of small defective probability and large number of objects, $p \to 0$ and $N \to \infty$. We construct and analyze one-stage algorithms for which we establish the occurrence of a non-detection/detection phase transition resulting in a sharp threshold, $\bar M$, for the number of tests. By optimizing the pool design we construct algorithms whose detection threshold follows the optimal scaling $\bar M\propto Np|\log p|$. Then we consider two-stages algorithms and analyze their performance for different choices of the first stage pools. In particular, via a proper random choice of the pools, we construct algorithms which attain the optimal value (previously determined in Ref. [16]) for the mean number of tests required for complete detection. We finally discuss the optimal pool design in the case of finite $p$.
---
PDF链接：
https://arxiv.org/pdf/711.2242
京公网安备 11010802022788号
