发帖
雷达卡
摘要翻译：
我们研究了一组N个项目的概率群检验，每个项目的概率p是有缺陷的。我们着重讨论了小缺陷概率p<1和大变量数n>>1的双重极限，取p->0在$n\to\infty$之后，或取$p=1/n^{\beta}$在(0,1/2)$中，$\beta}$。在这两种情况下，通过两个阶段的过程$\bar T(N，p)$确定缺陷所需的最佳测试次数被称为$np\log p$。本文确定了$\bart(N，p)/(np\logp)$的尖锐渐近值，并构造了一类两阶段算法，通过该算法得到了该最优值。这是通过为检测的第一阶段选择一个合适的二部正则图（测试和可变节点）来完成的。此外，我们还证明了在任意二部图上，当所有变量都具有相同的度，而检验具有泊松分布度时，这个最优值也是平均的。最后，我们改进了在[1/2,1)$中$p=1/n^{\beta}$与$\beta\情形下已有的最优测试数的上下界。
---
英文标题：
《Group Testing with Random Pools: optimal two-stage algorithms》
---
作者：
Marc Mezard, Cristina Toninelli
---
最新提交年份：
2007
---
分类信息：
一级分类：Computer Science 计算机科学
二级分类：Data Structures and Algorithms 数据结构与算法
分类描述：Covers data structures and analysis of algorithms. Roughly includes material in ACM Subject Classes E.1, E.2, F.2.1, and F.2.2.
涵盖数据结构和算法分析。大致包括ACM学科类E.1、E.2、F.2.1和F.2.2中的材料。
--
一级分类：Physics 物理学
二级分类：Disordered Systems and Neural Networks 无序系统与神经网络
分类描述：Glasses and spin glasses; properties of random, aperiodic and quasiperiodic systems; transport in disordered media; localization; phenomena mediated by defects and disorder; neural networks
眼镜和旋转眼镜；随机、非周期和准周期系统的性质；无序介质中的传输；本地化；由缺陷和无序介导的现象；神经网络
--
一级分类：Physics 物理学
二级分类：Statistical Mechanics 统计力学
分类描述：Phase transitions, thermodynamics, field theory, non-equilibrium phenomena, renormalization group and scaling, integrable models, turbulence
相变，热力学，场论，非平衡现象，重整化群和标度，可积模型，湍流
--
一级分类：Computer Science 计算机科学
二级分类：Information Theory 信息论
分类描述：Covers theoretical and experimental aspects of information theory and coding. Includes material in ACM Subject Class E.4 and intersects with H.1.1.
涵盖信息论和编码的理论和实验方面。包括ACM学科类E.4中的材料，并与H.1.1有交集。
--
一级分类：Mathematics 数学
二级分类：Information Theory 信息论
分类描述：math.IT is an alias for cs.IT. Covers theoretical and experimental aspects of information theory and coding.
它是cs.it的别名。涵盖信息论和编码的理论和实验方面。
--
---
英文摘要：
We study Probabilistic Group Testing of a set of N items each of which is defective with probability p. We focus on the double limit of small defect probability, p<<1, and large number of variables, N>>1, taking either p->0 after $N\to\infty$ or $p=1/N^{\beta}$ with $\beta\in(0,1/2)$. In both settings the optimal number of tests which are required to identify with certainty the defectives via a two-stage procedure, $\bar T(N,p)$, is known to scale as $Np|\log p|$. Here we determine the sharp asymptotic value of $\bar T(N,p)/(Np|\log p|)$ and construct a class of two-stage algorithms over which this optimal value is attained. This is done by choosing a proper bipartite regular graph (of tests and variable nodes) for the first stage of the detection. Furthermore we prove that this optimal value is also attained on average over a random bipartite graph where all variables have the same degree, while the tests have Poisson-distributed degrees. Finally, we improve the existing upper and lower bound for the optimal number of tests in the case $p=1/N^{\beta}$ with $\beta\in[1/2,1)$.
---
PDF链接：
https://arxiv.org/pdf/706.3104
京公网安备 11010802022788号
