Asymptotic Efficiency of Two-Stage
Toby Berger, V.I. Levenshtein · 2002
We adapt methods originally developed in informa- tion and coding theory to solve some testing problems. The ef- ficiency of two-stage pool testing of items is characterized by the minimum expected number of tests for the Bernoulli -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 as can be satisfied only if . Using random selection and linear programming, we bound some parameters of binary matrices, thereby determining up to positive constants how the asymptotic behavior of as depends on the manner in which . In particular, it is shown that for , where , the asymptotic efficiency of two-stage procedures cannot be improved upon by generalizing to the class of all multistage adaptive testing algorithms.