Bounds for Nonadaptive Group Tests to Estimate the Amount of Defectives

The classical and well-studied group testing problem is to find

d

defectives in a set of

n

elements by group tests, which tell us for any chosen subset whether it contains defectives or not. Strategies are preferred that use both a small number of tests close to the information-theoretic lower bound

d

log

n

, and a small constant number of stages, where tests in every stage are done in parallel, in order to save time. They should even work if

d

is completely unknown in advance. An essential ingredient of such competitive and minimal-adaptive group testing strategies is an estimate of

d

within a constant factor. More precisely,

d

shall be underestimated only with some given error probability, and overestimated only by a constant factor, called the competitive ratio. The latter problem is also interesting in its own right. It can be solved with

O

(log

n

) randomized group tests of a certain type. In this paper we prove that Ω(log

n

) tests are really needed. The proof is based on an analysis of the influence of tests on the searcher’s ability to distinguish between any two candidate numbers with a constant ratio. Once we know this lower bound, the next challenge is to get optimal constant factors in the

O

(log

n

) test number, depending on the desired error probability and competitive ratio. We give a method to derive upper bounds and conjecture that our particular strategy is already optimal.