Asymptotic efficiency of two-stage disjunctive testing

We adapt methods originally developed in information and coding theory to solve some testing problems. The efficiency of two-stage pool testing of n items is characterized by the minimum expected number E(n, p) of tests for the Bernoulli p-scheme, where the minimum is taken over a matrix that specifies the tests that constitute the first stage. An information-theoretic bound implies that the natural desire to achieve E(n, p) = o(n) as n → ∞ can be satisfied only if p(n) → 0. Using random selection and linear programming, we bound some parameters of binary matrices, thereby determining up to positive constants how the asymptotic behavior of E(n, p) as n → ∞ depends on the manner in which p(n) → 0. In particular, it is shown that for p(n) = n^-β+o(1), where 0 < β < 1, the asymptotic efficiency of two-stage procedures cannot be improved upon by generalizing to the class of all multistage adaptive testing algorithms