Group Testing With Nested Pools

DOI10.1109/TIT.2021.3123929MaRDI QIDQ5030349zbMATH OpenFDO

Authors Inés Armendáriz, Pablo A. Ferrari, Daniel Fraiman, Silvina Ponce Dawson, J. M. Martínez

Publication date 17 February 2022

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2005.13650

zbMATH Keywords

identification of infected individuals of a populationpools

Mathematics Subject Classification ID

Statistical aspects of information-theoretic topics (62B10) Fault detection; testing in circuits and networks (94C12)

Abstract: 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 $pin(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}extor{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 $$, comparable to the information theoretical lower bound $plo{g}_2(1/p)+(1-p)lo{g}_2(1/(1-p))$, the entropy of a Bernoulli$(p)$ random variable.

Recommendations

• Nested group testing procedure
• scientific article; zbMATH DE number 874562
• Group Testing With Random Pools: Optimal Two-Stage Algorithms
• Efficient testing of groups
• On optimal nested group testing algorithms
• Group testing with unreliable tests
• Group testing and batch verification
• Density-based group testing
• Group testing: revisiting the ideas

This page was built for publication: Group Testing With Nested Pools

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5030349)