Bounds for the Number of Tests in Non-Adaptive Randomized Algorithms for Group Testing

2019/11/05 by Bshouty, Nader H., Haddad, George, Haddad-Zaknoon, Catherine A.
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.1911.01694

Abstract

We study the group testing problem with non-adaptive randomized algorithms. Several models have been discussed in the literature to determine how to randomly choose the tests. For a model \cal M, let m_{\cal M}(n,d) be the minimum number of tests required to detect at most d defectives within n items, with success probability at least 1-δ, for some constant δ. In this paper, we study the measures c_{\cal M}(d)=lim_{n→ ∞} \fracm_{\cal M}(n,d)ln n and c_{\cal M}=lim_{d→ ∞} \fracc_{\cal M}(d)d. In the literature, the analyses of such models only give upper bounds for c_{\cal M}(d) and c_{\cal M}, and for some of them, the bounds are not tight. We give new analyses that yield tight bounds for c_{\cal M}(d) and c_{\cal M} for all the known models~\cal M.

Related

• Optimal Randomized Group Testing Algorithm to Determine the Number of\n Defectives
• On Detecting Some Defective Items in Group Testing
• A Tight Lower Bound of Ω(log n) for the Estimation of the Number of Defective Items
• A tight lower bound on non-adaptive group testing estimation
• Non-Adaptive Randomized Algorithm for Group Testing