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

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 $\mathcal{M}$, let $m_{\mathcal{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-\delta$, for some constant $\delta$. In this paper, we study the measures $$c_{\mathcal{M}}(d)=\underset{n\to \mathrm{\infty }}{\lim }\frac{m_{\mathcal{M}}(n,d)}{\ln n}and{c}_{\mathcal{M}}=\underset{d\to \mathrm{\infty }}{\lim }\frac{c_{\mathcal{M}}(d)}{d}\mathrm{.}$$ In the literature, the analyses of such models only give upper bounds for $c_{\mathcal{M}}(d)$ and $c_{\mathcal{M}}$, and for some of them, the bounds are not tight. We give new analyses that yield tight bounds for $c_{\mathcal{M}}(d)$ and $c_{\mathcal{M}}$ for all the known models~$\mathcal{M}$.