Optimal detection of two defectives with a parity check device.

Recently, the problems of detecting two defectives under various testing models have been studied as a forum for exploring the boundaries between easy problems and hard problems in combinatorial searching. In this paper we define five levels of optimality to measure the difficulty. These five levels are minimax, almost surely minimax, measure p minimax, first-order minimax and order of magnitude minimax. We give a new procedure which is almost surely minimax for the parity check model, improving the previously best procedure which is measure p minimax.