Group testing with random pools: Phase transitions and optimal strategy

DOI10.1007/S10955-008-9528-9MaRDI QIDQ937098zbMATH OpenOpenAlexFDO

Authors Marc Mézard, M. Tarzia, Cristina Toninelli

Publication date 20 August 2008

Published in Journal of Statistical Physics (Search for Journal in Brave)

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

zbMATH Keywords

group testinginformation theoryphase transitions

Mathematics Subject Classification ID

Phase transitions (general) in equilibrium statistical mechanics (82B26) Detection theory in information and communication theory (94A13)

Abstract: 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, $po0$ and $Noinfty$. 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, $$, for the number of tests. By optimizing the pool design we construct algorithms whose detection threshold follows the optimal scaling $$. 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$.

Recommendations

• Optimal group testing
• Optimal Two-Stage Algorithms for Group Testing Problems
• Phase transitions in group testing
• Randomized group testing both query-optimal and minimal adaptive
• scientific article; zbMATH DE number 2038701

Cites work

• Asymptotic efficiency of two-stage disjunctive testing
• Correlation inequalities on some partially ordered sets
• scientific article; zbMATH DE number 1508646 (Why is no real title available?)
• scientific article; zbMATH DE number 956611 (Why is no real title available?)
• Non-adaptive group testing in the presence of errors
• Nonrandom binary superimposed codes
• Probabilistic nonadaptive group testing in the presence of errors and DNA library screening
• The capacity of low-density parity-check codes under message-passing decoding

Cited in

(10)

• Optimal group testing with processing times and incomplete identification
• Random and quasi-random designs in group testing
• Applications of bulk queues to group testing models with incomplete identification
• Phase transitions in group testing
• Information-theoretic and algorithmic thresholds for group testing
• A tractable non-adaptative group testing method for non-binary measurements
• Static Risk-Based Group Testing Schemes Under Imperfectly Observable Risk
• Group Testing With Random Pools: Optimal Two-Stage Algorithms
• The planted k-factor problem
• Optimal group testing

This page was built for publication: Group testing with random pools: Phase transitions and optimal strategy

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