2007/06/21 by Marc Mézard, Mezard, Marc, Cristina Toninelli +1
Medicine · Decision Sciences · #SARS-CoV-2 detection and testing #Advanced Statistical Process Monitoring #Probability and Risk Models
paper · doi:10.48550/arxiv.0706.3104
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→∞ or p=1/Nβ with β∈(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, T(N,p), is known to scale as Np|log p|. Here we determine the sharp asymptotic value of 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β with β∈[1/2,1).