Random and quasi-random designs in group testing.

For large classes of group testing problems, we derive lower bounds for the probability that all significant items are uniquely identified using specially constructed random designs. These bounds allow us to optimize parameters of the randomization schemes. We also suggest and numerically justify a procedure of constructing designs with better separability properties than pure random designs. We illustrate theoretical considerations with a large simulation-based study. This study indicates, in particular, that in the case of the common binary group testing, the suggested families of designs have better separability than the popular designs constructed from disjunct matrices. We also derive several asymptotic expansions and discuss the situations when the resulting approximations achieve high accuracy. • Bounds for the probability that random designs detect all defective items. • Construction of nearly doubly regular designs with superior separability. • Extension for the noisy group testing when several lies are allowed. • Asymptotic expansions for the existential bounds for general group testing. [ABSTRACT FROM AUTHOR]