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 ${\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-\delta$, for some constant
$\delta$. In this paper, we study the measures $$c_{\cal M}(d)=\lim_{n\to
\infty} \frac{m_{\cal M}(n,d)}{\ln n} \mbox{ and } c_{\cal M}=\lim_{d\to
\infty} \frac{c_{\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}$.
