A new randomized algorithm for group testing with unknown number of defective items

In many fault detection problems, we want to identify defective items from a set of $$n$$n items using the minimum number of tests. Group testing is for the scenario where each test is on a subset of items, and tells whether the subset contains at least one defective item or not. In practice, the number $$d$$d of defective items is often unknown in advance. In this paper, we propose a new randomized group testing algorithm RPT (Randomized Parallel Testing) for the case where the number $$d$$d of defective items is unknown in advance, such that with high probability $$1-\frac{1}{(2d)^{\Omega (1)}}$$1-1^(2d)Ω(1), the total number of tests performed by RPT is bounded from the above by $$d\log \frac{n}{d}+2d+O(d^{\frac{2}{3}}\log d)$$dlognd+2d+O(^d23logd). If $$0<d<\rho _1 n$$0<d<ρ1n for some constant $$0<\rho _1<1-\frac{1}{e^2}=0.86\ldots $$0<ρ1<1-1^e2=0.86.., which holds for most practical applications, this upper bound is asymptotically smaller than previous best result. In addition, we give a new upper bound $$d\log \frac{n}{d}+2d$$dlognd+2d on $$M(d,n)$$M(d,n), the minimum number of tests required in the worst case to identify all the $$d$$d defective items out of $$n$$n items when the value of $$d$$d is known in advance.