Statistical two-round search for one excellent element
This work provides theoretical bounds for a variant of group testing with a different objective (finding one excellent element), which is relevant for applications where identifying a single positive is sufficient.
The paper studies a statistical version of Katona's two-round search problem, where the goal is to find at least one excellent element in a set using noiseless subset tests, minimizing the expected number of tests while achieving a success probability of at least 1-α. The authors show that the optimal expected number of tests grows logarithmically with the population size in the sparse Poisson regime.
We formulate and study a statistical version of Katona's two-round search problem of finding at least one excellent element in a set. A population of $n$ elements is considered, where each element is independently excellent with probability $λ/n$, $λ> 0$. A subset test is noiseless: it returns positive exactly when the queried subset contains at least one excellent element. The goal is to minimize the expected number of tests subject to finding one excellent element with probability at least $1-α$, where $0<α<1$, under the restriction that testing is performed in two rounds. Unlike classical group testing, the objective is not to recover the full set of excellent elements, but only to identify one of them. We first show that success is fundamentally limited by the possibility that no excellent element exists. In the sparse Poisson regime, this imposes the necessary feasibility condition $α\ge e^{-λ}$. When the target success probability is feasible, we prove that the optimal expected number of tests grows logarithmically with the population size. The upper bound is obtained by combining an initial existence test with a second-round separating design; the lower bound follows from an information-counting argument. Numerical illustrations show the feasibility boundary and the resulting logarithmic scaling.