Hypothesis Test for Bounds on the Size of Random Defective Set

摘要

The conventional model of disjunctive group testing assumes that there are several defective elements (or defectives) among a large population, and a group test yields the positive response if and only if the testing group contains at least one defective element. The basic problem is to find all defectives using a minimal possible number of group tests. However, when the number of defectives is unknown there arises an additional problem, namely: how to estimate the random number of defective elements. In this paper, we concentrate on testing the hypothesis H-0: the number of defectives <= s(1) against the alternative hypothesis H-1: the number of defectives >= s(2). We introduce a new decoding algorithm based on the comparison of the number of tests having positive responses with an appropriate fixed threshold. For some asymptotic regimes on s(1) and s(2), the proposed algorithm is shown to be order-optimal. Additionally, our simulation results verify the advantages of the proposed algorithm such as low complexity and a small error probability compared with known algorithms.