Group Testing with Random Pools: optimal two-stage algorithms

Understand

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.