# Generalized Group Testing

Xiwei Cheng, Sidharth Jaggi, Qiaoqiao Zhou X. Cheng (e-mail:
<EMAIL_ADDRESS>is with the Department of Computer Science and
Engineering, The Chinese University of Hong Kong, Hong Kong.S. Jaggi (e-mail:
<EMAIL_ADDRESS>is with the School of Mathematics, University of
Bristol, U.K.Q. Zhou (email<EMAIL_ADDRESS>is with the Department of
Computer Science, National University of Singapore.A preliminary version of
this work appeared in the Proceedings of the $25^{th}$ International
Conference on Artificial Intelligence and Statistics (AISTATS), Valencia,
Spain, 2022.

###### Abstract

In the problem of classical group testing one aims to identify a small subset
(of size $d$) diseased individuals/defective items in a large population (of
size $n$). This process is based on a minimal number of suitably-designed
group tests on subsets of items, where the test outcome is positive iff the
given test contains at least one defective item.

Motivated by physical considerations, such as scenarios with imperfect test
apparatus, we consider a generalized setting that includes as special cases
multiple other group-testing-like models in the literature. In our setting the
test outcome is governed by an arbitrary monotonically increasing (stochastic)
test function $f(\cdot)$, with the test outcome being positive with
probability $f(x)$, where $x$ is the number of defectives tested in that pool.
This formulation subsumes as special cases a variety of noiseless and noisy
group-testing models in the literature.

Our main contributions are as follows.

Firstly, for any monotone test function $f(\cdot)$ we present a non-adaptive
scheme that with probability $1-\varepsilon$ identifies all defective items.
Our scheme requires at most ${\cal
O}\left({H(f)}d\log\left(\frac{n}{\varepsilon}\right)\right)$ tests, where
${H(f)}$ is a suitably defined “sensitivity parameter” of $f(\cdot)$, and is
never larger than ${\cal O}(d^{1+o(1)})$, but indeed can be substantially
smaller for a variety of $f(\cdot)$.

Secondly, we argue that any non-adaptive group testing scheme needs at least
$\Omega\left((1-\varepsilon){h(f)}d\log\left(\frac{n}{d}\right)\right)$ tests
to ensure high reliability recovery. Here ${h(f)}$ is a suitably defined
“concentration parameter” of $f(\cdot)$, and ${h(f)}\in\Omega{(1)}$.

Thirdly, we prove that our sample-complexity bounds for generalized group
testing are information-theoretically near-optimal for a variety of sparse-
recovery group-testing models in the literature. That is, for any “noisy” test
function $f(\cdot)$ (i.e., $0<f(0)<f(d)<1$), and for a variety of “(one-sided)
noiseless” test functions $f(\cdot)$ (i.e., either $f(0)=0$, or $f(d)=1$, or
both) studied in the literature we show that
$\frac{{H(f)}}{{h(f)}}\in\Theta(1)$. As a by-product we tightly characterize
the heretofore open information-theoretic order-wise sample-complexity for the
well-studied model of threshold group-testing. For general (near)-noiseless
test functions $f(\cdot)$ we show that $\frac{{H(f)}}{{h(f)}}\in{\cal
O}(d^{1+o(1)})$. We also demonstrate a “natural” test-function $f(\cdot)$
whose sample complexity scales “extremally” as $\Theta(d^{2}\log n)$, rather
than $\Theta(d\log n)$ as in the case of classical group-testing.

Some of our techniques may be of independent interest – in particular our
achievability requires a delicate saddle-point approximation, our
impossibility proof relies on a novel bound relating the mutual information of
pair of random variables with the mean and variance of a specific function,
and as a by-product of our proof showing that our sample-complexity upper and
lower bounds are close we derive novel structural results about monotone
functions.

##  I Introduction

Group testing [1] is the non-linear sparse recovery process of identifying a
small subset of defective items from a larger set of items based on a series
of judiciously designed tests. Each test is carried out on a subset of items,
and each binary outcome indicates whether or not the test includes at least
one defective item. In other words, the test outcome is specified by the “OR”
function. In designing the testing scheme, it is desirable to minimize the
number of tests while still enabling high probability of correct
identification of the subset of defective items.111A significant part of the
group-testing literature focuses on zero-error recovery – see for instance the
survey in [2]. However, even in the context of classical group-testing more
stringent recovery criterion comes at the cost of requiring a number of tests
than high-probability recovery requires. Further, in the context of this work,
where test outcomes are probabilistic in nature, zero-error recovery is
impossible, hence we focus on high-probability recovery. The group testing
paradigm has found applications in a wide variety of contexts, including
biology [3], pattern finding [4], wireless communications [5, 6], and testing
for diseases recently COVID-19 testing [7].

Many variants of the classical group testing paradigm have already been
considered in the literature. For example, Damaschke [8] considered threshold
test functions: the test outcome is negative if the number of defectives in a
test is no larger than the lower threshold $\ell$; positive if no smaller than
the upper threshold $u$; and arbitrary (negative or positive) otherwise. Let
$n$ and $d$ be the number of all items and the number of defective items,
respectively. For $u=\ell+1$, [8] proposed an adaptive algorithm with the
number of tests scaling as ${\cal O}\left((d+u^{2})\log n\right)$ to exactly
identify the defectives. However, for $u>\ell+1$, they proved that the
defectives cannot be exactly identified, but ${\cal O}\left((dn^{b}+d^{u})\log
n\right)$ adaptive tests suffice to identify the defectives if up to
$(u-1)(1+\frac{1}{b})-\ell$ misidentifications are allowed (here $b>0$ is an
arbitrary constant). Chen and Fu [9] proposed a non-adaptive algorithm for
which the number of tests scales as ${\cal O}\left(\sigma
d^{u+1}\log(\frac{n}{d})\right)$ if up to $u-\ell-1$ misidentifications and
$\sigma$ erroneous tests are allowed. Subsequently, Cheraghchi [10] showed
that it can be reduced to ${\cal O}\left(d^{u-\ell+1}\log
d\log(\frac{n}{d})\right)$. More recently, for the special case $u=\ell+1$,
[11] reduced it further to ${\cal
O}\left(d^{\frac{3}{2}}\log(\frac{n}{d})\right)$ when $u$ is asymptotically
close to $\frac{d}{2}$. The works of [12, 13] sought to find schemes that
admit low decoding complexity. Chan et al. [14] studied stochastic threshold
group testing. They introduced two stochastic variants of the threshold test
function: Bernoulli gap stochasticity and linear gap stochasticity. For
Bernoulli gap stochasticity, the test outcome is equally likely to be negative
or positive whenever the number of defectives in a test is in the interval
$(\ell,u)$. For linear gap stochasticity, the probability of having positive
outcome increases linearly as the number of defectives ranges from $\ell$ to
$u$. By allowing a small error probability $\varepsilon$, they proposed a two-
stage adaptive algorithm with $11.09e^{2}d\log n+{\cal
O}\left(d\log(\frac{1}{\varepsilon})\right)$ number of tests and a non-
adaptive algorithm with ${\cal
O}\left(\log(\frac{1}{\varepsilon})d\sqrt{\ell}\log n\right)$ number of tests
for Bernoulli gap stochasticity, and a non-adaptive algorithm with ${\cal
O}\left((u-\ell-1)^{2}d\log n\right)+{\cal
O}\left(d\log(\frac{1}{\varepsilon})\right)$ number of tests for linear gap
stochasticity. Recently, for Bernoulli gap stochasticity, Reisizadeh et al.
[15] improved the number of tests required to ${\cal
O}\left(\sqrt{u}d\log^{3}n\right)$.

###  I-A Our contributions

In this paper, motivated by physical considerations such as the effect of
dilution on the chemistry of group tests, we formulate and analyze group
testing with a general monotonically increasing stochastic test function
$f(\cdot)$ (i.e., $x\geq y\Rightarrow f(x)\geq f(y)$) that takes as input the
number of defective items in a test and outputs the probability of the given
test having a positive outcome. This formulation subsumes as special cases a
variety of noiseless and noisy group-testing models in the literature. Our
contributions are as follows.

  * •

For any monotone test function $f(\cdot)$ we present a non-adaptive
generalized group-testing scheme that identifies all defective items with
probability at least $1-\varepsilon$. Our scheme requires at most ${\cal
O}\left({H(f)}d\log\left(\frac{n}{\varepsilon}\right)\right)$ tests, where
${H(f)}$ is a suitably defined “sensitivity parameter” of $f(\cdot)$, and is
never larger than ${\cal O}(d^{1+o(1)})$, but indeed can be substantially
smaller for a variety of $f(\cdot)$. The computational complexity of decoding
is ${\cal O}\left(n{H(f)}d\log\left(\frac{n}{\varepsilon}\right)\right)$.

  * •

We argue that any non-adaptive group testing scheme that has a probability of
error of at most $\varepsilon$ requires at least
$\Omega\left((1-\varepsilon){h(f)}d\log\left(\frac{n}{d}\right)\right)$ tests,
where ${h(f)}$ is a “concentration parameter” of $f(\cdot)$, and
${h(f)}\in\Omega{(1)}$.

  * •

We prove that our sample-complexity bounds for generalized group testing are
information-theoretically near-optimal for a variety of sparse-recovery group-
testing models in the literature. That is,

    * –

For any “noisy” test function $f(\cdot)$ (i.e., $0<f(0)<f(d)<1$) we show that
$\frac{{H(f)}}{{h(f)}}\in\Theta(1)$. This implies that for noisy test
functions our non-adaptive scheme has order-wise optimal sample complexity.

    * –

For a variety of “noiseless” test functions $f(\cdot)$ (i.e. $f(0)=0$,
$f(d)=1$) studied in the literature we also show that
$\frac{{H(f)}}{{h(f)}}\in\Theta(1)$. Hence for these test-functions as well
the sample complexity of our non-adaptive scheme is order-wise optimal.

    * –

As a by-product we tightly characterize the heretofore open information-
theoretic order-wise sample-complexity for the well-studied model of threshold
group-testing.

    * –

Perhaps surprisingly, for technical reason our results are somewhat weaker for
general “(one-sided) near-noiseless” test functions $f(\cdot)$ (i.e., either
$f(0)\xrightarrow{d\rightarrow\infty}0$, or
$f(d)\xrightarrow{d\rightarrow\infty}1$, or both) than for general noisy test
functions. For general near-noiseless test functions $f(\cdot)$ we show that
$\frac{{H(f)}}{{h(f)}}\in{\cal O}(d^{1+o(1)})$.

    * –

We also demonstrate a “natural” test-function $f(\cdot)$ whose sample
complexity scales “extremally” as $\Theta\left(d^{2}\log n\right)$ – our
results above exclude the possibility of any monotone test function having
optimal sample-complexity higher than this. Note that the optimal sample-
complexity scales as $\Theta(d\log n)$ in the case of classical group-testing.

  * •

Some of our techniques may be of independent interest – in particular:

    * –

Our achievability requires a delicate saddle-point approximation,

    * –

Our impossibility proof relies on a novel bound relating the mutual
information of pair of random variables with the mean and variance of a
specific function, and

    * –

As a by-product of our proof showing that our sample-complexity upper and
lower bounds are close we derive novel structural results about monotone
functions.

The rest of this paper is organized as follows. We formulate the generalized
(non-adaptive) group testing problem in Section II. Section III presents our
proposed non-adaptive algorithm. In Section IV we state the main results of
this work. In Section V we describe the intuition behind our results, and
proof sketches, with full proofs deferred to Section VI-VIII and corresponding
Appendices. Finally, Section IX contains simulation results of our proposed
algorithm.

##  II Problem Formulation

A set $\mathcal{N}:=\\{1,\dots,n\\}$ of $n$ items contains a subset
$\mathcal{D}\subsetneq\mathcal{N}$ of defective items – elements in
$\mathcal{N}\setminus\mathcal{D}$ are called non-defective. We follow the
“combinatorial group testing model”, which assumes that the size of defective
set ${\cal D}$ is fixed as $d$, and each such subset has the same probability.
The identity of ${\cal D}$ is unknown a priori – the goal of group testing is
to correctly identify ${\cal D}$ through a minimal series of group tests on
subsets of items. In “classical” group testing a test outcome is negative if
every item in the pool is non-defective, and is positive if at least one item
is defective. As such this may be viewed as a disjunctive measurement, i.e.,
viewing each item as a $0$ or a $1$ depending on whether it is non-defective
or defective, each test performs an OR of the items in its pool. A canonical
setting in which this measurement model is pertinent is when a small number of
individuals in a large population are diseased but only a small number of
testing kits are available; in this case samples from different individuals
may be “pooled” together in different combinations and the set of test
outcomes analyzed jointly to infer ${\cal D}$. In this work we assume that the
number $d=|{{\cal D}}|$ of defectives is known a priori.222 Another branch of
the group-testing literature (see for instance [16, 17, 18]) concerns itself
with the problem of reliably approximating the number $d$ itself with a
minimal number of adaptive or non-adaptive tests. In classical group-testing,
most algorithms are reasonably robust to small perturbations in the value of
$d$, and the task of roughly estimating $d$ is an “easier” task (requiring
asymptotically fewer tests than the task of estimating the set ${\cal D}$). In
this generalized group-testing setting, our algorithms and bounds are
sensitive to small perturbations in the value of $d$, and require the exact
value of $d$. In Appendix M, we present an algorithm for exactly estimating
$d$. It turns out to be a “harder” task (requiring asymptotically more tests
than the task of estimating the set ${\cal D}$).

Instantiating disjunctive tests which are sensitive to even a single defective
in a testing pool may be tricky, for instance due to the impact of dilution on
the chemistry used in pooled tests [19]. Our primary contribution in this work
is to consider a very general class of (probabilistic) measurement functions
$f(\cdot):\mathbb{Z}_{\geq 0}\rightarrow[0,1]$. The input, say $x$, to the
measurement function $f(x)$ is the number of defective items $x$ in a given
pool, and the value of $f(x)$ is the probability that the given test results
in a positive test outcome.

A slight notational subtlety here – since we will be interested in asymptotic
results (when $d$ and $n$ are “large”), in the interest of generality we allow
the function $f(\cdot)$ to also depend on the value of $d$, the overall number
of defectives in the population of size $n$. Hence our notation $f(\cdot)$
actually indexes a set $\\{f_{d}(\cdot)\\}_{d}$ of measurement functions.
Since we assume the number $d$ to be known in advance (see the discussion
above, and Footnote 2) thus the actual function $f_{d}(\cdot)$ in the set
$f(\cdot)$ is well-specified. Thus for notational convenience we suppress the
dependence of $f(\cdot)$ on $d$ in the remainder of this paper. Hence a
statement like $f(0)\xrightarrow{d\rightarrow\infty}0$ should be interpreted
as meaning that $\lim_{d\rightarrow\infty}f_{d}(0)=0$.

In this work we restrict ourselves to the natural class of measurement,
monotone measurement functions, i.e., $x\geq y\Rightarrow f(x)\geq f(y)$.
Monotone measurement functions subsume many existing models of group-testing
as special cases. For instance, when

$f(x)=\left\\{\begin{array}[]{cc}0&\;x=0,\\\ 1&\;x\geq 1,\end{array}\right.$
(1)

this reduces to the problem of classical group testing. Observe that when

$f(x)=\left\\{\begin{array}[]{cc}0&\;x\leq\ell,\\\
\frac{x-\ell}{u-\ell}&\;\ell<x<u,\\\ 1&\;x\geq u,\end{array}\right.$ (2)

for some integers $0<\ell<u<d$, this reduces to the “linear gap” stochastic
group testing examined by [14]. To avoid triviality, we further assume that
$f(0)<f(d)$. (If $f(0)=f(d)$, no sequence of tests can ever reliably recover
the defective set ${\cal D}$.)

It will be helpful to distinguish between two types of test functions
$f(\cdot)$.

  * •

If $0<f(0)<f(d)<1$, we say that $f(\cdot)$ is noisy. For such $f(\cdot)$, even
pools with no defective items have a probability $f(0)$ (some positive
constant independent of $d$) of resulting in a positive test outcome, and
pools with one or more defective items have a probability of at least $1-f(d)$
(again, a constant bounded away from $0$, independent of $d$) of resulting in
a negative test outcome. The corresponding notion of noisy test outcomes in
the classical group-testing literature (see for instance [20]) often focuses
on test functions of the form

$f(x)=\left\\{\begin{array}[]{cc}a&\;x=0,\\\ b&\;x\geq 1,\end{array}\right.$
(3)

for some $0<a<b<1$ (with the symmetric noise setting, i.e. $b=1-a$, receiving
the most attention).

  * •

In contrast,

    * –

If either $f(0)\xrightarrow{d\rightarrow\infty}0$ or
$f(d)\xrightarrow{d\rightarrow\infty}1$ we say that $f(\cdot)$ is one-sided
near-noiseless, and

    * –

If both $f(0)\xrightarrow{d\rightarrow\infty}0$ and
$f(d)\xrightarrow{d\rightarrow\infty}1$ hold we say that $f(\cdot)$ is near-
noiseless.

    * –

Analogously, if either $f(0)=0$ or $f(d)=1$ we say that $f(\cdot)$ is one-
sided noiseless, and

    * –

If both $f(0)=0$ and $f(d)=1$ hold we say that $f(\cdot)$ is noiseless.

Note that (one-sided) near-noiselessness is a significantly weaker requirement
on $f(\cdot)$ than in much of the noiseless group-testing literature, where it
is often assumed that $f(0)=0$ and $f(1)=1$ (the corresponding one-sided
noiseless version was studied in [21]).

Group testing schemes can be adaptive (where each test may be designed based
on the outcomes of all preceding tests) or non-adaptive (where all tests must
be chosen prior to observing any test outcomes). Here, we focus on non-
adaptive group testing.333The adaptive version of group-testing has also been
extensively studied – see for instance the survey in [2]. However, since non-
adaptive tests allow for test-parallelization, and also make it easier to
design hardware to perform the tests (unlike adaptive test designs, where the
composition of (at least some) tests may depend on prior test outcomes), we
restrict our attention in this work to designing non-adaptive schemes.

Non-adaptive generalized group-testing test designs are specified by a
(possibly randomly chosen) binary matrix $\boldsymbol{M}\in\\{0,1\\}^{T\times
n}$, where $M_{ji}=1$ if test $j$ includes item $i$ and $M_{ji}=0$ otherwise.
The rows of $\boldsymbol{M}$ correspond to tests, and the columns correspond
to items. The probability of error of any non-adaptive algorithm (with a
specified test matrix $\boldsymbol{M}$) is defined as the probability that the
estimated defective set $\hat{\mathcal{D}}$ differs from the true
$\mathcal{D}$. This probability is over the elements comprising ${\cal D}$
(which is assumed to be distributed uniformly at random from all $d$-sized
subsets of $\\{1,\ldots,n\\}$), over the randomness in test outcomes (since
each test with $x$ defectives may result in a positive test outcome with
probability $f(x)$ and a negative test outcome with probability $1-f(x)$), and
randomness if any in the decoding rule. We require that the probability of
error is bounded from above by some $\varepsilon$. That is,
$\Pr(\hat{\mathcal{D}}\neq\mathcal{D})\leq\varepsilon$ – such test designs
will be called $(1-\varepsilon)$-reliable.

##  III Test Design and Decoding

We now present our non-adaptive test designs, and the corresponding decoding
rules. We emphasize here that the algorithm below depends critically on prior
knowledge of the size $d$ of the defective set – the setting where $d$ is not
known a priori  is the context of Lemma 3 in Section IV-D.

Test design: We consider Bernoulli designs – see, for example, [22, 23, 24,
25, 26]. That is, the test matrix ${\boldsymbol{M}}$ is a ${T}\times n$ binary
matrix in which each entry is independently chosen to equal $1$ with
probability ${q}$ and $0$ otherwise, for some design parameters $T$ and
${q}\in(0,1)$ to be specified later.

Parameters for the decoding rule: Given these tests and their outcomes we now
specify two decoding rules we use to produce an estimate $\hat{{\cal D}}$ of
the defective set ${\cal D}$. Before presenting the algorithm, let us first
introduce some definitions and notation.

Definitions:

  1. 1.

Item-included test-positivity probability: For any item $i$ in a test, the
quantity ${P(-,{q})}$ denotes the probability that the test has a positive
outcome conditioned on the event that item $i$ is non-defective.444 Due to the
symmetry of randomness in the defective set ${{\cal D}}$ this value is
independent of the index value $i$, hence in our notation we do not index the
notation for these probabilities with $i$. Analogously ${P(+,{q})}$
denotes${}^{\ref{fn:no-i}}$ the probability that the test has a positive
outcome conditioned on the event that item $i$ is defective. Mathematically,

$\displaystyle{P(-,{q})}$
$\displaystyle:=\sum\limits_{j=0}^{d}\binom{d}{j}{q}^{j}(1-{q})^{d-j}f(j),\text{
and}$ (4) $\displaystyle{P(+,{q})}$
$\displaystyle:=\sum\limits_{j=0}^{d-1}\binom{d-1}{j}{q}^{j}(1-{q})^{d-1-j}f(j+1).$

  2. 2.

Item-not-included test-positivity probability: For any item $i$ not in a test,
the quantity ${Q(-,{q})}$ denotes${}^{\ref{fn:no-i}}$ the probability (over
the randomness in the defective set ${{\cal D}}$) that the test has a positive
outcome conditioned on the event that item $i$ is non-defective. Analogously,
${Q(+,{q})}$, denotes${}^{\ref{fn:no-i}}$ the probability that the test has a
positive outcome conditioned on the event that item $i$ is defective.
Mathematically,

$\displaystyle{Q(-,{q})}$
$\displaystyle:=\sum\limits_{j=0}^{d}\binom{d}{j}{q}^{j}(1-{q})^{d-j}f(j),\text{
and}$ (5) $\displaystyle{Q(+,{q})}$
$\displaystyle:=\sum\limits_{j=0}^{d-1}\binom{d-1}{j}{q}^{j}(1-{q})^{d-1-j}f(j).$

  3. 3.

Item test sensitivity: For any item $i$ in a test, its test sensitivity
${\Delta({q})}$ (respectively ${\nabla({q})}$) is defined as the difference
between the probabilities of positive test outcomes conditioned on item $i$
being defective or not.${}^{\ref{fn:no-i}}$ Mathematically,

$\displaystyle{\Delta({q})}:={P(+,{q})}-{P(-,{q})},\text{ and}$ (6)
$\displaystyle{\nabla({q})}:={Q(-,{q})}-{Q(+,{q})}.$

  4. 4.

Minimal test sensitivity: A parameter that will be useful in our code design
and analysis is the minimal test sensitivity ${P_{\min}({q})}$, defined as

$\displaystyle{P_{\min}({q})}:=\min\left\\{{P(+,{q})},1-{Q(+,{q})}\right\\}.$
(7)

Lemma 1 below, whose proof is given in Appendix B, provides (in)equalities
relating the quantities defined thus far.

###### Lemma 1

For all ${q}\in(0,1)$, we have

$\displaystyle f(d)\geq{P(+,{q})}>{P(-,{q})}={Q(-,{q})}>{Q(+,{q})}\geq f(0),$
(8) $\displaystyle{\nabla({q})}=\frac{{q}}{1-{q}}{\Delta({q})},$ (9)
$\displaystyle
1\geq{P_{\min}({q})}\geq\max\left\\{{\Delta({q})},{\nabla({q})}\right\\}.$
(10)

  5. 5.

Test participation parameter: It also helps to define the test participation
parameter ${m}$ as in (11) below.

${m}:=\frac{8.32{P_{\min}({q})}}{\left({\Delta({q})}\right)^{2}}\log\left(\frac{2n}{\varepsilon}\right).$
(11)

As shown in Lemma 4 in Section VI-A, with high probability each item in ${\cal
N}$ participates in at least ${m}$ tests. Correspondingly, we define the test
participation parameter ${s}$ as below.

${s}:=\frac{8.32{P_{\min}({q})}}{\left({\nabla({q})}\right)^{2}}\log\left(\frac{2n}{\varepsilon}\right).$
(12)

Also, as shown in Lemma 6 in Section VI-A, with high probability each item in
${\cal N}$ participates in at most $T-{s}$ tests.

  6. 6.

Number of tests: Finally, we set the number of tests as any integer $T$ such
that

$\displaystyle T\geq{{\Gamma}({q})}:=\frac{13(1-{q})}{3{q}}{m},$ (13)

e.g., we can set $T=\lceil{{\Gamma}({q})}\rceil$.

  7. 7.

Choice of ${q}$: One wishes to choose ${q}$ such that the defective set ${\cal
D}$ can be reliably recovered while minimizing the required number of tests.
As shown in Section VI-A, for all ${q}\in(0,1)$, ${{\Gamma}({q})}$ tests of
the above design can reliably recover the defective set ${\cal D}$. Therefore
we should choose ${q}$ as the value in $(0,1)$ that minimizes
${{\Gamma}({q})}$. However, such a minimizing ${q}$ is hard to analyze and
analytically characterize. Instead, we consider the quantity
${\hat{\Gamma}}({q})$ defined as

${\hat{\Gamma}}({q}):=\frac{{{\Gamma}({q})}}{{P_{\min}({q})}}=\frac{36.06(1-{q})}{{q}({\Delta({q})})^{2}}\log\left(\frac{2n}{\varepsilon}\right).$
(14)

The equality in (14) follows by using (11) and (13). Note that
${\hat{\Gamma}}({q})\geq{{\Gamma}({q})}$ for all ${q}\in(0,1)$ since
${P_{\min}({q})}\leq 1$ by (10), and hence an upper bound on
${\hat{\Gamma}}({q})$ is also an upper bound for ${{\Gamma}({q})}$. We will
choose ${q}$ as

${{q}^{*}}:=\operatorname*{argmin}_{{q}\in(0,1)}\frac{36.06(1-{q})}{{q}({\Delta({q})})^{2}}\log\left(\frac{2n}{\varepsilon}\right).$
(15)

It turns out such a ${{q}^{*}}$ can be efficiently characterized – see Theorem
1-c) for details.

Decoding rules: We are now ready to describe our two decoding rules, each of
which proceeds by separately estimating whether or not each item $i\in{\cal
N}$ is defective or not (instead of jointly estimating the (non)-defective
status of all $i$ simultaneously). Note that both decoding rules work for all
${q}\in(0,1)$. However, as we will elaborate in Section VI-A that, the first
rule requires fewer tests for $(1-\varepsilon)$-reliable recovery when
${q}\in(0,1/2]$, whereas the second rule requires fewer tests for
$(1-\varepsilon)$-reliable recovery when ${q}\in(1/2,1)$. Hence we use
decoding rule $1$ if ${q}\leq\frac{1}{2}$, and decoding rule $2$ otherwise.

Decoding Rule 1: The first decoding rule makes use of the tests that each item
participates in. More precisely, denote by ${{m}_{i}}$ the number of tests
that item $i$ participates in, and denote by ${{m}_{i}^{+}}$ (respectively
${{m}_{i}^{-}}$) the number of tests with positive (respectively negative)
outcome within these ${{m}_{i}}$ tests. We then classify $i$ as follows:

$i=\left\\{\begin{array}[]{ll}\text{non-
defective}&\text{if}\;\frac{{{m}_{i}^{+}}}{{{m}_{i}}}\leq\frac{{P(-,{q})}+{P(+,{q})}}{2},\\\
\text{defective}&\text{if}\;\frac{{{m}_{i}^{+}}}{{{m}_{i}}}>\frac{{P(-,{q})}+{P(+,{q})}}{2}.\end{array}\right.$
(16)

Decoding Rule 2: In contrast, the second decoding rule makes use of the tests
that do not include the item. More precisely, let ${{s}_{i}}$ denote the
number of tests that item $i$ is excluded from, and let ${{s}_{i}^{+}}$
(respectively ${{s}_{i}^{-}}$) denote the number of tests with positive
(respectively negative) outcome within these ${{s}_{i}}$ tests. We then
classify $i$ as follows:

$i=\left\\{\begin{array}[]{ll}\text{non-
defective}&\text{if}\;\frac{{{s}_{i}^{+}}}{{{s}_{i}}}>\frac{{Q(-,{q})}+{Q(+,{q})}}{2},\\\
\text{defective}&\text{if}\;\frac{{{s}_{i}^{+}}}{{{s}_{i}}}\leq\frac{{Q(-,{q})}+{Q(+,{q})}}{2}.\end{array}\right.$
(17)

##  IV Main Results

As described in this Section, we have four main results, corresponding
respectively to an an upper bound on the number of tests required for
$(1-\varepsilon)$-reliable recovery via the test-design/decoder proposed in
Section III, an information-theoretic lower bound on the number of tests
required by any non-adaptive test-design/decoder guaranteeing
$(1-\varepsilon)$-reliable recovery, a comparison between our algorithmic
upper bound and our information-theoretic lower bound, and an algorithm for
estimating the exact number of defectives.

###  IV-A Achievability/Upper bound

Before stating our achievability, it is useful to define the “sensitivity
parameter” ${H(f)}$ of a given monotone test function $f(\cdot)$. This
sensitivity parameter, in a certain manner, measures the “fastest rate of
change” of $f(\cdot)$, maximized over all intervals $[{L},{U}]\subseteq[0,d]$.

###### Definition 8

Sensitivity parameter: Given a monotone test function $f(\cdot)$, its
sensitivity parameter ${H(f)}$ is defined as

$\displaystyle{H(f)}:=\min_{0\leq{L}<{U}\leq
d}\left(\frac{1}{\min\left\\{{U}-{L},\sqrt{{L}+1},\sqrt{d-{U}+1}\right\\}}\times\frac{{U}-{L}}{f({U})-f({L})}\right)^{2}.$
(18)

Here the $\frac{{U}-{L}}{f({U})-f({L})}$ term bounds the inverse slope of the
test function $f(\cdot)$ in the region $[{L},{U}]$, and the

$\min\left\\{{U}-{L},\sqrt{{L}+1},\sqrt{d-{U}+1}\right\\}$

term is an amortization factor that, at a high level, relates to the standard
deviation of $f(\cdot)$ w.r.t. a certain hypergeometric distribution in that
interval.

Further, for any monotone test function $f(\cdot)$, Lemma 2 below (whose proof
may be found in Appendix A) bounds the sensitivity parameter ${H(f)}$ of
$f(\cdot)$, and asserts ${H(f)}\in{\cal O}\left(d^{1+o(1)}\right)$.

###### Lemma 2

For any monotone test function $f(\cdot)$ and $d\geq 2$, we have555For $d=1$,
we directly have ${H(f)}=\frac{1}{\left(f(d)-f(0)\right)^{2}}$ by definition.

$\displaystyle\frac{1}{\left(f(d)-f(0)\right)^{2}}\leq{H(f)}\leq\frac{16}{\left(f(d)-f(0)\right)^{2}}\left(\log\log
d+2\right)^{2}d.$ (19)

While the bounds in Lemma 2 hold universally for any monotone $f(\cdot)$, the
upper bound in (19) may be unduly pessimistic. For instance, for any
$w\in[0,1]$, consider the natural class of test functions for which the slope
is $\frac{1}{d^{w}}$. Namely:

###### Example 1

Let the test function $f(\cdot)$ be defined as

$f(x)=\left\\{\begin{array}[]{ll}\frac{x}{d^{w}}&x\in\left[0,d^{w}\right]\cap\mathbb{Z}^{+},\\\
1&\text{otherwise},\end{array}\right.$ (20)

For such $f(\cdot)$, one can see that ${H(f)}\in{\cal O}\left(d^{w}\right)$,
for instance by choosing ${L}=\left\lfloor\frac{d^{w}}{3}\right\rfloor$ and
${U}=\left\lceil\frac{2d^{w}}{3}\right\rceil$.

With the definition of ${H(f)}$ and the corresponding bounds at hand, we can
now state our main achievability result, including the computation of the test
design parameter ${{q}^{*}}$ in (15).

###### Theorem 1

The non-adaptive test design and decoding outlined in Section III has the
following performance:

  1. a)

The probability of error is at most $\varepsilon$;

  2. b)

The number of tests $T$ satisfies

$\displaystyle T\leq
376017{P_{min}({{q}^{*}})}{H(f)}d\log\left(\frac{2n}{\varepsilon}\right)+1\leq
376017{H(f)}d\log\left(\frac{2n}{\varepsilon}\right)+1;$ (21)

  3. c)

The test design parameter ${{q}^{*}}$ in (15) can be efficiently approximated
in ${\cal O}(d^{7}\log^{2}(d))$ time;

  4. d)

The computation complexity of decoding is ${\cal
O}\left(n{H(f)}d\log\left(\frac{n}{\varepsilon}\right)\right)$.

Proofs of each part of Theorem 1 may be found in consecutive sub-sections in
Section VI.

###### Remark 1

Our current method of finding an appropriate ${{q}^{*}}$ is via a brute-force
method, hence the somewhat high computational complexity of ${\cal
O}(d^{7}\log^{2}(d))$ (though it is the one-time cost of designing our
algorithm parameters, rather than the many-time cost of decoding). We are
currently exploring methods to choose ${{q}^{*}}$ with lower computational
complexity.

###### Remark 2

Due to Lemma 2, Theorem 1 guarantees that our scheme requires at most ${\cal
O}\left(d^{2+o(1)}\log\left(\frac{n}{\varepsilon}\right)\right)$ tests for
$(1-\varepsilon)$-reliable recovery. However, as noted in Example 1, the
universal bound on ${H(f)}$ presented in Lemma 2 may be loose – for the class
of test functions in Example 1, the number of tests required by our scheme
actually scales as ${\cal
O}\left(d^{1+w}\log\left(\frac{n}{\varepsilon}\right)\right)$.

###  IV-B Converse/Lower bound

To complement our achievability result in Theorem 1, we also present an
information-theoretic lower bound on the number of tests required by any non-
adaptive group testing algorithm that has a probability of error of at most
$\varepsilon$. To this end, it is useful to define the “concentration
parameter” ${h(f)}$ of a given monotone function $f(\cdot)$. This definition
parallels (but is distinct from) the definition of ${H(f)}$ in the previous
Section IV-A) – it may be thought of as a measure of concentration of
$f(\cdot)$ under hypergeometric sampling.

Note that for a pool size of ${\chi}$, the quantities ${\mu}({\chi})$ and
${\sigma^{2}}({\chi})$, defined respectively as

$\displaystyle{\mu}({\chi})$
$\displaystyle\coloneqq\sum\limits_{{a}=0}^{d}\frac{\binom{d}{{a}}\binom{n-d}{{\chi}-{a}}}{\binom{n}{{\chi}}}f({a}),$
(22) $\displaystyle{\sigma^{2}}({\chi})$
$\displaystyle\coloneqq\sum\limits_{{a}=0}^{d}\frac{\binom{d}{{a}}\binom{n-d}{{\chi}-{a}}}{\binom{n}{{\chi}}}(f({a})-{\mu}({\chi}))^{2},$

correspond respectively to (the hypergeometrically weighted) mean and variance
of the measurement function $f(\cdot)$, given that the pool-size is ${\chi}$.
That is, conditioned on choosing a random pool of size ${\chi}$, these are the
mean and variance of the test positivity probability.

###### Remark 3

We have $f(0)\leq{\mu}({\chi})\leq f(d)$ by the monotonicity of $f(\cdot)$.

###### Definition 9

For test function $f(\cdot)$ and ${\chi}\in\\{0,1,\dots,n\\}$, we define the
concentration parameter ${h(f)}$ of $f(\cdot)$ as

$\displaystyle{h(f)}:=\min_{{\chi}\in\\{1,\dots,n-1\\}}\frac{{\mu}({\chi})\left(1-{\mu}({\chi})\right)}{{\sigma^{2}}({\chi})},$
(23)

We are now in a position to state our main converse/impossibility result
(whose proof can be found in Section VII ) as follows:

###### Theorem 2

For any non-adaptive group testing algorithm that ensures a reconstruction
error of at most $\varepsilon$, the number of tests $T$ must satisfy

$T\geq\frac{1}{\log e}{h(f)}\left((1-\varepsilon)\log\binom{n}{d}-1\right).$
(24)

###### Remark 4

Note also that for any test function ${h(f)}\geq 1$. This is because $f(a)\leq
1$ for all $a$, so using the identity
$(f({a})-{\mu}({\chi}))^{2}=f^{2}({a})+{\mu}^{2}({\chi})-2f({a}){\mu}({\chi})$,
we have that for all ${\chi}$,

$\displaystyle{\sigma^{2}}({\chi})=\sum\limits_{{a}=0}^{d}\frac{\binom{d}{{a}}\binom{n-d}{{\chi}-{a}}}{\binom{n}{{\chi}}}f^{2}({a})-{\mu}^{2}({\chi})\leq\sum\limits_{{a}=0}^{d}\frac{\binom{d}{{a}}\binom{n-d}{{\chi}-{a}}}{\binom{n}{{\chi}}}f({a})-{\mu}^{2}({\chi})={\mu}({\chi})\left(1-{\mu}({\chi})\right).$

Hence the lower bound in (24) scales as $\Omega\left(\log\binom{n}{d}\right)$,
which in turns scales as $\Omega\left(d\log\left(\frac{n}{d}\right)\right)$.
However, as noted in Section IV-C (see Corollary 1.c) below), the bound
${h(f)}\geq 1$ is in general loose – there exist test functions for which
${h(f)}$ can be as large as $\Omega(d)$. Hence, due to the ${h(f)}$ term in
(24), this impossibility result may scale as
$\Omega\left(d^{2}\log\left(\frac{n}{d}\right)\right)$, which is a strict
tightening of the information-theoretic lower bounds
$\Omega\left(d\log\left(\frac{n}{d}\right)\right)$ extant in the literature
(see for instance [27]).

###  IV-C Comparison between upper and lower bounds

Comparing the lower bound in (24) with the upper bound in (21), we note that
their ratio scales order-wise as $\frac{{H(f)}}{{h(f)}}$. Corollary 1 below
(whose proof may be found in Appendix K) demonstrates that for a variety of
test functions in the literature
$\frac{{H(f)}}{{h(f)}}\in\Theta\left(1\right)$. Thus, our bounds are order-
wise tight for those test functions.

###### Corollary 1

Consider the sparse regime $d=n^{\theta},0\leq\theta<1$.

  1. a)

For the classical group testing measurement function $f(\cdot)$ given in (1),
both the ${H(f)}$ and ${h(f)}$ functionals equal $1$, enabling us to recover
the well-known fact (see for instance [27]) that the sample-complexity of
classical group-testing is $\Theta(d\log n)$

  2. b)

For the threshold test function, i.e., for some $\ell\in\\{0,\dots,d-1\\}$,

$f(x)=\left\\{\begin{array}[]{ll}0&\text{if}\;x\leq{\ell},\\\
1&\text{if}\;x>{\ell},\end{array}\right.$ (25)

both the upper bound on the number of tests required for
$(1-\varepsilon)$-reliable recovery in Theorem 1 and the corresponding lower
bound in Theorem 2 scale as $\Theta\left(d\log n\right)$. To the best of our
knowledge this is the first order-wise tight characterization of the optimal
sample-complexity of threshold group testing.

  3. c)

For the “linear” test function, i.e.,

$f(x)=\frac{x}{d},\quad x\in\\{0,\dots,d\\},$ (26)

the upper bound on the number of tests required for $(1-\varepsilon)$-reliable
recovery in Theorem 1 matches (order-wise) the lower bound in Theorem 2, both
scaling as $\Theta\left(d^{2}\log n\right)$. Hence, by Lemma 2, this test
function is essentially extremal in its sample complexity.

For general (near-noiseless) monotone test functions $f(\cdot)$, while we are
not able to show that the sample-complexities in Theorems 1 and 2 match up to
constant factors, we nonetheless show in Theorem 3 below (for which a proof
may be found in Section VIII) that they match up to a ${\cal
O}\left(\frac{{P_{min}({{q}^{*}})}}{{\mu}({\chi}^{*})\left(1-{\mu}({\chi}^{*})\right)}\right)$
factor. Here ${\chi}^{*}$ denotes an optimal solution to (23), i.e.,

$\displaystyle{\chi}^{*}$
$\displaystyle\coloneqq\operatorname*{argmin}_{{\chi}\in\\{1,\dots,n-1\\}}\frac{{\mu}({\chi})(1-{\mu}({\chi}))}{{\sigma^{2}}({\chi})}$
(27)

is the pool-size minimizing
$\frac{{\mu}({\chi})\left(1-{\mu}({\chi})\right)}{{\sigma^{2}}({\chi})}$.

###### Theorem 3

In the sparse regime $d=n^{\theta},0\leq\theta<1$, the number of tests
required in Theorem 1 is no more than a ${\cal
O}\left(\frac{{P_{min}({{q}^{*}})}}{{\mu}({\chi}^{*})\left(1-{\mu}({\chi}^{*})\right)}\right)$
factor larger than the lower bound presented in Theorem 2. In particular, the
number of tests required in Theorem 1 is never more than a ${\cal
O}\left(d^{1+o(1)}\right)$ factor larger than the information-theoretic lower
bound in Theorem 2.

Using Theorem 3, we show in Corollary 2 below (whose proof is in Appendix L)
that for any noisy test function our non-adaptive scheme is indeed order-wise
optimal.

###### Corollary 2

In the sparse regime $d=n^{\theta},0\leq\theta<1$, the upper and lower bounds
are order-wise tight for all noisy test functions.

Indeed, we present the following conjecture, whose positive resolution would
tightly characterize the order-wise sample-complexity for any monotone test
function.

###### Conjecture 1

We conjecture that for any monotone test function $f(\cdot)$,
$\frac{\min_{{q}\in(0,1)}{{\Gamma}({q})}}{{h(f)}d\log n}\in\Theta(1)$.

###  IV-D Estimating the Exact Number of Defectives

As highlighted in Section III, our algorithms depend critically on the
assumption that the number of defectives $d$ is known a priori. Moreover,
different from the classical group-testing in which most algorithms are robust
to small perturbations in the value of $d$, our algorithms require the exact
value of $d$. If the value of $d$ is not available, which is likely to be the
case in practice, it will be useful to have an algorithm for exactly
estimating this. In Appendix M, we develop such an algorithm, whose
performance is summarized in the following result.

###### Lemma 3

For any fixed ${\varepsilon}\in(0,1)$, there exists an adaptive algorithm that
outputs the exact value of $d$ with probability at least $1-{\varepsilon}$,
using ${\cal O}\left(\left({H(f)}d\right)^{2}\log d\log\left(\frac{\log
n}{{\varepsilon}}\right)\right)$ tests, where ${H(f)}$ is the sensitivity
parameter (18). Moreover, it uses at most $2\log(2d)$ stages of adaptivity.

The idea of the algorithm may be found in Section V. The details are given in
Appendix M.

Comparing Lemma 3 with Theorem 1, we see the number of tests required by our
algorithm for estimating $d$ is about a ${\cal O}({H(f)}d)$ factor larger than
the number of tests required by our algorithm for estimating ${\cal D}$,
because we need an exact estimate of $d$. Therefore, as future work we are
exploring algorithms which can estimate the set ${\cal D}$ even when $d$ is
only known up to a (small) multiplicative factor.

##  V Intuition and Proof Sketches

We give here some high-level intuition behind our main results and provide
corresponding proof sketches. For readers’ convenience, we also provide a
road-map of the intermediate results leading to our main results in Figs. 1
and 2.

Lemma 2Bounds on sensitivity parameter ${H(f)}$(Appendix A)Theorem 1Validity
and performance of algorithm (Section VI)Theorem 1-a)Upper bound on error
(Section VI-A)Theorem 1-b)Upper bound on $T$(Section VI-B)Theorem
1-c)Complexity to approximate ${{q}^{*}}$(Section VI-C)Proposition 1Decoding
rule (16) (Section VI-A1)Proposition 2Decoding rule (17) (Section
VI-A2)Proposition 3Upper bound on ${\hat{\Gamma}}({{q}^{*}})$for
$0\leq{L}<{U}\leq d$(Appendix D)Proposition 5Upper bound on
${\hat{\Gamma}}({{q}^{*}})$for $1\leq{L}<{U}\leq d-1$(Appendix E) Proposition
6Upper bound on ${\hat{\Gamma}}({{q}^{*}})$for boundary points (Appendix D)
Lemmas 4, 5W.H.P. $i$ in ${{m}_{i}}\geq{m}$ tests W.H.P.
$\hat{\mathcal{D}}=\mathcal{D}$ given ${{m}_{i}}\geq{m},\forall i$(Appendices
-1, -2)Lemmas 6, 7W.H.P. $i$ not in ${{s}_{i}}\geq{s}$ tests W.H.P.
$\hat{\mathcal{D}}=\mathcal{D}$ given ${{s}_{i}}\geq{s},\forall i$(Appendices
-3, -4)Lemma 1Relationship between ${\Delta({q})}$ and
${\nabla({q})}$(Appendix B)Lemma
1${P(+,{q})}\geq{P(-,{q})}={Q(-,{q})}\geq{Q(+,{q})}$$1\geq{P_{\min}({q})}\geq\max\left\\{{\Delta({q})},{\nabla({q})}\right\\}$(Appendix
B) Lemma 12Involved upper bound on ${\hat{\Gamma}}({{q}^{*}})$for
$1\leq{L}<{U}\leq d-1$(Appendix F) Lemmas 13, 14, 15Properties of
$({{\lambda}_{{i}}},{{\lambda}_{{i}+1}})$(Appendix E) Lemmas 17, 18Saddle-
point approximation (Appendices F)Lemmas 16Stirling approximation (Appendices
F)Lemmas 8Bound on ${{q}^{*}}$(Appendix G) Lemma 9Upper bound on
${{\Gamma}({q})}$ for ${q}$ that is close to ${{q}^{*}}$(Appendix H)

Figure 1: Organization of Propositions, Lemmas, and Theorems for our proof of
achievability. Theorem 1-b)Upper bound on $T$(Section VI-B) Theorem 2Lower
bound on $T$(Section VII) Theorem 3Near-optimality (Section VIII) Proposition
4Existence of proper $({\hat{L}},{\hat{U}})$(Section VIII) Lemma 10Bound on
the mutual information of each test (Appendix I) Lemma 11Existence of a
“large-increment-interval” (Appendix J) Lemma 19Perturbation inequality on
$x\ln(x)$(Appendix I)  Figure 2: Organization of Propositions, Lemmas, and
Theorems for our proof of converse and its tightness. Parameters in the
Problem Formulation
---
${\cal N}$ | The set of all items.
$n$ | The total number of items, and $n=|{\cal N}|$.
${\cal D}$ | The unknown subset of defective items, distributed uniformly at random over all $\binom{n}{d}$ sets of size $d$.
$d$ | The number of defective items, with $d=|{\cal D}|$.
$f(\cdot)$ | The test function, a monotone function indicating the probability $f(x)$ that a test pool with $x$ defectives has a positive test outcome.
$\varepsilon$ | The pre-specified upper bound on the probability of incorrect reconstruction of ${\cal D}$.
$T$ | The number of tests.
Test Design and Decoding Parameters
${\boldsymbol{M}}$ | The $T\times n$ binary test matrix: $M_{ji}=1$ if item $i$ is in test $j$; $M_{ji}=0$ otherwise.
${q}$ | Probability with which each element in ${\boldsymbol{M}}$ is chosen as $1$ in an i.i.d. manner.
${P(-,{q})}$ | The probability that a test containing $i$ has a positive outcome when $i$ is non-defective, as defined in (4).
${P(+,{q})}$ | The probability that a test containing $i$ has a positive outcome when $i$ is defective, as defined in (4).
${Q(-,{q})}$ | The probability that a test excluding $i$ has a positive outcome when $i$ is non-defective, as defined in (5).
${Q(+,{q})}$ | The probability that a test excluding $i$ has a positive outcome when $i$ is defective, as defined in (5).
${\Delta({q})}$,${\nabla({q})}$ | The difference of test-positivity probability conditioned on item $i$ being defective or not, as defined in (6).
${P_{\min}({q})}$ | Minimal test sensitivity, as defined in (7).
${m}$, ${s}$ | Test participation parameter such that one item is included in $[{m},T-{s}]$ tests with high probability, as defined in (11) and (12).
${{\Gamma}({q})}$ | The number of tests required in our algorithm, as defined in (13).
${\hat{\Gamma}}({q})$ | As defined in (14), an upper bound on ${{\Gamma}({q})}$ that is easier to analyze and optimize than ${{\Gamma}({q})}$.
${{q}^{*}}$ | The parameter that minimizes ${\hat{\Gamma}}({q})$, as defined in (15) – it can be efficiently approximated by Theorem 1-c).
Parameters in the Achievability/Theorem 1
${H(f)}$ | The sensitivity parameter (as defined in (18)) which helps bound $T$ from above in Theorem 1-b) and is bounded in Lemma 2.
${\Gamma}_{1}({q})$ | The number of tests required by Decoding Rule 1 in (16), as defined in (28).
${\Gamma}_{2}({q})$ | The number of tests required by Decoding Rule 2 in (17), as defined in (29).
${\hat{{q}}^{*}}$ | Any ${q}$ that is “close enough” to ${{q}^{*}}$ – the corresponding ${{\Gamma}({q})}$ can be bounded by $\Theta({\Gamma}({{q}^{*}}))$ in Lemma 9.
${\hat{{q}}}$ | An approximation to ${{q}^{*}}$.
${\alpha}$ | A useful parameter w.r.t. ${L}^{\prime}$ and ${U}^{\prime}$ in the saddle-point approximation in Lemma 18, defined as $\frac{1}{2}\min\left\\{{U}^{\prime}-{L}^{\prime},\sqrt{{L}^{\prime}},\sqrt{d-{U}^{\prime}}\right\\}$.
${\beta}$ | The minimum term in ${H(f)}$ w.r.t. ${L}$ and ${U}$, as defined in (119).
Parameters in the Converse/Theorem 2
${\chi}$ | The pool size.
${\mu}({\chi})$,${\sigma^{2}}({\chi})$ | The mean and variance of the test positivity probability, given that the pool size is ${\chi}$.
${h(f)}$ | The concentration parameter (as defined in (23)) which helps bound $T$ from below in Theorem 2.
${\chi}^{*}$ | The pool size that minimizes $({\mu}(1-{\mu}))/{\sigma^{2}}$, as defined in (27).
$\boldsymbol{{X}}$ | The length-$n$ binary vector that is a weight $d$ vector representing the locations of the defective set ${\cal D}$.
$\boldsymbol{{Y}}$ | The length-$T$ binary vector representing the outcome of each test.
$\boldsymbol{{Z}}$ | The length-$T$ vector representing the number of defectives in each test.
$\boldsymbol{{\hat{X}}}$ | The length-$n$ binary vector representing the estimated locations of the defective set ${\cal D}$.
Tightness Parameters/Theorem 3
${\vartheta}$ | The expected number of defectives in a test of pool size ${\chi}^{*}$, as defined in (47).
$({\hat{L}},{\hat{U}})$ | A pair of parameters for ${H(f)}$ such that ${H(f)}$ is upper bounded by $\Theta(1/{\sigma^{2}}({\chi}^{*}))$.
${\eta}$ | The closest integer to ${\vartheta}$, as defined in (50), which is one of the pair $({\hat{L}},{\hat{U}})$.
${\kappa}$ | The other one of the pair $({\hat{L}},{\hat{U}})$, whose existence is proved in Lemma 11.
${\gamma}(\cdot)$ | A parameter similar to ${\beta}$ defined as ${\gamma}({\kappa}):=\min\left\\{|{\kappa}-{\vartheta}|,\sqrt{{\kappa}+1},\sqrt{d-{\kappa}+1},\sqrt{{\vartheta}+1},\sqrt{d-{\vartheta}+1}\right\\}$.
TABLE I: Table of frequently used notation.

A. Achievability/Theorem 1: As noted in Section III we use a Bernoulli test
design, where each item participates in a test in an i.i.d. manner with
probability ${q}$. Both of our two decoding rules, specified in (16) and (17),
proceed by classifying each item $i\in\\{1,\ldots,n\\}$ as defective or non-
defective independently of any other item.

In particular, Decoding Rule $1$, specified in (16), proceeds as follows. For
any test including item $i$, we denote by ${P(-,{q})}$ the probability of
having a positive outcome if item $i$ is non-defective and by ${P(+,{q})}$ if
item $i$ is defective. Due to the monotonicity of our test function
$f(\cdot)$, ${P(+,{q})}>{P(-,{q})}$. By the law of large numbers, when item
$i$ participates in a large enough number of tests, the fraction of positive-
outcome tests converges to either ${P(-,{q})}$ or ${P(+,{q})}$ depending on
whether the item is non-defective or defective respectively. Therefore,
decoding rule (16) proceeds by classifying $i$ as defective or not by checking
that the fraction of positive test outcomes is closer to ${P(+,{q})}$ or
${P(-,{q})}$.

Analogously, Decoding Rule 2 specified in (17) is similar, but now makes use
of the tests not including item $i$, with ${Q(-,{q})}$ denoting the
probability of having a positive outcome if item $i$ is non-defective, and
${Q(+,{q})}$ denoting the corresponding probability if item $i$ is defective.
As above, due to the monotoncity of $f(\cdot)$, ${Q(-,{q})}>{Q(+,{q})}$. The
fraction of positive-outcome tests converges to ${Q(-,{q})}$ and ${Q(+,{q})}$,
respectively, and $i$ is classified according to which fraction is closer.

The reason we have two different decoding rules is since, as shown in Fig. 3
when ${q}\in(0,1/2]$, the first rule requires fewer tests than the second does
for $(1-\varepsilon)$-reliable recovery, with the situation reversed in
${q}\in(1/2,1)$.

$\bullet$ Lemma 2 – ${H(f)}$: Lemma 2, whose proof can be found in Appendix A,
helps provide a universal bound on the the sensitivity parameter for any
monotone function $f(\cdot)$.

In order to simplify the
$\min\left\\{{U}-{L},\sqrt{{L}+1},\sqrt{d-{U}+1}\right\\}$ term, we first
split our analysis into two cases, corresponding to the scenarios
$f\left(\left\lceil d/2\right\rceil\right)\geq(f(0)+f(d))/2$ and
$f\left(\left\lceil d/2\right\rceil\right)<(f(0)+f(d))/2$ – we choose ${L}$
and ${U}$ from $[0,d/2]$ or $(d/2,d]$ accordingly. This enables us to argue
that only one of $\sqrt{{L}+1}$ and $\sqrt{d-{U}+1}$ is active in the
$\min\left\\{{U}-{L},\sqrt{{L}+1},\sqrt{d-{U}+1}\right\\}$ term, simplifying
our argumentation. We focus on the first case – the proof of the second case
is analogous. Considering any ${\upsilon}\in(0,1]$ and
${k}=\lceil\log(1/{\upsilon})+1\rceil$, we construct a sequence
$\\{{S}_{{i}}\\}$ with ${k}+1$ elements such that
$\frac{{S}_{{i}+1}^{2}}{{S}_{i}+1}\leq 2d^{1+{\upsilon}}$ for all ${i}$. We
then argue that there exists two adjacent elements ${S}_{\ell}$ and
${S}_{{\ell}+1}$ such that
$f({S}_{{\ell}+1})-f({S}_{{\ell}})\geq(f(d)-f(0))/2{k}$. Finally, using the
definition of ${H(f)}$ in (18) with ${L}={S}_{{\ell}}$ and
${U}={S}_{{\ell}+1}$ and letting ${\upsilon}=1/\log d$, one can prove Lemma 2.

$\bullet$ Theorem 1.a) – Probability of error:  We first collect various
inequalities relating quantities such as ${P(+,{q})}$, ${P(-,{q})}$,
${Q(+,{q})}$, ${Q(-,{q})}$, etc, in Lemma 1, whose proof may be found in
Appendix B. With these relations at hand, the probability of error of these
two decoding rules can be analyzed via standard concentration inequalities,
collected in Appendix C.

In particular Proposition 1, posits that for Decoding Rule 1,
$T\geq\frac{13}{6{q}}{m}$ tests allow for $(1-\varepsilon)$-reliable recovery
of the set of ${\cal D}$ of defectives. This is proved in two steps. First, in
Lemma 4, we compute the probability that an arbitrary item participates in
less than ${m}$ tests, which, by using the Chernoff bound [28], is no larger
than $\frac{\varepsilon}{2n}$. Second, conditioning on the event that each
item participates in at least ${m}$ tests, in Lemma 5 we compute the
probability of misidentification (either false alarm or missed detection).
Using the Chernoff bound, this probability is again no larger than
$\frac{\varepsilon}{2n}$. Combining these two parts with a union bound yields
Proposition 1.

Proposition 2 similarly analyzes Decoding Rule 2 – here we show that
$T\geq\frac{13}{6(1-{q})}{s}$ tests allow for $(1-\varepsilon)$-reliable
recovery of the set of ${\cal D}$ of defectives. This is proved in a similar
manner to Proposition 1. In Lemma 6, we compute the probability that an
arbitrary item participates in more than $T-{s}$ tests is no larger than
$\frac{\varepsilon}{2n}$. Then, conditioning on the event that each item
participates in at most $T-{s}$ tests, in Lemma 7 we compute the probability
of misidentification (either false alarm or missed detection) is again no
larger than $\frac{\varepsilon}{2n}$. Taking the union bound over these two
parts gives us Proposition 2.

Next, we compare the number of tests required by the two decoding rules. This
is accomplished by using the identity
${\nabla({q})}=\frac{{q}}{1-{q}}{\Delta({q})}$ shown in Lemma 1. With this
identity, we argue that $T$ tests in (13) suffice.

$\bullet$ Theorem 1.b) – Bound on $T$:  The number of tests chosen in (13) as
$\lceil{{\Gamma}({q})}\rceil$ suffices to ensure $(1-\varepsilon)$-reliable
recovery, but it is not immediately apparent how this quantity relates to the
bound claimed in (21). As a simplifying first step, as noted in the text
surrounding (14), instead of bounding ${{\Gamma}({q})}$ directly, we bound
instead ${\hat{\Gamma}}({q})=\frac{{{\Gamma}({q})}}{{P_{\min}({q})}}$ – since
${P_{\min}({q})}\leq 1$ (see Lemma 1) this suffices to give an upper bound on
$T$ allowing $(1-\varepsilon)$-reliable recovery.

Perhaps the most technically involved part of our work focuses on providing a
reasonably tight upper bound – as accomplished in Proposition 3 – on
${\hat{\Gamma}}({{q}^{*}})$ in terms of the sensitivity parameter ${H(f)}$
defined in Definition 8.

Before discussing Proposition 3 in the context of general monotone functions,
consider first the example of the threshold group-testing function described
in (25) (corresponding to negative test outcomes if there are at most ${\ell}$
defectives in a pool). Intuitively speaking, for accurately classifying each
item, we should choose some $q$ such that the gap
${\Delta({q})}={P(+,{q})}-{P(-,{q})}$ is “large” (bounded away from $0$). This
can also be seen from (14), wherein to minimize ${\hat{\Gamma}}({q})$, we
would like ${\Delta({q})}$ to be as large as possible. For the threshold group
testing scenario, if we choose ${q}={\ell}/d$, then on the one hand if an item
$i$ is non-defective the expected number defectives in a pool is ${\ell}$; and
on the other hand if item $i$ is defective the expected number of defectives
is $\frac{{\ell}}{d}(d-1)+1\approx{\ell}+1$, and hence the gap ${\Delta({q})}$
in test positivity is about as large as can be hoped for – one can see that
choices of $q$ signficantly larger or smaller than this would result in a
smaller gap ${\Delta({q})}$.

For a general test function $f(\cdot)$, the gap ${\Delta({q})}$ can be
regarded as the “binomially-weighted mean of the increment” of $f(\cdot)$ (see
(83) for the precise expression). To make ${\Delta({q})}$ larger, we should
attempt to assign a larger weight to a carefully chosen region “large-
increment-interval” $[{L},{U}]$ where $f(\cdot)$ exhibits a large increment.

More precisely, for general test functions $f(\cdot)$ our pathway to proving
Proposition 3 relies on bounding the integral of ${\Delta({q})}$ from ${L}/d$
to ${U}/d$, which, by the mean value theorem, gives a bound on
${\Delta({q}_{0})}$ for some ${q}_{0}\in[{L}/d,{U}/d]$. To this end in Lemmas
17 and 18 we provide a delicate saddle-point-approximation style bound for
$\int_{{L}/d}^{{U}/d}{q}^{j}(1-{q})^{d-j}{\,\mathrm{d}}{q}$. This together
with Stirling’s approximation summarized in Lemma 16 results in Lemma 12,
which almost gets us to Proposition 3, except for two issues.

Firstly, there is a
$\frac{(d-{L}^{\prime}){U}^{\prime}}{(d-{U}^{\prime}){L}^{\prime}}$
multiplicative term that appears in Lemma 12 but not in Proposition 3. Towards
this end, we divide $[{L}^{\prime},{U}^{\prime})$ into suitably small
intervals
$[{{\lambda}_{{i}}},{{\lambda}_{{i}+1}}),\;{i}\in\\{0,\dots,{\tau}-1\\}$. The
intervals are chosen in this manner to satisfy the following two constraints,
which are in tension with each other:

  1. (i)

In Lemma 13 – each ${{\lambda}_{{i}+1}}-{{\lambda}_{{i}}}$ should be larger
than
$\min\\{{U}^{\prime}-{L}^{\prime},\sqrt{{L}^{\prime}},\sqrt{{U}^{\prime}-{L}^{\prime}}\\}$
that appears in the denominator of Lemma 12,

  2. (ii)

In Lemma 14 – each ${{\lambda}_{{i}+1}}-{{\lambda}_{{i}}}$ should also be
small enough so that
$\frac{(d-{{\lambda}_{{i}}}){{\lambda}_{{i}+1}}}{(d-{{\lambda}_{{i}+1}}){{\lambda}_{{i}}}}$
can be bounded from above by a constant.

By substituting ${L}^{\prime}={{\lambda}_{{\ell}}}$ and
${U}^{\prime}={{\lambda}_{{\ell}+1}}$ for a specific ${\ell}$ identified by
the mean value theorem in Lemma 15 allows us to obtain Proposition 5.

Secondly, the “boundary points”, i.e., ${L}=0$ or ${U}=d$, are handled
separately in Proposition 6.

Proposition 3 is then proved by unifying Propositions 5 and 6.

$\bullet$ Theorem 1.c) – Complexity of approximating ${{q}^{*}}$:  A critical
part of our test-design and decoding algorithms is an appropriate choice of
${q}\in(0,1)$. We proceed as follows: we uniformly quantize the interval
$(0,1)$ into $\Theta(d^{4})$ intervals and calculate the corresponding
${{\Gamma}({q})}$ for each ${q}$, and then set ${q}$ to equal the value
${\hat{{q}}}$ that minimizes ${{\Gamma}({q})}$. We then prove that choosing
${q}={\hat{{q}}}$ results in our scheme having similar performance to using
the value ${q}={{q}^{*}}$, i.e.,
${\Gamma({\hat{{q}}})}=\Theta({\Gamma}({{q}^{*}}))$.

To this end, in Lemma 8 we first show that ${{q}^{*}}$ can never be either
“too small” or “too large” – i.e.,
${{q}^{*}}\in\left(\frac{1}{376017d^{3}},1-\frac{1}{376017d^{3}}\right)$.
Next, we prove in Lemma 9 that for all ${\hat{{q}}^{*}}$ that is close enough
to ${{q}^{*}}$, i.e.,
$\left|{\hat{{q}}^{*}}-{{q}^{*}}\right|\leq\frac{1}{376017d^{4}}$, we have
${\Gamma({\hat{{q}}^{*}})}\leq 64e^{2}{\Gamma}({{q}^{*}})$.

$\bullet$ Theorem 1.d) – Complexity of decoding:  Since our decoder only needs
to count the number of tests and tests with positive outcomes that one item is
included in (respectively not included in) and check the ratio via Decoding
Rule 1 in (16) (respectively Decoding Rule 2 in (17)), the computational
complexity of decoding is ${\cal O}(nT)={\cal
O}\left(n{H(f)}d\log\left(\frac{n}{\varepsilon}\right)\right)$.

B. Converse/Theorem 2: The proof of our converse argument, which may be found
in Section VII, proceeds as follows. Let $\boldsymbol{{X}}$ be the input
vector and $\boldsymbol{{Y}}$ be the outcome vector. We decompose the entropy
$H(\boldsymbol{{X}})$ into the conditional entropy term
$H(\boldsymbol{{X}}|\boldsymbol{{Y}})$ and the mutual information
$I(\boldsymbol{{X}};\boldsymbol{{Y}})$. By the assumption that ${\cal D}$ is
uniformly distributed over all $\binom{n}{d}$ size-$d$ subsets of
$\\{1,\ldots,n\\}$, we have $H(\boldsymbol{{X}})=\log\binom{n}{d}$. Using
Fano’s inequality, $H(\boldsymbol{{X}}|\boldsymbol{{Y}})$ can be bounded in
terms of the error probability $\varepsilon$. Following techniques similar to
the channel coding literature (see for instance [29, Sec. 7.3]), one can upper
bound
${I}(\boldsymbol{{X}};\boldsymbol{{Y}})\leq\sum_{i=1}^{T}[{H}({Y}_{i})-{H}({Y}_{i}|{Z}_{i})]$,
where ${{Z}_{i}}$ denotes the number of defectives in the $i$-th pool. One
salient feature of generalized group testing is that the test outcome is no
longer deterministic when given the number of defectives in the test pool.
That is, ${H}({Y}_{i}|{Z}_{i})>0$ and is not negligible. Next (by resorting to
an inequality on the $\ln(\cdot)$ function presented in Lemma 19) in Lemma 10
we bound each
${H}({Y}_{i})-{H}({Y}_{i}|{Z}_{i})\leq\frac{{\sigma^{2}}({\chi}_{i})}{{\mu}({\chi}_{i})(1-{\mu}({\chi}_{i}))}$,
where ${\chi}_{i}$ is the size of the $i$-th pool, ${\mu}({\chi}_{i})$ and
${\sigma^{2}}({\chi}_{i})$ are, respectively, the mean and variance of being
positive. Finally, by optimizing the pool-size parameter ${\chi}$, we prove
the lower bound.

C. Tightness/Theorem 3: To prove the tightness of our achievability and
converse in Theorem 3 (whose proof may be found in Section VIII), we show
there exists a pair of $({\hat{L}},{\hat{U}})$ such that
$\frac{1}{\min\left\\{{\hat{U}}-{\hat{L}},\sqrt{{\hat{L}}+1},\sqrt{d-{\hat{U}}+1}\right\\}}\times\frac{{\hat{U}}-{\hat{L}}}{f({\hat{U}})-f({\hat{L}})}={\cal
O}\left(\frac{1}{\sigma({\chi}^{*})}\right)$. From the definition of
${\chi}^{*}$ in (27), we know that ${\sigma^{2}}({\chi}^{*})$ is “relatively
large”. This implies that $f(\cdot)$ increases rapidly in the region adjacent
to ${\chi}^{*}\frac{d}{n}$ (which quantity equals the expected number of
defectives in the test pool). Therefore it is reasonable to choose
${\chi}^{*}\frac{d}{n}$ as one of the pair $({\hat{L}},{\hat{U}})$. The
existence of the other one is shown in a proof by contradiction in Lemma 11,
making use of the mean and variance formulae for hypergeometric distributions.
Based on Lemma 11, in Proposition 4 we deal with integrality issues and
specify $({\hat{L}},{\hat{U}})$. Finally, invoking Proposition 3 with this
pair of $({\hat{L}},{\hat{U}})$, one can prove Theorem 3.

D. Estimation of $d$/Lemma 3: Let ${\hat{d}}\geq 2$ be a putative number of
defective items. We devise a subroutine which decides whether
$d\leq{\hat{d}}-1$ or $d\geq{\hat{d}}$. The idea of the subroutine is similar
to that of the algorithm for deciding whether an item is defective or not in
Section III. More precisely, in a Bernoulli test design where items are
included with probability ${\zeta}$, denote by ${{P}({\hat{d}},{\zeta})}$
(respectively ${{P}({\hat{d}}-1,{\zeta})}$) the probability of having a
positive outcome if there are ${\hat{d}}$ (respectively ${\hat{d}}-1$)
defectives. By the law of large numbers, when taking a large enough number of
tests, the fraction of positive-outcome tests should be either at least
${{P}({\hat{d}},{\zeta})}$ or at most ${{P}({\hat{d}}-1,{\zeta})}$, depending
on whether there are at least ${\hat{d}}$ defectives or at most ${\hat{d}}-1$
defectives respectively. Therefore, we can reliably estimate whether or not
$d$ exceeds ${\hat{d}}$ by checking the fraction of positive test outcomes. By
an analogous argument to that of Lemma 5, one can bound the probability of
error of the subroutine. By a similar argument to the one in Theorem 1.b), one
can find an upper bound on the number of tests used by the subroutine. Using
this subroutine, we can obtain an exact estimate of $d$ via the following two
steps.

  1. (i)

To obtain an upper bound on $d$, we perform a sequence of subroutines to check
whether $d\leq 2^{i}$ for $i\in\\{1,2,\dots\\}$, until the answer is
affirmative.

  2. (ii)

To find the exact value of $d$, we perform another sequence of subroutines via
a binary search.

##  VI Proof of Theorem 1

###  VI-A Proof of Theorem 1-a)

First, we separately discuss the performance of the decoding rules proposed in
(16) and (17).

####  VI-A1 Performance of Decoding Rule 1 in (16)

###### Proposition 1

Suppose that the decoding rule used is (16). Then we show that the probability
of error is at most $\varepsilon$ if

${T}\geq{\Gamma}_{1}({q}):=\frac{13}{6{q}}{m}.$ (28)

This is proved in two steps. First, we compute the probability that an
arbitrary item participates in less than ${m}$ tests, which can be made
sufficiently small. Second, assuming that each item participates in at least
${m}$ tests, we compute the probability of misidentification, which again can
be made sufficiently small. Formally, we have the following two lemmas, whose
proofs are relegated to Appendices -1 and -2, respectively.

###### Lemma 4

With probability at least $1-\frac{\varepsilon}{2}$ over the test design, each
item $i\in{\cal N}$ participates in at least ${m}$ tests.

###### Lemma 5

Conditioning on the event that each item participates in at least ${m}$ tests,
with probability at least $1-\frac{\varepsilon}{2}$ over the test design, all
items are correctly identified using (16).

Upon combining Lemmas 4 and 5, via the union bound, the probability that all
items are correctly identified is bounded from below by $1-\varepsilon$, which
proves Proposition 1.

####  VI-A2 Performance of Decoding Rule 2 in (17)

###### Proposition 2

Suppose that the decoding rule used is (17). Then we show that the probability
of error is at most $\varepsilon$ if

$T\geq{\Gamma}_{2}({q}):=\frac{13}{6(1-{q})}{s}.$ (29)

Similarly to Proposition 1, this is established by proving the following two
lemmas whose proofs can be found in Appendices -3 and -4.

###### Lemma 6

With probability at least $1-\frac{\varepsilon}{2}$ over the test design, each
item $i\in{\cal N}$ participates in at most $T-{s}$ tests.

###### Lemma 7

Conditioning on the event that each item participates in at most $T-{s}$
tests, with probability at least $1-\frac{\varepsilon}{2}$ over the test
design, all items are correctly identified using (17).

Next, since both decoding rules are applicable to all ${q}\in(0,1)$, we shall
compare the bound given in (28) and (29) and choose the more efficient one,
i.e., the one that has a smaller lower bound on $T$. Using (9) along with (11)
and (12), we have

$\displaystyle\frac{13}{6(1-{q})}{s}$
$\displaystyle=\frac{13}{6(1-{q})}\times\frac{8.32{P_{\min}({q})}}{({\nabla({q})})^{2}}\log\left(\frac{2n}{\varepsilon}\right)$
$\displaystyle=\frac{1-{q}}{{q}}\times\frac{13}{6{q}}\times\frac{8.32{P_{\min}({q})}}{({\Delta({q})})^{2}}\log\left(\frac{2n}{\varepsilon}\right)$
$\displaystyle=\frac{1-{q}}{{q}}\times\frac{13}{6{q}}{m},$

which suggests that the decoding rule (16) is more efficient when ${q}\leq
1/2$, whereas the decoding rule (17) is more efficient when ${q}>1/2$. By
leveraging this observation, we argue that the value given in (13) is always
an upper bound on the minimum of (28) and (29) for all ${q}\in(0,1)$, i.e.,

$\displaystyle\min\left\\{{\Gamma}_{1}({q}),{\Gamma}_{2}({q})\right\\}\leq{{\Gamma}({q})},\forall{q}\in(0,1).$

To see this, when ${q}\leq 1/2$, we have

${\Gamma}_{1}({q})=\frac{13}{6{q}}{m}\leq\frac{13(1-{q})}{3{q}}{m}={{\Gamma}({q})};$

on the other hand, when ${q}>1/2$, we have

${\Gamma}_{2}({q})=\frac{13}{6(1-{q})}{s}=\frac{13(1-{q})}{6{q}^{2}}{m}<\frac{13(1-{q})}{3{q}}{m}={{\Gamma}({q})}.$

This is also illustrated in Fig. 3, where we plot the values of (13), (28) and
(29) as a function of ${q}$.

$0$$0.2$$0.4$$0.6$$0.8$$1$$0$$2$$4$$6$$8$$10$${q}$$\frac{\\#\text{ of
tests}}{\frac{13{m}}{6{q}}}$${\Gamma}_{1}({q})$${\Gamma}_{2}({q})$${{\Gamma}({q})}$
Figure 3: Comparisons of the number of tests defined in (13), (28) and (29).
The black line corresponds to the performance of decoding rule (16), the blue
line corresponds to that of decoding rule (17), and the red line corresponds
to that of our algorithm, which is a combination of the two decoding rules.

Thus, for ${q}\leq 1/2$ (respectively ${q}>1/2$), the number of tests $T$
given in (13) can output the defective set ${\cal D}$ with probability of
error at most $\varepsilon$ using the decoding rule (16) (respectively (17)).
This proves Theorem 1-a).

###  VI-B Proof of Theorem 1-b)

We provide an explicit bound on the value of ${\hat{\Gamma}}({q})$ defined in
(14) for some ${q}$, namely Proposition 3 below, whose proof is presented in
Appendix D.

###### Proposition 3

There exists some ${q}_{0}\in(0,1)$ such that

${\hat{\Gamma}}({q}_{0})\leq
376017{H(f)}d\log\left(\frac{2n}{\varepsilon}\right),$ (30)

where ${H(f)}$ is the “sensitivity parameter” defined in (18).

Combined with (10), (14) and (15), this result yields

$\displaystyle T=\left\lceil{\Gamma}({{q}^{*}})\right\rceil$
$\displaystyle=\left\lceil{P_{min}({{q}^{*}})}{\hat{\Gamma}}({{q}^{*}})\right\rceil$
$\displaystyle\leq\left\lceil{P_{min}({{q}^{*}})}{\hat{\Gamma}}({q}_{0})\right\rceil$
$\displaystyle\leq
376017{P_{min}({{q}^{*}})}{H(f)}d\log\left(\frac{2n}{\varepsilon}\right)+1$
(31) $\displaystyle\leq
376017{H(f)}d\log\left(\frac{2n}{\varepsilon}\right)+1,$ (32)

which proves Theorem 1-b).

###  VI-C Proof of Theorem 1-c)

We first show in Lemma 8 below, whose proof is presented in Appendix G, that
${{q}^{*}}$ can never be too small nor too large.

###### Lemma 8

We have

${{q}^{*}}\in\left(\frac{1}{376017d^{3}},1-\frac{1}{376017d^{3}}\right).$ (33)

Next, we show in Lemma 9 below, whose proof is presented in Appendix H, that
for any ${q}$ that is within $\frac{1}{376017d^{4}}$ distance of ${{q}^{*}}$,
${{\Gamma}({q})}$ is bounded from above by $64e^{2}{\Gamma}({{q}^{*}})$. This
means that our algorithm still performs well for an estimator of ${{q}^{*}}$
with small error.

###### Lemma 9

For any
${\hat{{q}}^{*}}\in\left[{{q}^{*}}-\frac{1}{376017d^{4}},{{q}^{*}}+\frac{1}{376017d^{4}}\right]$,

${\Gamma({\hat{{q}}^{*}})}\leq 64e^{2}{\Gamma}({{q}^{*}}).$ (34)

Armed with Lemma 9, we are now ready to describe our algorithm to selecting
${q}$: First, calculate ${{\Gamma}({q})}$ for all ${q}=\frac{j}{376017d^{4}}$,
$j=1,2,\cdots,376017d^{4}-1$. Then choose the one having the smallest
${{\Gamma}({q})}$ value, denoted by ${\hat{{q}}}$. It follows that
${\Gamma({\hat{{q}}})}\leq{\Gamma({\hat{{q}}^{*}})}\leq
64e^{2}{\Gamma}({{q}^{*}})$. The computational complexity of computing
binomial coefficients is ${\cal O}(d^{2}\log^{2}d)$, and the computational
complexity of multiplying the binomial coefficient (which comprises of ${\cal
O}(d\log d)$ bits) with ${q}^{j}(1-{q})^{d-j}$ (which comprises ${\cal O}(d)$
bits), is ${\cal O}(d^{2}\log d)$. According to (83), the computational
complexity of computing ${\Delta({q})}$ is ${\cal O}(d^{3}\log^{2}d)$. Hence
the overall computational complexity of this algorithm is ${\cal
O}(d^{7}\log^{2}d)$.

###  VI-D Proof of Theorem 1-d)

Given the tests and their outcomes, the computational complexity of counting
all ${{m}_{i}}$ (respectively ${{s}_{i}}$) and ${{m}_{i}^{+}}$ (respectively
${{s}_{i}^{+}}$) is ${\cal O}(nT)$. Thus, the complexity of decoding is ${\cal
O}(nT)$. According to Theorem 1-b), the complexity is at most ${\cal
O}\left(n{H(f)}d\log\left(\frac{n}{\varepsilon}\right)\right)$.

##  VII Proof of Theorem 2

In this section, for any given monotone test function $f(\cdot)$, we provide
an information-theoretic lower bound on the number of tests required by _any_
non-adaptive group testing algorithm that is allowed to make an error with
probability at most $\varepsilon$.

Let us first introduce some notation which will be used in the proof. We use a
binary vector $\boldsymbol{{X}}\in\\{0,1\\}^{n}$ to represent the set ${\cal
N}$, where $1$s indicate which items are defective. To estimate
$\boldsymbol{{X}}$, we perform $T$ suitable-designed tests, in which each test
must be designed prior to observing any outcomes. Let
$\boldsymbol{{Z}}=({Z}_{1},\dots,{Z}_{T})$ be a length $T$ vector, where
${Z}_{i}$ denotes the number of defectives in the $i$-th test. The test
outcomes are represented by a binary vector
$\boldsymbol{{Y}}=({Y}_{1},\dots,{Y}_{T})\in\\{0,1\\}^{T}$, where ${Y}_{i}=1$
indicates the outcome of the $i$-th test is positive. We emphasize that
${Z}_{i}$ is independent of
$({Y}_{1},\dots,{Y}_{i-1},{Y}_{i+1},\dots,{Y}_{T})$. Given the tests and their
outcomes, let $\boldsymbol{{\hat{X}}}$ be an estimate of $\boldsymbol{{X}}$.

By standard information-theoretic definitions, we have

$\displaystyle{H}(\boldsymbol{{X}})$
$\displaystyle={H}(\boldsymbol{{X}}|\boldsymbol{{Y}})+{I}(\boldsymbol{{X}};\boldsymbol{{Y}})$
$\displaystyle={H}(\boldsymbol{{X}}|\boldsymbol{{Y}},\boldsymbol{{\hat{X}}})+{I}(\boldsymbol{{X}};\boldsymbol{{Y}})$
$\displaystyle\leq{H}(\boldsymbol{{X}}|\boldsymbol{{\hat{X}}})+{I}(\boldsymbol{{X}};\boldsymbol{{Y}})$
(35)

where the second line follows since $\boldsymbol{{\hat{X}}}$ is a function of
$\boldsymbol{{Y}}$; the thrid line follows from the fact that conditioning
reduces entropy. Since the defective set ${\cal D}$ is uniformly distributed
over all length $n$ vector of Hamming weight $d$, we have

${H}(\boldsymbol{{X}})=\log\binom{n}{d}.$ (36)

By Fano’s inequality,

${H}(\boldsymbol{{X}}|\boldsymbol{{\hat{X}}})\leq
1+\varepsilon\log\binom{n}{d}.$ (37)

Let ${Y}^{i-1}:=({Y}_{1},\dots,{Y}_{i-1})$ and
${Z}^{i-1}:=({Z}_{1},\dots,{Z}_{i-1})$.666For $i=1$, we follow the convention
that ${Y}^{i-1}={Z}^{i-1}=\emptyset$. Similar to channel coding (see for
example [29, Sec. 7.3]), it can be easily verified that

$\displaystyle(\boldsymbol{{X}},{Z}^{i-1},{Y}^{i-1})-{Z}_{i}-{Y}_{i}$

which implies

$\displaystyle(\boldsymbol{{X}},{Y}^{i-1})-{Z}_{i}-{Y}_{i}.$ (38)

Following a standard set of inequalities we have

$\displaystyle I(\boldsymbol{{X}};\boldsymbol{{Y}})$
$\displaystyle=\sum\limits_{i=1}^{T}\left[{H}({Y}_{i}|{Y}^{i-1})-{H}({Y}_{i}|\boldsymbol{{X}},{Y}^{i-1})\right]$
$\displaystyle\leq\sum\limits_{i=1}^{T}\left[{H}({Y}_{i})-{H}({Y}_{i}|\boldsymbol{{X}},{Y}^{i-1})\right]$
$\displaystyle\leq\sum\limits_{i=1}^{T}\left[{H}({Y}_{i})-{H}({Y}_{i}|\boldsymbol{{X}},{Y}^{i-1},{Z}_{i})\right]$
$\displaystyle=\sum\limits_{i=1}^{T}\left[{H}({Y}_{i})-{H}({Y}_{i}|{Z}_{i})\right]$
(39)

where the first line follows from chain rule; the second and third lines
follow since conditioning reduces entropy; the last line follows from (38).

Let ${\chi}_{i}$ denote the pool-size of the $i$-th test and
$\Pr({Z}_{i}={a})$ denote the probability that ${Z}_{i}={a}$. We have

$\displaystyle\Pr({Z}_{i}={a})$
$\displaystyle=\frac{\binom{d}{{a}}\binom{n-d}{{\chi}_{i}-{a}}}{\binom{n}{{\chi}_{i}}}.$
(40)

For simplicity, we define

$\displaystyle{\mu}({\chi}_{i})$
$\displaystyle\coloneqq\sum\limits_{{a}=0}^{d}\Pr({Z}_{i}={a})f({a}),$ (41)
$\displaystyle{\sigma^{2}}({\chi}_{i})$
$\displaystyle\coloneqq\sum\limits_{{a}=0}^{d}\Pr({Z}_{i}={a})\left(f({a})-{\mu}({\chi}_{i})\right)^{2},$

where ${\mu}({\chi}_{i})$ and ${\sigma^{2}}({\chi}_{i})$ denote the mean and
variance of $\Pr({Y}_{i}=1|{Z}_{i})$. It turns out we are able to bound the
bracketed term $[\cdot]$ in (39) as follows:

###### Lemma 10

${H}({Y}_{i})-{H}({Y}_{i}|{Z}_{i})\leq\frac{{\sigma^{2}}({\chi}_{i})\log
e}{{\mu}({\chi}_{i})(1-{\mu}({\chi}_{i}))}$ (42)

###### Proof:

See Appendix I. ∎

Now substituting (42) into (39), we see that

$\displaystyle{I}(\boldsymbol{{X}};\boldsymbol{{Y}})$
$\displaystyle\leq\sum\limits_{i=1}^{T}\frac{{\sigma^{2}}({\chi}_{i})\log
e}{{\mu}({\chi}_{i})(1-{\mu}({\chi}_{i}))}$ $\displaystyle\leq
T\times\frac{{\sigma^{2}}({\chi}^{*})\log
e}{{\mu}({\chi}^{*})(1-{\mu}({\chi}^{*}))},$ (43)

where the second line follows by defining

$\displaystyle{\chi}^{*}:=\operatorname*{argmax}_{{\chi}\in\\{1,\dots,n-1\\}}\frac{{\sigma^{2}}({\chi})}{{\mu}({\chi})(1-{\mu}({\chi}))}.$
(44)

The reason for restricting ${\chi}\in\\{1,\dots,n-1\\}$ is that
${\sigma^{2}}(0)={\sigma^{2}}(n)=0$.

Finally, combining (VII), (36), (37) and (43) gives us the desired result

$T\geq\frac{{\mu}({\chi}^{*})\left(1-{\mu}({\chi}^{*})\right)}{{\sigma^{2}}({\chi}^{*})\log
e}\left((1-\varepsilon)\log\binom{n}{d}-1\right).$ (45)

This along with the definition of ${h(f)}$ in (23) completes the proof of
Theorem 2.

##  VIII Proof of Theorem 3

In this section, we argue that the upper bound in (21) given by the proposed
testing algorithm is at most a ${\cal
O}\left(\frac{{P_{min}({{q}^{*}})}}{{\mu}({\chi}^{*})\left(1-{\mu}({\chi}^{*})\right)}\right)$
factor larger than the lower bound in (24).

Before presenting the proof, let us give some technical results that
constitute the basic ingredients of the proof. To proceed, recall the
definitions of ${\mu}({\chi}),{\sigma^{2}}({\chi})$ in (22) and ${\chi}^{*}$
in (27), which we repeat here for convenience:

$\displaystyle{\chi}^{*}$
$\displaystyle\coloneqq\operatorname*{argmin}_{{\chi}\in\\{1,\dots,n-1\\}}\frac{{\mu}({\chi})(1-{\mu}({\chi}))}{{\sigma^{2}}({\chi})},$
(46) $\displaystyle{\mu}({\chi})$
$\displaystyle\coloneqq\sum\limits_{{i}=0}^{d}\frac{\binom{d}{{i}}\binom{n-d}{{\chi}-{i}}}{\binom{n}{{\chi}}}f({i}),$
$\displaystyle{\sigma^{2}}({\chi})$
$\displaystyle\coloneqq\sum\limits_{{i}=0}^{d}\frac{\binom{d}{{i}}\binom{n-d}{{\chi}-{i}}}{\binom{n}{{\chi}}}\left(f({i})-{\mu}({\chi})\right)^{2}.$

Define

$\displaystyle{\vartheta}$ $\displaystyle:={\chi}^{*}\frac{d}{n},$ (47)
$\displaystyle{\eta}$
$\displaystyle:=\left\\{\begin{array}[]{ll}\lfloor{\vartheta}\rfloor&\text{if}\;{\vartheta}-\lfloor{\vartheta}\rfloor<0.5,\\\
\lceil{\vartheta}\rceil&\text{if}\;{\vartheta}-\lfloor{\vartheta}\rfloor\geq
0.5.\end{array}\right.$ (50)

Since $0<{\chi}^{*}<n$, we have ${\vartheta}\in(0,d)$.

###### Lemma 11

$\exists\,{\kappa}\in\\{0,1,\cdots,d-1,d\\}\backslash\\{{\eta}\\}$ such that

$\left({\gamma}({\kappa})\frac{f({\kappa})-f({\eta})}{{\kappa}-{\vartheta}}\right)^{2}>\frac{{\sigma^{2}}({\chi}^{*})}{11},$
(51)

where
${\gamma}({\kappa}):=\min\left\\{|{\kappa}-{\vartheta}|,\sqrt{{\kappa}+1},\sqrt{d-{\kappa}+1},\sqrt{{\vartheta}+1},\sqrt{d-{\vartheta}+1}\right\\}$.

###### Proof:

See Appendix J. ∎

The following proposition plays a key role in the proof of Theorem 3.

###### Proposition 4

$\exists\,{\hat{L}},{\hat{U}}\in\\{0,\dots,d\\}$ with ${\hat{L}}<{\hat{U}}$
such that

$\left({\beta}\frac{f({\hat{U}})-f({\hat{L}})}{{\hat{U}}-{\hat{L}}}\right)^{2}\geq\frac{{\sigma^{2}}({\chi}^{*})}{176},$
(52)

where
${\beta}:=\min\left\\{{\hat{U}}-{\hat{L}},\sqrt{{\hat{L}}+1},\sqrt{d-{\hat{U}}+1}\right\\}$
and ${\sigma^{2}}({\chi}^{*})$ is defined in (46).

###### Proof:

Using ${\kappa}$ in Lemma 11, we construct a pair of $({\hat{L}},{\hat{U}})$
that satisfies (52). Set

$\displaystyle{\hat{L}}:=\min\\{{\kappa},{\eta}\\},\quad{\hat{U}}:=\max\\{{\kappa},{\eta}\\}.$
(53)

It follows that

$\displaystyle|{\hat{U}}-{\hat{L}}|$
$\displaystyle=\left|{\kappa}-{\eta}\right|,$ (54)
$\displaystyle\sqrt{{\hat{L}}+1}$
$\displaystyle=\min\left\\{\sqrt{{\kappa}+1},\sqrt{{\eta}+1}\right\\},$ (55)
$\displaystyle\sqrt{d-{\hat{U}}+1}$
$\displaystyle=\min\left\\{\sqrt{d-{\kappa}+1},\sqrt{d-{\eta}+1}\right\\},$
(56) $\displaystyle\left(f({\hat{U}})-f({\hat{L}})\right)^{2}$
$\displaystyle=\left(f({\kappa})-f\left({\eta}\right)\right)^{2}.$ (57)

From the definition of ${\eta}$ in (50), we have $|{\eta}-{\vartheta}|\leq
0.5$. From the assumption that
${\kappa}\in\\{0,1,\cdots,d-1,d\\}\setminus\left\\{{\eta}\right\\}$, we have
$|{\kappa}-{\eta}|\geq 1$. Using the triangle inequality, we have

$\displaystyle|{\kappa}-{\vartheta}|=|{\kappa}-{\eta}+{\eta}-{\vartheta}|\geq|{\kappa}-{\eta}|-|{\eta}-{\vartheta}|\geq
0.5\geq|{\eta}-{\vartheta}|.$

Using this observation together with (54), it follows that

$4({\kappa}-{\vartheta})^{2}\geq
2({\kappa}-{\vartheta})^{2}+2({\vartheta}-{\eta})^{2}\geq({\kappa}-{\vartheta}+{\vartheta}-{\eta})^{2}=({\hat{U}}-{\hat{L}})^{2}.$
(58)

Recalling the definition of ${\gamma}({\kappa})$ in Lemma 11, we have

$\displaystyle{\gamma}({\kappa})$
$\displaystyle=\min\left\\{|{\kappa}-{\vartheta}|,\sqrt{{\kappa}+1},\sqrt{d-{\kappa}+1},\sqrt{{\vartheta}+1},\sqrt{d-{\vartheta}+1}\right\\}$
$\displaystyle\leq\min\left\\{|{\kappa}-{\eta}|+|{\eta}-{\vartheta}|,\sqrt{{\kappa}+1},\sqrt{d-{\kappa}+1},\sqrt{{\vartheta}+1},\sqrt{d-{\vartheta}+1}\right\\}$
$\displaystyle\leq\min\left\\{|{\kappa}-{\eta}|+1,\sqrt{{\kappa}+1},\sqrt{d-{\kappa}+1},\sqrt{{\eta}+2},\sqrt{d-{\eta}+2}\right\\}$
$\displaystyle\leq\min\left\\{2|{\kappa}-{\eta}|,2\sqrt{{\kappa}+1},2\sqrt{d-{\kappa}+1},2\sqrt{{\eta}+1},2\sqrt{d-{\eta}+1}\right\\}$
$\displaystyle=\min\left\\{2|{\hat{U}}-{\hat{L}}|,2\sqrt{{\hat{L}}+1},2\sqrt{d-{\hat{U}}+1}\right\\}$
$\displaystyle=2{\beta},$ (59)

where the second line follows from the triangle inequality
$|{\kappa}-{\vartheta}|\leq|{\kappa}-{\eta}|+|{\eta}-{\vartheta}|$; the third
line is because $|{\eta}-{\vartheta}|\leq 1$; the fourth line follows from
$|{\kappa}-{\eta}|\geq 1$; the fifth line follows from (54), (55) and (56).
Combining (57), (58) (VIII), along with (51) in Lemma 11, we obtain

$\left({\beta}\frac{f({\hat{U}})-f({\hat{L}})}{{\hat{U}}-{\hat{L}}}\right)^{2}\geq\frac{{\gamma}({\kappa})^{2}}{4}\times\frac{(f({\kappa})-f({\eta}))^{2}}{4({\kappa}-{\vartheta})^{2}}>\frac{{\sigma^{2}}({\chi}^{*})}{176}.$
(60)

This completes the proof of Proposition 4. ∎

Now we set out to prove Theorem 3. Recalling the upper bound on $T$ in (21),
we have

$\displaystyle T$ $\displaystyle\leq
376017{P_{min}({{q}^{*}})}{H(f)}d\log\left(\frac{2n}{\varepsilon}\right)+1$
$\displaystyle\leq
376017{P_{min}({{q}^{*}})}\left(\frac{1}{\min\left\\{{\hat{U}}-{\hat{L}},\sqrt{{\hat{L}}+1},\sqrt{d-{\hat{U}}+1}\right\\}}\times\frac{{\hat{U}}-{\hat{L}}}{f({\hat{U}})-f({\hat{L}})}\right)^{2}d\log\left(\frac{2n}{\varepsilon}\right)+1$
$\displaystyle\leq
376017{P_{min}({{q}^{*}})}\frac{176}{{\sigma^{2}}({\chi}^{*})}d\log\left(\frac{2n}{\varepsilon}\right)+1$

where the second inequality follows from the definition of ${H(f)}$ in (18) by
letting $({L},{U})$ therein to be the pair $({\hat{L}},{\hat{U}})$ in
Proposition 4; the last inequality follows from Proposition 4. This implies
that the upper bound in (21) scales as ${\cal
O}\left(\frac{{P_{min}({{q}^{*}})}}{{\sigma^{2}}({\chi}^{*})}d\log\left(\frac{2n}{\varepsilon}\right)\right)$.
On the other hand, by the definition of ${h(f)}$ in (23), the lower bound in
(24) scales as
$\Omega\left(\frac{{\mu}({\chi}^{*})\left(1-{\mu}({\chi}^{*})\right)}{{\sigma^{2}}({\chi}^{*})}\log\binom{n}{d}\right)$.
By standard arguments via Stirling’s approximation, $\log\binom{n}{d}$ is at
least $d\log\frac{n}{d}$. Thus, under the assumptions that
$d=n^{\theta},0\leq\theta<1$, the number of tests $T$ required for
$(1-\varepsilon)$-reliable recovery in Theorem 1 is up to a ${\cal
O}\left(\frac{{P_{min}({{q}^{*}})}}{{\mu}({\chi}^{*})\left(1-{\mu}({\chi}^{*})\right)}\right)$
factor larger than the lower bound presented in Theorem 2.

From Remarks 2 and 4, we know that our upper and lower bounds scale as ${\cal
O}\left(d^{2+o(1)}\log n\right)$ and $\Omega\left(d\log n\right)$,
respectively. Therefore, the number of tests required in Theorem 1 is never
more than a ${\cal O}(d^{1+o(1)})$ factor larger than the information-
theoretic lower bound in Theorem 2.

##  IX Simulation

In this section we report the results of our computer simulations to evaluate
the performance of our proposed schemes.777The computing resource we use is an
Intel(R) Xeon(R) CPU E5-2699 v4 @ 2.20GHz CPU. Our algorithm takes as input

  * •

number of items $n$;

  * •

number of defectives $d$;

  * •

test function $f$;

  * •

number of tests $T$.

We then run the proposed test design and decoding rule multiple times to
evaluate the probability of successful reconstruction.

Testing: For given $(n,d,f,T)$, we randomly generate an array $\boldsymbol{X}$
of length $n$ with $(n-d)$ 0s and $d$ 1s, where 0 represents non-defective and
1 represents defective. Then we choose the parameter ${q}$ accordingly, and
randomly generate a $T\times n$ matrix $\boldsymbol{M}$ where each entry is
i.i.d. Bernoulli(${q}$). Each row of $\boldsymbol{M}$ corresponds to a
distinct test, and each column corresponds to a distinct item. Finally, we
compute $\boldsymbol{Z}=(Z_{1},\dots,Z_{T})=\boldsymbol{M}\boldsymbol{X}$ and
generate the test outcomes according to $f(Z_{i}),i=1,\dots,T$.

Decoding: Depending on the value of ${q}$, we then use the decoding rules (16)
or (17). Let $\boldsymbol{\hat{X}}$ be the estimation of the decoder. The test
succeeds if $\boldsymbol{\hat{X}}=\boldsymbol{X}$, and fails otherwise.

###  IX-A Simulation result for threshold test function in Corollary 1-b)

Consider the function $f(\cdot)$ defined in (25) for ${\ell}=5$ i.e.,

$f(x)=\left\\{\begin{array}[]{ll}0&\text{if}\;x\leq 5,\\\
1&\text{if}\;x>5,\end{array}\right.$ (61)

which is also illustrated in Figure 4(a). In Corollary 1-b), we have shown
that our algorithm is order-wise optimal and the number of tests $T$ scales as
$\Theta(d\log n)$. For ease of implementation, we assign ${q}=\frac{5}{d}$. In
the waterfall plot in Figure 4(b), $n=2000$, $d=20$, the $x$-axis plots the
number of tests $T$ ranging from $T_{min}=0$ to $T_{max}=\left\lfloor 40d\log
n\right\rfloor$ with step size
$\Delta_{T}=\left\lfloor\frac{T_{max}-T_{min}}{100}\right\rfloor$, and the
$y$-axis plots the probability of successful reconstruction calculated by
$1000$ trials for each test
$T=T_{min}+j\times\Delta_{T},j\in\\{0,1,\dots,100\\}$. When $T\gtrapprox
19.2d\log n$, the probability of successful reconstruction generally exceeds
$0.99$.888Here and below, “generally exceeds” means that the average of itself
and two tests prior to it is larger than $0.99$. In the heat-map in Figure
4(c), $n=2000$, the $x$-axis denotes the number of defectives $d$ ranging from
$20$ to $120$, and the $y$-axis denotes the number of tests $T$ as a multiple
of $d\log n$. In the heat-map in Figure 4(d), $d=20$, the $x$-axis corresponds
to the number of items $n$ ranging from $2000$ to $6000$, and the $y$-axis
corresponds to the number of tests $T$ as a multiple of $d\log n$. In both
Figures 4(c) and 4(d), each pixel is coloured according to the probability of
successful reconstruction calculated by $1000$ trials for each test $T$– the
lighter the colour, the higher the probability of reconstruction success. For
each value of $d$ (respectively $n$) in Figure 4(c) (respectively Figure
4(d)), the corresponding red dot in that column represents the number of tests
for which this probability first equals $0.99$. The horizontal blue dashed
line indicates that when $T\gtrapprox 17.2d\log n$ (respectively $20.4d\log
n$), the probability of successful reconstruction generally exceeds $0.99$.

$f(x)$$x$$0.5$$1$$5$$6$$d$ (a) Example test function defined in (61): The test
outcome is positive if and only if at least $6$ items in a pool are defective.
(b) The $x$-axis plots the number of tests $T$ as a multiple of $d\log n$, and
the $y$-axis plots the probability of successful reconstruction, for fixed
$n=2000,d=20$. When $T\gtrapprox 19.2d\log n$, the probability of successful
reconstruction exceeds $0.99$.  (c) The $x$-axis corresponds to the number of
defectives $d$ ranging from $20$ to $120$, and the $y$-axis corresponds to the
number of tests $T$ as a multiple of $d\log n$–the number of items $n$ is
fixed to be $2000$. Each pixel is coloured according to the probability of
successful reconstruction– the lighter the colour, the higher the probability
of reconstruction success. For each value of $d$, the corresponding red dot in
that column represents the number of tests for which this probability first
equals $0.99$. The horizontal blue dashed line indicates that when
$T\gtrapprox 17.2d\log n$, the probability of successful reconstruction
generally exceeds $0.99$. (d) The $x$-axis denotes the number of items $n$
ranging from $2000$ to $6000$, and the $y$-axis denotes the number of tests
$T$ as a multiple of $d\log n$–the number of defectives $d$ equals $20$. Each
pixel is coloured according to the probability of successful reconstruction –
the lighter the colour, the higher the probability of reconstruction success.
For each value of $n$, the corresponding red dot in that column represents the
number of tests for which this probability first equals $0.99$. The horizontal
blue dashed line indicates that when $T\gtrapprox 20.4d\log n$, the
probability of successful reconstruction generally exceeds $0.99$.

Figure 4: Simulation result for threshold test function in Corollary 1-b).

$f(x)$$x$$0$$0$$0.5$$1$$\frac{d}{2}$$d$ (a) Example test function $f$ defined
in (26): The probability that test outcome is positive increases linearly. (b)
The $x$-axis plots the number of tests $T$ as a multiple of $d^{2}\log n$, and
the $y$-axis plots the probability of successful reconstruction, for fixed
$n=2000$ and $d=20$. When $T\gtrapprox 21.6d^{2}\log n$, the probability of
successful reconstruction exceeds $0.99$.  (c) The $x$-axis corresponds to the
number of defectives $d$ ranging from $20$ to $70$, and the $y$-axis
corresponds to the number of tests $T$ as a multiple of $d^{2}\log n$, for
fixed number of items $n=2000$. Each pixel is coloured according to the
probability of successful reconstruction– the lighter the colour, the higher
the probability of reconstruction success. For each value of $d$, the
corresponding red dot in that column represents the number of tests for which
this probability first equals $0.99$. The horizontal blue dashed line
indicates that when $T\gtrapprox 20.0d^{2}\log n$, the probability of
successful reconstruction generally exceeds $0.99$. (d) The $x$-axis denotes
the number of items $n$ ranging from $2000$ to $4000$, and the $y$-axis
denotes the number of tests $T$ as a multiple of $d^{2}\log n$, for fixed
number of defectives $d=20$. Each pixel is coloured according to the
probability of successful reconstruction – the lighter the colour, the higher
the probability of reconstruction success. For each value of $n$, the
corresponding red dot in that column represents the number of tests for which
this probability first equals $0.99$. The horizontal blue dashed line
indicates that when $T\gtrapprox 19.6d^{2}\log n$, the probability of
successful reconstruction generally exceeds $0.99$.

Figure 5: Simulation result for linear test function in Corollary 1-c).

###  IX-B Simulation result for linear test function in Corollary 1-c)

We now consider the function $f(\cdot)$ defined in (26) and illustrated in
Figure 5(a). In Corollary 1-c), we have shown that our algorithm is order-wise
optimal and the number of tests $T$ scales as $\Theta(d^{2}\log n)$. For ease
of implementation, we assign ${q}=\frac{1}{2}$. In the waterfall plot in
Figure 5(b), $n=2000$, $d=20$, the $x$-axis plots the number of tests $T$
ranging from $T_{min}^{\prime}=0$ to $T_{max}^{\prime}=\left\lfloor
40d^{2}\log n\right\rfloor$ with step size
$\Delta_{T}^{\prime}=\left\lfloor\frac{T_{max}-T_{min}}{100}\right\rfloor$,
and the $y$-axis plots the probability of successful reconstruction calculated
by $100$ trials for each test
$T=T_{min}^{\prime}+j\times\Delta_{T}^{\prime},j\in\\{0,1,\dots,100\\}$. When
$T\gtrapprox 21.6d^{2}\log n$, the probability of successful reconstruction
exceeds $0.99$. In the heat-map figure 5(c), $n=2000$, the $x$-axis denotes
the number of defectives $d$ ranging from $20$ to $70$, and the $y$-axis
denotes the number of tests $T$ as a multiple of $d^{2}\log n$. In the heat-
map figure 5(d), $d=20$, the $x$-axis corresponds to the number of items $n$
ranging from $2000$ to $4000$, and the $y$-axis corresponds to the number of
tests $T$ as a multiple of $d^{2}\log n$. In both figures 5(c) and 5(d), each
pixel is coloured according to the probability of successful reconstruction
calculated by $100$ trials for each test $T$– the lighter the colour, the
higher the probability of reconstruction success. For each value of $d$
(respectively $n$) in figure 5(c) (respectively figure 5(d)), the
corresponding red dot in that column represents the number of tests for which
this probability first equals $0.99$. The horizontal blue dashed line
indicates that when $T\gtrapprox 20.0d^{2}\log n$ (respectively $19.6d^{2}\log
n$), the probability of successful reconstruction generally exceeds $0.99$.

###  IX-C Simulation result for Conjecture 1

We consider two test functions and show the corresponding performance of our
algorithm. Consider one specific “partial linear” function defined in (20) in
Example 1:

$f(x)=\left\\{\begin{array}[]{ll}\frac{x}{d^{2/3}}&x\in\left[0,d^{2/3}\right]\cap\mathbb{Z}^{+},\\\
1&\text{otherwise},\end{array}\right.$ (62)

Letting $n=1250$ and $d=125$, the performance of our algorithm is presented in
Fig. 6(b). Then consider the well-known sigmoid function:

$f(x)=\frac{e^{\frac{x}{2}-\frac{d}{4}}}{e^{\frac{x}{2}-\frac{d}{4}}+1}.$ (63)

Letting $n=2000$ and $d=100$, the performance of our algorithm is presented in
Fig. 6(d). One can see from the figures that
$\frac{\min_{{q}\in(0,1)}{{\Gamma}({q})}}{{h(f)}d\log n}\leq 2$ in both two
cases, which supports our conjecture.

$f(x)$$x$$0$$0$$0.5$$1$$d^{\frac{2}{3}}$$d$ (a) Example test function $f$
defined in (62). (b) Performance of our algorithm for the “partial linear”
function.  $f(x)$$x$$0$$0$$0.5$$1$$\frac{d}{2}$$d$ (c) Example test function
$f$ defined in (63).  (d) Performance of our algorithm for the sigmoid
function.

Figure 6: Simulation result for Conjecture 1.

## Acknowledgment

The authors wish to acknowledge useful discussions with Profs. Oliver Johnson
and Jonathan Scarlett. We would also like to thank the anonymous reviewers of
the conference version for many helpful suggestions which greatly improved the
quality of this work.

##  Appendix A Proof of Lemma 2

Since $\min\left\\{{U}-{L},\sqrt{{L}+1},\sqrt{d-{U}+1}\right\\}\leq{U}-{L}$,
it follows from the definition of ${H(f)}$ in (18) that

$\displaystyle{H(f)}$ $\displaystyle\geq\min_{0\leq{L}<{U}\leq
d}\left(\frac{1}{{U}-{L}}\times\frac{{U}-{L}}{f({U})-f({L})}\right)^{2}$
$\displaystyle\geq\frac{1}{\left(f(d)-f(0)\right)^{2}}$

where the second line follows from the assumption that $f(\cdot)$ is
monotonically increasing.

The upper bound is proved by taking into account the “shape” of the monotone
test function $f(\cdot)$. For any ${\upsilon}\in\left(0,1\right]$, define

$\displaystyle{k}:=\left\lceil\log\frac{1}{{\upsilon}}+1\right\rceil.$ (64)

For notational convenience, let

${\delta}:=f(d)-f(0)>0.$

There are two possible cases for $f(\cdot)$:

  1. i)

$f\left(\left\lceil\frac{d}{2}\right\rceil\right)\geq
f(0)+\frac{{\delta}}{2}$;

  2. ii)

$f\left(\left\lceil\frac{d}{2}\right\rceil\right)<f(0)+\frac{{\delta}}{2}$.

Case i): For $f\left(\left\lceil\frac{d}{2}\right\rceil\right)\geq
f(0)+\frac{{\delta}}{2}$, define a sequence $\\{{S}_{{i}}\\}$ such that

${S}_{i}:=\left\\{\begin{array}[]{ll}\left\lfloor\frac{1}{2}d^{1-2^{-{i}+1}}\right\rfloor&{i}=1,2,\cdots,{k},\\\
\left\lceil\frac{1}{2}d\right\rceil&{i}={k}+1.\end{array}\right.$ (65)

From (65) we have that for ${i}\in\\{1,\cdots,{k}-1\\}$,

$\displaystyle\frac{{S}_{{i}+1}^{2}}{{S}_{{i}}+1}\leq\left(\frac{d^{1-2^{-{i}}}}{2}\right)^{2}\frac{2}{d^{1-2^{-{i}+1}}}=\frac{d}{2};$
(66)

for ${i}={k}$,

$\displaystyle\frac{{S}_{{i}+1}^{2}}{{S}_{{i}}+1}\leq\left(\frac{d+1}{2}\right)^{2}\frac{2}{d^{1-2^{-{k}+1}}}\leq
d^{2}\frac{2}{d^{1-2^{-{k}+1}}}\leq 2d^{1+{\upsilon}},$ (67)

where the second inequality follows the fact that $\frac{d+1}{2}\leq d,\forall
d\geq 1$; the last inequality follows from the definition of ${k}$ in (64).
Combining (66) and (67), we see that

$\displaystyle\frac{{S}_{{i}+1}^{2}}{{S}_{{i}}+1}\leq
2d^{1+{\upsilon}},\quad\forall{i}\in\\{1,\dots,{k}\\}.$ (68)

Note that the sequence $\\{{S}_{{i}}\\}$ is increasing in terms of ${i}$. It
then follows that
${S}_{{i}}+{S}_{{i}+1}\leq\left\lfloor\frac{1}{2}d\right\rfloor+\left\lceil\frac{1}{2}d\right\rceil=d,\;\forall{i}\in\\{1,\dots,{k}\\}$.
This implies

$\displaystyle{S}_{{i}}+1\leq
d-{S}_{{i}+1}+1,\quad\forall{i}\in\\{1,\dots,{k}\\}.$ (69)

Then we argue that $\exists{\ell}\in\\{1,\cdots,{k}\\}$ such that

$f({S}_{{\ell}+1})-f({S}_{{\ell}})\geq\frac{{\delta}}{2{k}},$ (70)

because, if to the contrary that such a ${\ell}$ does not exist, then

$\displaystyle
f\left(\left\lceil\frac{d}{2}\right\rceil\right)-f(0)=f({S}_{{k}+1})-f({S}_{1})=\sum_{i=1}^{k}\left(f({S}_{{i}+1})-f({S}_{{i}})\right)<k\frac{{\delta}}{2{k}}=\frac{{\delta}}{2}$

contradicts our assumption that
$f\left(\left\lceil\frac{d}{2}\right\rceil\right)\geq
f(0)+\frac{{\delta}}{2}$.

Next, letting ${L}={S}_{{\ell}}$ and ${U}={S}_{{\ell}+1}$, we obtain from (69)
that

$\displaystyle\min\left\\{{U}-{L},\sqrt{{L}+1},\sqrt{d-{U}+1}\right\\}=\min\left\\{{S}_{{\ell}+1}-{S}_{{\ell}},\sqrt{{S}_{{\ell}}+1}\right\\}$

It then follows from (18) that

$\displaystyle{H(f)}$
$\displaystyle\leq\left(\frac{1}{\min\left\\{{S}_{{\ell}+1}-{S}_{{\ell}},\sqrt{{S}_{{\ell}}+1}\right\\}}\times\frac{{S}_{{\ell}+1}-{S}_{{\ell}}}{f({S}_{{\ell}+1})-f({S}_{{\ell}})}\right)^{2}$
$\displaystyle\leq\frac{4{k}^{2}}{{\delta}^{2}}\times\max\left\\{1,\frac{({S}_{{\ell}+1}-{S}_{{\ell}})^{2}}{{S}_{{\ell}}+1}\right\\}$
$\displaystyle\leq\frac{4{k}^{2}}{{\delta}^{2}}\times\max\left\\{1,\frac{{S}_{{\ell}+1}^{2}}{{S}_{{\ell}}+1}\right\\}$
$\displaystyle\leq\frac{8{k}^{2}}{{\delta}^{2}}\times d^{1+{\upsilon}}$
$\displaystyle\leq\frac{8}{{\delta}^{2}}\left(\log\frac{1}{{\upsilon}}+2\right)^{2}d^{1+{\upsilon}}$
(71)

where the second line follows from (70); the fourth line follows from (68);
the last line follows from the definition of ${k}$ in (64).

Case ii): For
$f\left(\left\lceil\frac{d}{2}\right\rceil\right)<f(0)+\frac{{\delta}}{2}$, we
define

$\displaystyle{\tilde{f}}(x):=1-f(d-x),\quad x\in\\{0,\dots,d\\}.$ (72)

It follows that

${\tilde{f}}\left(\left\lceil\frac{d}{2}\right\rceil\right)-{\tilde{f}}(0)\geq{\tilde{f}}\left(\left\lfloor\frac{d}{2}\right\rfloor\right)-{\tilde{f}}(0)=1-f\left(d-\left\lfloor\frac{d}{2}\right\rfloor\right)-\left(1-f(d)\right)=f(d)-f\left(\left\lceil\frac{d}{2}\right\rceil\right)>\frac{{\delta}}{2}.$
(73)

Consider the sequence $\\{{S}_{{i}}\\}$ defined in (65). Following the same
argument as above, we have that $\exists{\ell}\in\\{1,\cdots,{k}\\}$ such that

${\tilde{f}}({S}_{{\ell}+1})-{\tilde{f}}({S}_{{\ell}})\geq\frac{{\delta}}{2{k}}.$
(74)

Using (74) along with the definition of ${\tilde{f}}$ in (72) implies

$f(d-{S}_{{\ell}})-f(d-{S}_{{\ell}+1})=1-{\tilde{f}}({S}_{{\ell}})-(1-{\tilde{f}}({S}_{{\ell}+1}))={\tilde{f}}({S}_{{\ell}+1})-{\tilde{f}}({S}_{{\ell}})\geq\frac{{\delta}}{2{k}}.$
(75)

Setting ${L}=d-{S}_{{\ell}+1}$ and ${U}=d-{S}_{{\ell}}$, we have from (69)
that

$\displaystyle\min\left\\{{U}-{L},\sqrt{{L}+1},\sqrt{d-{U}+1}\right\\}=\min\left\\{{S}_{{\ell}+1}-{S}_{{\ell}},\sqrt{{S}_{{\ell}}+1}\right\\}$

Similar to the derivation of (A), we have from (18) that

$\displaystyle{H(f)}$
$\displaystyle\leq\left(\frac{1}{\min\left\\{{S}_{{\ell}+1}-{S}_{{\ell}},\sqrt{{S}_{{\ell}}+1}\right\\}}\times\frac{d-{S}_{{\ell}}-\left(d-{S}_{{\ell}+1}\right)}{f(d-{S}_{{\ell}})-f(d-{S}_{{\ell}+1})}\right)^{2}$
$\displaystyle\leq\frac{8}{{\delta}^{2}}\left(\log\frac{1}{{\upsilon}}+2\right)^{2}d^{1+{\upsilon}}$
(76)

Summarizing the two cases, we see that for any monotone test function
$f(\cdot)$,

${H(f)}\leq\frac{8}{\left(f(d)-f(0)\right)^{2}}\left(\log\frac{1}{{\upsilon}}+2\right)^{2}d^{1+{\upsilon}}.$
(77)

For $d\geq 2$, upon setting ${\upsilon}=\frac{1}{\log d}$, we obtain from (77)
that

${H(f)}\leq\frac{16}{\left(f(d)-f(0)\right)^{2}}\left(\log\log
d+2\right)^{2}d,$ (78)

which completes the proof.

##  Appendix B Proof of Lemma 1

We expand ${P(-,{q})},{P(+,{q})},{Q(-,{q})}$ and ${P(+,{q})}$ using elementary
combinatorial and algebraic identities. Regarding ${P(-,{q})}$, we have that

$\displaystyle{P(-,{q})}$
$\displaystyle=\sum\limits_{j=0}^{d}\binom{d}{j}{q}^{j}(1-{q})^{d-j}f(j)$
$\displaystyle=(1-{q})^{d}f(0)+\sum\limits_{j=1}^{d-1}\binom{d}{j}{q}^{j}(1-{q})^{d-j}f(j)+{q}^{d}f(d)$
$\displaystyle=(1-{q})^{d}f(0)+\sum\limits_{j=1}^{d-1}\left(\binom{d-1}{j}+\binom{d-1}{j-1}\right){q}^{j}(1-{q})^{d-j}f(j)+{q}^{d}f(d)$
$\displaystyle=\sum\limits_{j=0}^{d-1}\binom{d-1}{j}{q}^{j}(1-{q})^{d-j}f(j)+\sum\limits_{j=1}^{d}\binom{d-1}{j-1}{q}^{j}(1-{q})^{d-j}f(j).$
(79)

Regarding ${P(+,{q})}$, by relabelling, we have that

$\displaystyle{P(+,{q})}$
$\displaystyle=\sum\limits_{j=0}^{d-1}\binom{d-1}{j}{q}^{j}(1-{q})^{d-1-j}f(j+1)$
(80)
$\displaystyle=\sum\limits_{j=1}^{d}\binom{d-1}{j-1}{q}^{j-1}(1-{q})^{d-j}f(j).$
(81)

From (80) and (81), we can rewrite ${P(+,{q})}$ as

$\displaystyle{P(+,{q})}$
$\displaystyle=(1-{q})\sum\limits_{j=0}^{d-1}\binom{d-1}{j}{q}^{j}(1-{q})^{d-1-j}f(j+1)+{q}\sum\limits_{j=1}^{d}\binom{d-1}{j-1}{q}^{j-1}(1-{q})^{d-j}f(j)$
$\displaystyle=\sum\limits_{j=0}^{d-1}\binom{d-1}{j}{q}^{j}(1-{q})^{d-j}f(j+1)+\sum\limits_{j=1}^{d}\binom{d-1}{j-1}{q}^{j}(1-{q})^{d-j}f(j).$
(82)

Combining (B) and (B), we can write ${\Delta({q})}$ as

$\displaystyle{\Delta({q})}$ $\displaystyle={P(+,{q})}-{P(-,{q})}$ (83)
$\displaystyle=\sum\limits_{j=0}^{d-1}\binom{d-1}{j}{q}^{j}(1-{q})^{d-j}(f(j+1)-f(j)).$

Under the assumption that $f(\cdot)$ is monotonically increasing and
$f(0)<f(d)$, we conclude that

$\displaystyle{\Delta({q})}>0\;\text{ or equivalently
}\;{P(+,{q})}>{P(-,{q})}.$ (84)

Similarly, regarding ${Q(-,{q})}$, we have

$\displaystyle{Q(-,{q})}$
$\displaystyle=\sum\limits_{j=0}^{d}\binom{d}{j}{q}^{j}(1-{q})^{d-j}f(j)$
$\displaystyle=\sum\limits_{j=0}^{d-1}\binom{d-1}{j}{q}^{j}(1-{q})^{d-j}f(j)+\sum\limits_{j=1}^{d}\binom{d-1}{j-1}{q}^{j}(1-{q})^{d-j}f(j).$

And regarding ${Q(+,{q})}$, we have

$\displaystyle{Q(+,{q})}$
$\displaystyle=\sum\limits_{j=0}^{d-1}\binom{d-1}{j}{q}^{j}(1-{q})^{d-1-j}f(j)$
$\displaystyle=\sum\limits_{j=1}^{d}\binom{d-1}{j-1}{q}^{j-1}(1-{q})^{d-j}f(j-1)$
$\displaystyle=(1-{q})\sum\limits_{j=0}^{d-1}\binom{d-1}{j}{q}^{j}(1-{q})^{d-1-j}f(j)+{q}\sum\limits_{j=1}^{d}\binom{d-1}{j-1}{q}^{j-1}(1-{q})^{d-j}f(j-1)$
$\displaystyle=\sum\limits_{j=0}^{d-1}\binom{d-1}{j}{q}^{j}(1-{q})^{d-j}f(j)+\sum\limits_{j=1}^{d}\binom{d-1}{j-1}{q}^{j}(1-{q})^{d-j}f(j-1).$

It then follows that

$\displaystyle{\nabla({q})}$ $\displaystyle={Q(-,{q})}-{Q(+,{q})}$ (85)
$\displaystyle=\sum\limits_{j=1}^{d}\binom{d-1}{j-1}{q}^{j}(1-{q})^{d-j}(f(j)-f(j-1))$
$\displaystyle=\sum\limits_{j=0}^{d-1}\binom{d-1}{j}{q}^{j+1}(1-{q})^{d-j-1}(f(j+1)-f(j))$
$\displaystyle=\frac{{q}}{1-{q}}{\Delta({q})},$ (86)

where the last equality follows from (83). This together with (84) implies
that

$\displaystyle{\nabla({q})}>0\;\text{ or equivalently
}\;{Q(-,{q})}>{Q(+,{q})}.$ (87)

Using the monotonicity of $f(\cdot)$, we see that

$\displaystyle{P(+,{q})}$
$\displaystyle\leq\sum\limits_{j=0}^{d-1}\binom{d-1}{j}{q}^{j}(1-{q})^{d-1-j}f(d)=f(d)$
(88) $\displaystyle{Q(+,{q})}$
$\displaystyle\geq\sum\limits_{j=0}^{d-1}\binom{d-1}{j}{q}^{j}(1-{q})^{d-1-j}f(0)=f(0)$
(89)

Combining (84), (87), (88) and (89), along with the definitions of
${P(-,{q})}$ in (4) and ${Q(-,{q})}$ in (5), we obtain

$\displaystyle f(d)\geq{P(+,{q})}>{P(-,{q})}={Q(-,{q})}>{Q(+,{q})}\geq f(0).$
(90)

Recalling the definition

$\displaystyle{P_{\min}({q})}=\min\left\\{{P(+,{q})},1-{Q(+,{q})}\right\\},$
(91)

we have from (90) that

$\displaystyle 1\geq{P_{\min}({q})}$
$\displaystyle\geq\min\\{{P(+,{q})},1-{P(-,{q})}\\}$
$\displaystyle\geq\min\\{{P(+,{q})}-{P(-,{q})},{P(+,{q})}-{P(-,{q})}\\}$
$\displaystyle={\Delta({q})},$ (92)

and

$\displaystyle{P_{\min}({q})}$
$\displaystyle\geq\min\\{{Q(-,{q})},1-{Q(+,{q})}\\}$
$\displaystyle\geq\min\\{{Q(-,{q})}-{Q(+,{q})},{Q(-,{q})}-{Q(+,{q})}\\}$
$\displaystyle={\nabla({q})},$ (93)

Combining (92) and (B), we have that

$\displaystyle
1\geq{P_{\min}({q})}\geq\max\left\\{{\Delta({q})},{\nabla({q})}\right\\}.$

This concludes the proof.

##  Appendix C Proofs of tail-bound lemmas

The proofs of the tail-bound lemmas that bound the probability of error of our
decoding rules in Theorem 1 are collected in this Appendix.

###  -1 Proof of Lemma 4

We shall use the following well-known Chernoff bound [28].

######  Fact 1 (Chernoff bound [28])

Suppose that $X\sim\text{Binomial}(n,p)$. Then, for any
$\delta^{\prime}\in(0,1)$, we have

$\displaystyle\Pr\left(X\leq(1-\delta^{\prime})np\right)$
$\displaystyle\leq\exp\left(-\frac{\delta^{\prime
2}}{2}np\right)\leq\exp\left(-\frac{\delta^{\prime 2}}{3}np\right),$ (94)
$\displaystyle\Pr\left(X\geq(1+\delta^{\prime})np\right)$
$\displaystyle\leq\exp\left(-\frac{\delta^{\prime
2}}{2+\delta^{\prime}}np\right)\leq\exp\left(-\frac{\delta^{\prime
2}}{3}np\right).$

We now proceed with the proof of Lemma 4. Recall that in (28), $T$ was
selected to satisfy $T\geq\frac{13}{6{q}}m$. Consider an arbitrary item
$i\in\mathcal{N}$. Since each item participates in a test i.i.d. with
probability ${q}$, the expected number of tests item $i$ involving is

$\displaystyle\mathbb{E}({{m}_{i}})$ $\displaystyle={q}T$
$\displaystyle\geq\frac{13}{6}{m}$
$\displaystyle=2{m}+\frac{1}{6}\times\frac{12{P_{\min}({q})}}{({\Delta({q})})^{2}}\ln\left(\frac{2n}{\varepsilon}\right)$
$\displaystyle\geq 2{m}+2\ln\left(\frac{2n}{\varepsilon}\right),$ (95)

where the third line follows from the definition of ${m}$ in (11); the last
line follows from (10).

Let $\mathcal{E}_{i}$ be the event that item $i$ participates in less than
${m}$ tests. By Fact 1, we have

$\displaystyle\Pr(\mathcal{E}_{i})$
$\displaystyle=\Pr\left({{m}_{i}}<{m}=\left(1-\frac{\mathbb{E}({{m}_{i}})-{m}}{\mathbb{E}({{m}_{i}})}\right)\mathbb{E}({{m}_{i}})\right)$
$\displaystyle\leq\exp\left(-\left(\frac{\mathbb{E}({{m}_{i}})-{m}}{\mathbb{E}({{m}_{i}})}\right)^{2}\,\frac{\mathbb{E}({{m}_{i}})}{2}\right)$
$\displaystyle=\exp\left(-\frac{\mathbb{E}({{m}_{i}})}{2}+{m}-\frac{{m}^{2}}{2\mathbb{E}({{m}_{i}})}\right)$
$\displaystyle\leq\exp\left(-\frac{\mathbb{E}({{m}_{i}})}{2}+{m}\right)$
$\displaystyle\leq\exp\left(-\ln\left(\frac{2n}{\varepsilon}\right)\right)=\frac{\varepsilon}{2n},$

where the last inequality follows from (95). By the union bound, the
probability that all items participate in at least ${m}$ tests can be bounded
from below by

$1-\Pr\left(\bigcup\limits_{i\in{\cal N}}\mathcal{E}_{i}\right)\geq
1-\sum\limits_{i\in{\cal
N}}\Pr(\mathcal{E}_{i})>1-\frac{\varepsilon}{2n}\times
n=1-\frac{\varepsilon}{2}.$

###  -2 Proof of Lemma 5

To begin with, assume that each item participates in at least ${m}$ tests,
i.e., ${{m}_{i}}\geq{m}$ for all items $i$. As discussed in Decoding Rule $1$,
we identify item $i$ via (16). Two types of error can happen:

  1. 1.

Item $i$ is non-defective, but is identified as defective, i.e., false alarm;

  2. 2.

Item $i$ is defective, but is identified as non-defective, i.e., missed
detection.

We will bound the probabilities of $1)$ and $2)$ occuring separately as
follows. For notational simplicity, let ${\rho}={P(-,{q})}$,
${\nu}={P(+,{q})}$, ${\Delta}={\Delta({q})}$, ${P_{\min}}={P_{\min}({q})}$.
Recall that by Definition 3, ${\Delta}={\nu}-{\rho}$.

####  -21 False alarm for item $i$

In this scenario, each test outcome is positive with probability ${\rho}$, and

$\frac{{{m}_{i}^{+}}}{{{m}_{i}}}>\frac{{\rho}+{\nu}}{2}.$ (96)

Let ${P_{\text{FA}}}$ denote the probability of this false alarm. Since the
test outcomes are independent due to the tests being constructed in an i.i.d.
manner, ${{m}_{i}^{+}}\sim\text{Binomial}({{m}_{i}},{\rho})$. From Fact 1,
${P_{\text{FA}}}$ can be bounded as

$\displaystyle{P_{\text{FA}}}$
$\displaystyle=\Pr\left(\frac{{{m}_{i}^{+}}}{{{m}_{i}}}>\frac{{\rho}+{\nu}}{2}\right)$
$\displaystyle=\Pr\left({{m}_{i}^{+}}>\left(1+\frac{{\Delta}}{2{\rho}}\right){\rho}{{m}_{i}}\right)$
$\displaystyle\leq\exp\left(-\frac{1}{3}\times\frac{{\Delta}^{2}}{4{\rho}^{2}}\times{\rho}{{m}_{i}}\right)$
$\displaystyle=\exp\left(-\frac{{\Delta}^{2}}{12{\rho}}{{m}_{i}}\right)$
$\displaystyle\leq\exp\left(-\frac{{\Delta}^{2}}{12{\rho}}{m}\right).$ (97)

On the other hand, we also have
${{m}_{i}^{-}}\sim\text{Binomial}({{m}_{i}},1-{\rho})$. From Fact 1,
${P_{\text{FA}}}$ can also be bounded as

$\displaystyle{P_{\text{FA}}}$
$\displaystyle=\Pr\left(\frac{{{m}_{i}^{+}}}{{{m}_{i}}}>\frac{{\rho}+{\nu}}{2}\right)$
$\displaystyle=\Pr\left(\frac{{{m}_{i}^{-}}}{{{m}_{i}}}<1-\frac{{\rho}+{\nu}}{2}\right)$
$\displaystyle=\Pr\left({{m}_{i}^{-}}<\left(1-\frac{{\Delta}}{2(1-{\rho})}\right)(1-{\rho}){{m}_{i}}\right)$
$\displaystyle\leq\exp\left(-\frac{1}{3}\times\frac{{\Delta}^{2}}{4(1-{\rho})^{2}}(1-{\rho}){{m}_{i}}\right)$
$\displaystyle=\exp\left(-\frac{{\Delta}^{2}}{12(1-{\rho})}{{m}_{i}}\right)$
$\displaystyle\leq\exp\left(-\frac{{\Delta}^{2}}{12(1-{\rho})}{m}\right).$
(98)

Combining (-21) and (-21), we obtain

$\displaystyle{P_{\text{FA}}}$
$\displaystyle\leq\exp\left(-\frac{{\Delta}^{2}}{12\min\\{{\rho},1-{\rho}\\}}{m}\right)$
$\displaystyle\leq\exp\left(-\frac{{\Delta}^{2}}{12{P_{\min}}}{m}\right)$
$\displaystyle\leq\frac{\varepsilon}{2n},$ (99)

where the second inequality follows from (7) and (8); the last inequality
follows by substituting the definition of ${m}$ in (11).

####  -22 Missed detection for item $i$

The calculations are similar to those above analyzing the probability of a
false alarm for item $i$. In this case, each test outcome is positive with
probability ${\nu}$, and

$\frac{{{m}_{i}^{+}}}{{{m}_{i}}}\leq\frac{{\rho}+{\nu}}{2}.$ (100)

Let ${P_{\text{MD}}}$ denote the probability of this false non-defective.
Again since the test outcomes are independent, we have
${{m}_{i}^{+}}\sim\text{Binomial}({{m}_{i}},{\nu})$. From Fact 1, we can bound
${P_{\text{MD}}}$ as

$\displaystyle{P_{\text{MD}}}$
$\displaystyle=\Pr\left(\frac{{{m}_{i}^{+}}}{{{m}_{i}}}\leq\frac{{\rho}+{\nu}}{2}\right)$
$\displaystyle=\Pr\left({{m}_{i}^{+}}\leq\left(1-\frac{{\Delta}}{2{\nu}}\right){\nu}{{m}_{i}}\right)$
$\displaystyle\leq\exp\left(-\frac{1}{3}\times\frac{{\Delta}^{2}}{4{\nu}^{2}}\times{\nu}{{m}_{i}}\right)$
$\displaystyle=\exp\left(-\frac{{\Delta}^{2}}{12{\nu}}{{m}_{i}}\right)$
$\displaystyle\leq\exp\left(-\frac{{\Delta}^{2}}{12{\nu}}{m}\right).$ (101)

From another perspective,
${{m}_{i}^{-}}\sim\text{Binomial}({{m}_{i}},1-{\nu})$. From Fact 1, we can
also bound ${P_{\text{MD}}}$ as

$\displaystyle{P_{\text{MD}}}$
$\displaystyle=\Pr\left(\frac{{{m}_{i}^{+}}}{{{m}_{i}}}\leq\frac{{\rho}+{\nu}}{2}\right)$
$\displaystyle=\Pr\left(\frac{{{m}_{i}^{-}}}{{{m}_{i}}}\geq
1-\frac{{\rho}+{\nu}}{2}\right)$
$\displaystyle=\Pr\left({{m}_{i}^{-}}\geq\left(1+\frac{{\Delta}}{2(1-{\nu})}\right)(1-{\nu}){{m}_{i}}\right)$
$\displaystyle\leq\exp\left(-\frac{1}{3}\times\frac{{\Delta}^{2}}{4(1-{\nu})^{2}}(1-{\nu}){{m}_{i}}\right)$
$\displaystyle=\exp\left(-\frac{{\Delta}^{2}}{12(1-{\nu})}{{m}_{i}}\right)$
$\displaystyle\leq\exp\left(-\frac{{\Delta}^{2}}{12(1-{\nu})}{m}\right).$
(102)

Combining (-22) and (-22), we see that

$\displaystyle{P_{\text{MD}}}$
$\displaystyle\leq\exp\left(-\frac{{\Delta}^{2}}{12\min\\{{\nu},1-{\nu}\\}}{m}\right)$
$\displaystyle\leq\exp\left(-\frac{{\Delta}^{2}}{12{P_{\min}}}{m}\right)$
$\displaystyle\leq\frac{\varepsilon}{2n},$ (103)

where the second inequality follows from (7) and (8); the last inequality
follows from the definition of ${m}$ in (11).

From (-21) and (-22) we conclude that for any item $i\in\mathcal{N}$, the
probability of misidentification (either false alarm or missed detection) is
smaller than $\frac{\varepsilon}{2n}$. Therefore, when all items participate
in at least ${m}$ tests, by the union bound the probability that all items are
correctly identified is bounded from below by

$1-\frac{\varepsilon}{2n}\times n=1-\frac{\varepsilon}{2},$ (104)

which concludes the proof of Lemma 5.

###  -3 Proof of Lemma 6

Recall that in (29), $T$ was chosen to satisfy $T\geq\frac{13}{6(1-{q})}{s}$.
Consider an arbitrary item $i\in{\cal N}$. Since each item does not
participate in a test i.i.d. with probability $1-{q}$, the expected number of
tests without item $i$ is

$\displaystyle\mathbb{E}({{s}_{i}})$ $\displaystyle=(1-{q})T$
$\displaystyle\geq\frac{13}{6}{s}$
$\displaystyle=2{s}+\frac{1}{6}\times\frac{12{P_{\min}({q})}}{({\nabla({q})})^{2}}\ln\left(\frac{2n}{\varepsilon}\right)$
$\displaystyle\geq 2{s}+2\ln\left(\frac{2n}{\varepsilon}\right),$ (105)

where the third line follows from the definition of ${s}$ in (12); the last
line follows from (10).

Let ${\hat{\mathcal{E}}}_{i}$ be the event that item $i$ participates in more
than $T-{s}$. In other words, the number of tests without item $i$ is less
than ${s}$. By Fact 1, we have

$\displaystyle\Pr({\hat{\mathcal{E}}}_{i})$
$\displaystyle=\Pr\left({{s}_{i}}<{s}=\left(1-\frac{\mathbb{E}({{s}_{i}})-{s}}{\mathbb{E}({{s}_{i}})}\right)\mathbb{E}({{s}_{i}})\right)$
$\displaystyle\leq\exp\left(-\left(\frac{\mathbb{E}({{s}_{i}})-{s}}{\mathbb{E}({{s}_{i}})}\right)^{2}\,\frac{\mathbb{E}({{s}_{i}})}{2}\right)$
$\displaystyle=\exp\left(-\frac{\mathbb{E}({{s}_{i}})}{2}+{s}-\frac{{s}^{2}}{2\mathbb{E}({{s}_{i}})}\right)$
$\displaystyle\leq\exp\left(-\frac{\mathbb{E}({{s}_{i}})}{2}+{s}\right)$
$\displaystyle\leq\exp\left(-\ln\left(\frac{2n}{\varepsilon}\right)\right)=\frac{\varepsilon}{2n},$

where the last inequality follows from (105). By the union bound, the
probability that each item participates in at most $T-{s}$ tests can be
bounded from below by

$1-\Pr\left(\bigcup\limits_{i}{\hat{\mathcal{E}}}_{i}\right)\geq
1-\sum\limits_{i}\Pr({\hat{\mathcal{E}}}_{i})>1-\frac{\varepsilon}{2n}\times
n=1-\frac{\varepsilon}{2}.$ (106)

###  -4 Proof of Lemma 7

To begin with, assume that each item participates in at most $T-{s}$ tests,
i.e., ${{s}_{i}}\geq{s}$ for all items $i$. As discussed in Decoding Rule $2$,
we identify item $i$ via (17). Two types of error can happen:

  1. 1.

Item $i$ is non-defective, but is identified as defective, i.e., false alarm;

  2. 2.

Item $i$ is defective, but is identified as non-defective, i.e., missed
detection.

We will bound the probabilities of $1)$ and $2)$ occuring separately as
follows. For notational simplicity, let ${\hat{{\rho}}}={Q(-,{q})}$,
${\hat{{\nu}}}={Q(+,{q})}$, ${\nabla}={\nabla({q})}$,
${P_{\min}}={P_{\min}({q})}$. Recall that by Definition 3,
${\nabla}={\hat{{\rho}}}-{\hat{{\nu}}}$.

####  -41 False alarm for item $i$

In this scenario, each test outcome is positive with probability
${\hat{{\rho}}}$, and

$\frac{{{s}_{i}^{+}}}{{{s}_{i}}}\leq\frac{{\hat{{\rho}}}+{\hat{{\nu}}}}{2}.$
(107)

Let ${\hat{P}_{\text{FA}}}$ denote the probability of this false alarm. Since
the test outcomes are independent due to the tests being constructed in an
i.i.d. manner, ${{s}_{i}^{+}}\sim\text{Binomial}({{s}_{i}},{\hat{{\rho}}})$.
From Fact 1, ${\hat{P}_{\text{FA}}}$ can be bounded as

$\displaystyle{\hat{P}_{\text{FA}}}$
$\displaystyle=\Pr\left(\frac{{{s}_{i}^{+}}}{{{s}_{i}}}\leq\frac{{\hat{{\rho}}}+{\hat{{\nu}}}}{2}\right)$
$\displaystyle=\Pr\left({{s}_{i}^{+}}\leq\left(1-\frac{{\nabla}}{2{\hat{{\rho}}}}\right){\hat{{\rho}}}{{s}_{i}}\right)$
$\displaystyle\leq\exp\left(-\frac{1}{3}\times\frac{{\nabla}^{2}}{4{\hat{{\rho}}}^{2}}\times{\hat{{\rho}}}{{s}_{i}}\right)$
$\displaystyle=\exp\left(-\frac{{\nabla}^{2}}{12{\hat{{\rho}}}}{{s}_{i}}\right)$
$\displaystyle\leq\exp\left(-\frac{{\nabla}^{2}}{12{\hat{{\rho}}}}{s}\right).$
(108)

On the other hand, we also have
${{s}_{i}^{-}}\sim\text{Binomial}({{s}_{i}},1-{\hat{{\rho}}})$. From Fact 1,
${\hat{P}_{\text{FA}}}$ can also be bounded as

$\displaystyle{\hat{P}_{\text{FA}}}$
$\displaystyle=\Pr\left(\frac{{{s}_{i}^{+}}}{{{s}_{i}}}\leq\frac{{\hat{{\rho}}}+{\hat{{\nu}}}}{2}\right)$
$\displaystyle=\Pr\left(\frac{{{s}_{i}^{-}}}{{{s}_{i}}}\geq
1-\frac{{\hat{{\rho}}}+{\hat{{\nu}}}}{2}\right)$
$\displaystyle=\Pr\left({{s}_{i}^{-}}\geq\left(1+\frac{{\nabla}}{2(1-{\hat{{\rho}}})}\right)(1-{\hat{{\rho}}}){{s}_{i}}\right)$
$\displaystyle\leq\exp\left(-\frac{1}{3}\times\frac{{\nabla}^{2}}{4(1-{\hat{{\rho}}})^{2}}(1-{\hat{{\rho}}}){{s}_{i}}\right)$
$\displaystyle=\exp\left(-\frac{{\nabla}^{2}}{12(1-{\hat{{\rho}}})}{{s}_{i}}\right)$
$\displaystyle\leq\exp\left(-\frac{{\nabla}^{2}}{12(1-{\hat{{\rho}}})}{s}\right).$
(109)

Combining (-41) and (-41), we obtain

${\hat{P}_{\text{FA}}}\leq\exp\left(-\frac{{\nabla}^{2}}{12\min\\{{\hat{{\rho}}},1-{\hat{{\rho}}}\\}}{s}\right)\leq\exp\left(-\frac{{\nabla}^{2}}{12{P_{\min}}}{s}\right)\leq\frac{\varepsilon}{2n},$
(110)

where the second inequality follows from (7) and (8); the last inequality
follows by substituting the definition of ${s}$ in (12).

####  -42 Missed detection for item $i$

The calculations are similar to those above analyzing the probability of a
false alarm for item $i$. In this case, each test outcome is positive with
probability ${\hat{{\nu}}}$, and

$\frac{{{s}_{i}^{+}}}{{{s}_{i}}}>\frac{{\hat{{\rho}}}+{\hat{{\nu}}}}{2}.$
(111)

Let ${\hat{P}_{\text{MD}}}$ denote the probability of this false non-
defective. Again since the outcomes are independent, we have
${{s}_{i}^{+}}\sim\text{Binomial}({{s}_{i}},{\hat{{\nu}}})$. From Fact 1, we
can bound ${\hat{P}_{\text{MD}}}$ as

$\displaystyle{\hat{P}_{\text{MD}}}$
$\displaystyle=\Pr\left(\frac{{{s}_{i}^{+}}}{{{s}_{i}}}>\frac{{\hat{{\rho}}}+{\hat{{\nu}}}}{2}\right)$
$\displaystyle=\Pr\left({{s}_{i}^{+}}>\left(1+\frac{{\nabla}}{2{\hat{{\nu}}}}\right){\hat{{\nu}}}{{s}_{i}}\right)$
$\displaystyle\leq\exp\left(-\frac{1}{3}\times\frac{{\nabla}^{2}}{4{\hat{{\nu}}}^{2}}\times{\hat{{\nu}}}{{s}_{i}}\right)$
$\displaystyle=\exp\left(-\frac{{\nabla}^{2}}{12{\hat{{\nu}}}}{{s}_{i}}\right)$
$\displaystyle\leq\exp\left(-\frac{{\nabla}^{2}}{12{\hat{{\nu}}}}{s}\right).$
(112)

From another perspective,
${{s}_{i}^{-}}\sim\text{Binomial}({{s}_{i}},1-{\hat{{\nu}}})$. From Fact 1, we
can also bound ${\hat{P}_{\text{MD}}}$ as

$\displaystyle{\hat{P}_{\text{MD}}}$
$\displaystyle=\Pr\left(\frac{{{s}_{i}^{+}}}{{{s}_{i}}}>\frac{{\hat{{\rho}}}+{\hat{{\nu}}}}{2}\right)$
$\displaystyle=\Pr\left(\frac{{{s}_{i}^{-}}}{{{s}_{i}}}<1-\frac{{\hat{{\rho}}}+{\hat{{\nu}}}}{2}\right)$
$\displaystyle=\Pr\left({{s}_{i}^{-}}<\left(1-\frac{{\nabla}}{2(1-{\hat{{\nu}}})}\right)(1-{\hat{{\nu}}}){{s}_{i}}\right)$
$\displaystyle\leq\exp\left(-\frac{1}{3}\times\frac{{\nabla}^{2}}{4(1-{\hat{{\nu}}})^{2}}(1-{\hat{{\nu}}}){{s}_{i}}\right)$
$\displaystyle=\exp\left(-\frac{{\nabla}^{2}}{12(1-{\hat{{\nu}}})}{{s}_{i}}\right)$
$\displaystyle\leq\exp\left(-\frac{{\nabla}^{2}}{12(1-{\hat{{\nu}}})}{s}\right).$
(113)

Combining (-42) and (-42), we see that

${\hat{P}_{\text{MD}}}\leq\exp\left(-\frac{{\nabla}^{2}}{12\min\\{{\hat{{\nu}}},1-{\hat{{\nu}}}\\}}{s}\right)\leq\exp\left(-\frac{{\nabla}^{2}}{12{P_{\min}}}{s}\right)\leq\frac{\varepsilon}{2n},$
(114)

where the second inequality follows from (7) and (8); the last inequality
follows from the definition of ${s}$ in (12).

From (110) and (114) we conclude that for any item $i\in\mathcal{N}$, the
probability of misidentification (either false alarm or missed detection) is
smaller than $\frac{\varepsilon}{2n}$. Therefore, when each item participates
in at most $T-{s}$ tests, by the union bound the probability that all items
are correctly identified is bounded from below by

$1-\frac{\varepsilon}{2n}\times n=1-\frac{\varepsilon}{2},$ (115)

which concludes the proof of Lemma 7.

##  Appendix D Proof of Proposition 3

From (14), we know that the value of ${\hat{\Gamma}}({q})$ depends on the
choice of ${q}$. For ${q}\in\left(\frac{1}{d},\frac{d-1}{d}\right)$ with
$d\geq 3$, the following result asserts that by choosing ${q}$ properly, we
can give an explicit bound on the value of ${\hat{\Gamma}}({q})$.

###### Proposition 5

Let $d\geq 3$. For any ${L}^{\prime},{U}^{\prime}\in\\{1,\dots,d-1\\}$ with
${L}^{\prime}<{U}^{\prime}$ and $f({L}^{\prime})<f({U}^{\prime})$, there
exists ${q}_{0}\in\left(\frac{{L}^{\prime}}{d},\frac{{U}^{\prime}}{d}\right)$
such that ${\hat{\Gamma}}({q}_{0})$ in (14) satisfies

${\hat{\Gamma}}({q}_{0})\leq
31334.75\times\frac{1}{{\alpha}^{2}}\left(\frac{{U}^{\prime}-{L}^{\prime}}{f({U}^{\prime})-f({L}^{\prime})}\right)^{2}d\log\left(\frac{2n}{\varepsilon}\right)$
(116)

where
${\alpha}:=\frac{1}{2}\min\left\\{{U}^{\prime}-{L}^{\prime},\sqrt{{L}^{\prime}},\sqrt{d-{U}^{\prime}}\right\\}$.

###### Proof:

The proof of Proposition 5 is rather involved and is deferred to Appendix E. ∎

Below, the boundary points are handled separately.

###### Proposition 6

  1. 1.

By choosing ${q}_{0}=\frac{1}{d+1}$, which implicitly requires
$f(1)-f(0)>0$,999If $f(1)-f(0)=0$ or $f(d)-f(d-1)=0$, we can choose ${q}_{0}$
as in Proposition 5. ${\hat{\Gamma}}({q}_{0})$ in (14) satisfies

${\hat{\Gamma}}({q}_{0})\leq\frac{266.45}{(f(1)-f(0))^{2}}d\log\left(\frac{2n}{\varepsilon}\right).$
(117)

  2. 2.

By choosing ${q}_{0}=\frac{d}{d+1}$, which implicitly requires
$f(d)-f(d-1)>0$,${}^{\ref{fn:boundary:cases}}$ ${\hat{\Gamma}}({q}_{0})$ in
(14) satisfies

${\hat{\Gamma}}({q}_{0})\leq\frac{266.45}{(f(d)-f(d-1))^{2}}d\log\left(\frac{2n}{\varepsilon}\right).$
(118)

###### Proof:

We prove the first part of the lemma directly. Upon choosing
${q}_{0}=\frac{1}{d+1}$, we have from (83) that

$\displaystyle{\Delta}({q}_{0})$
$\displaystyle=\sum\limits_{j=0}^{d-1}\binom{d-1}{j}{q}_{0}^{j}(1-{q}_{0})^{d-j}(f(j+1)-f(j))$
$\displaystyle\geq{q}_{0}^{0}(1-{q}_{0})^{d}(f(1)-f(0))$
$\displaystyle\geq\frac{f(1)-f(0)}{e},$

where the last inequality follows from the fact that
$\left(1-\frac{1}{d+1}\right)^{d}$ is decreasing in $d$ and
$\lim_{d\to\infty}\left(1-\frac{1}{d+1}\right)^{d}=\frac{1}{e}$. Then,
plugging this into (14), we obtain

$\displaystyle{\hat{\Gamma}}({q}_{0})=\frac{36.06(1-{q}_{0})}{{q}_{0}({\Delta}({q}_{0}))^{2}}\log\left(\frac{2n}{\varepsilon}\right)\leq\frac{266.45}{(f(1)-f(0))^{2}}d\log\left(\frac{2n}{\varepsilon}\right),$

which yields (117) as desired.

We now turn to prove the second part of the lemma. Under the choice
${q}_{0}=\frac{d}{d+1}$, we have from (83) that

$\displaystyle{\Delta}({q}_{0})$
$\displaystyle=\sum\limits_{j=0}^{d-1}\binom{d-1}{j}{q}_{0}^{j}(1-{q}_{0})^{d-j}(f(j+1)-f(j))$
$\displaystyle\geq{q}_{0}^{d-1}(1-{q}_{0})^{1}(f(d)-f(d-1))$
$\displaystyle=\left(1-\frac{1}{d+1}\right)^{d}\frac{f(d)-f(d-1)}{d}$
$\displaystyle\geq\frac{f(d)-f(d-1)}{ed}.$

Then, plugging this into (14), we obtain

$\displaystyle{\hat{\Gamma}}({q}_{0})=\frac{36.06(1-{q}_{0})}{{q}_{0}({\Delta}({q}_{0}))^{2}}\log\left(\frac{2n}{\varepsilon}\right)\leq\frac{266.45}{(f(d)-f(d-1))^{2}}d\log\left(\frac{2n}{\varepsilon}\right).$

This completes the proof of Proposition 6. ∎

Proposition 3 is proved by unifying Propositions 5 and 6. To begin with,
consider any ${L},{U}\in\\{0,\dots,d\\}$ such that ${L}<{U}$ and
$f({L})<f({U})$.101010If there is no such pair of $({L},{U})$, we have
$f(x)$=constant for all $x$. In this case, the defective set $\mathcal{D}$ can
never be recovered. To simplify the notation, define

$\displaystyle{\beta}:=\min\left\\{{U}-{L},\sqrt{{L}+1},\sqrt{d-{U}+1}\right\\}.$
(119)

Consider the following four cases:

  1. i)

$1\leq{L}<{U}\leq d-1$;

  2. ii)

$0={L}<{U}\leq d-1$;

  3. iii)

$1\leq{L}<{U}=d$;

  4. iv)

$0={L}<{U}=d$.

Case i): For $1\leq{L}<{U}\leq d-1$, we have

$\displaystyle{\beta}$
$\displaystyle=\min\left\\{{U}-{L},\sqrt{{L}+1},\sqrt{d-{U}+1}\right\\}\leq\min\left\\{\sqrt{2}({U}-{L}),\sqrt{2{L}},\sqrt{2(d-{U})}\right\\}.$
(120)

Then, applying Proposition 5 with ${L}^{\prime}={L}$ and ${U}^{\prime}={U}$,
we have that ${\beta}\leq 2\sqrt{2}{\alpha}$ and

$\displaystyle{\hat{\Gamma}}({q}_{0})$ $\displaystyle\leq
250678\times\frac{1}{{\beta}^{2}}\left(\frac{{U}-{L}}{f({U})-f({L})}\right)^{2}d\log\left(\frac{2n}{\varepsilon}\right)$
$\displaystyle\leq{376017\times\frac{1}{{\beta}^{2}}\left(\frac{{U}-{L}}{f({U})-f({L})}\right)^{2}d\log\left(\frac{2n}{\varepsilon}\right)}$
(121)

for some ${q}_{0}\in\left(\frac{{L}}{d},\frac{{U}}{d}\right)$.

Case ii): For $0={L}<{U}\leq d-1$, we have ${\beta}=1$ by definition (119). We
proceed with two further sub-cases.

  * •

${U}=1$: From Proposition 6 we see that

$\displaystyle{\hat{\Gamma}}({q}_{0})$
$\displaystyle\leq\frac{266.45}{(f(1)-f(0))^{2}}d\log\left(\frac{2n}{\varepsilon}\right)$
$\displaystyle\leq{376017\times\frac{1}{{\beta}^{2}}\left(\frac{{U}-{L}}{f({U})-f({L})}\right)^{2}d\log\left(\frac{2n}{\varepsilon}\right)}$
(122)

for ${q}_{0}=\frac{1}{d+1}\in\left(\frac{{L}}{d},\frac{{U}}{d}\right)$.

  * •

${U}\geq 2$: Both Propositions 5 and 6 are applicable, we prefer to choose the
one with smaller upper bound. Applying Proposition 5 with ${L}^{\prime}=1$ and
${U}^{\prime}={U}$, we have that ${{\alpha}}=\frac{1}{2}$ and

$\displaystyle{\hat{\Gamma}}({q}_{0}^{\prime})\leq
125339\times\left(\frac{{U}-1}{f({U})-f(1)}\right)^{2}d\log\left(\frac{2n}{\varepsilon}\right)$
(123)

for some ${q}_{0}^{\prime}\in\left(\frac{1}{d},\frac{{U}}{d}\right)$. On the
other hand, Proposition 6 gives

$\displaystyle{\hat{\Gamma}}({q}_{0}^{\prime\prime})\leq\frac{266.45}{(f(1)-f(0))^{2}}d\log\left(\frac{2n}{\varepsilon}\right)$
(124)

for
${q}_{0}^{\prime\prime}=\frac{1}{d+1}\in\left(\frac{{L}}{d},\frac{1}{d}\right)$.
Since

$\displaystyle\min\left\\{\frac{1}{(f(1)-f(0))^{2}},\frac{({U}-1)^{2}}{(f({U})-f(1))^{2}}\right\\}$
$\displaystyle\leq\frac{1+({U}-1)^{2}}{(f(1)-f(0))^{2}+(f({U})-f(1))^{2}}$
$\displaystyle\leq\frac{2{U}^{2}}{(f({U})-f(0))^{2}},$ (125)

it follows that

$\displaystyle{\hat{\Gamma}}({q}_{0})$
$\displaystyle\leq\min\left\\{125339\times\left(\frac{{U}-1}{f({U})-f(1)}\right)^{2}d\log\left(\frac{2n}{\varepsilon}\right),\frac{576.96}{(f(1)-f(0))^{2}}d\log\left(\frac{2n}{\varepsilon}\right)\right\\}$
$\displaystyle\leq
125339\times\min\left\\{\frac{1}{(f(1)-f(0))^{2}},\frac{({U}-1)^{2}}{(f({U})-f(1))^{2}}\right\\}\times
d\log\left(\frac{2n}{\varepsilon}\right)$ $\displaystyle\leq
250678\times\frac{{U}^{2}}{(f({U})-f(0))^{2}}d\log\left(\frac{2n}{\varepsilon}\right)$
$\displaystyle=250678\times\frac{1}{{\beta}^{2}}\left(\frac{{U}-{L}}{f({U})-f({L})}\right)^{2}d\log\left(\frac{2n}{\varepsilon}\right)$
$\displaystyle\leq{376017\times\frac{1}{{\beta}^{2}}\left(\frac{{U}-{L}}{f({U})-f({L})}\right)^{2}d\log\left(\frac{2n}{\varepsilon}\right)}$
(126)

for some ${q}_{0}\in\left(\frac{{L}}{d},\frac{{U}}{d}\right)$.

Case iii): For $1\leq{L}<{U}=d$, we have ${\beta}=1$ by definition (119). The
proof is similar to Case ii). Consider the following two sub-cases.

  * •

${L}=d-1$: From Proposition 6 we see that

$\displaystyle{\hat{\Gamma}}({q}_{0})$
$\displaystyle\leq\frac{266.45}{(f(d)-f(d-1))^{2}}d\log\left(\frac{2n}{\varepsilon}\right)$
$\displaystyle\leq{376017\times\frac{1}{{\beta}^{2}}\left(\frac{{U}-{L}}{f({U})-f({L})}\right)^{2}d\log\left(\frac{2n}{\varepsilon}\right)}$
(127)

for ${q}_{0}=\frac{d}{d+1}\in\left(\frac{{L}}{d},\frac{{U}}{d}\right)$.

  * •

${L}\leq d-2$: Applying Proposition 5 with ${L}^{\prime}={L}$ and
${U}^{\prime}=d-1$, we have that ${{\alpha}}=\frac{1}{2}$ and

$\displaystyle{\hat{\Gamma}}({q}_{0}^{\prime})\leq
125339\times\left(\frac{d-1-{L}}{f(d-1)-f({L})}\right)^{2}d\log\left(\frac{2n}{\varepsilon}\right)$
(128)

for some ${q}_{0}^{\prime}\in\left(\frac{{L}}{d},\frac{d-1}{d}\right)$. On the
other hand, Proposition 6 gives

$\displaystyle{\hat{\Gamma}}({q}_{0}^{\prime\prime})\leq\frac{266.45}{(f(d)-f(d-1))^{2}}d\log\left(\frac{2n}{\varepsilon}\right)$
(129)

for
${q}_{0}^{\prime\prime}=\frac{1}{d+1}\in\left(\frac{d-1}{d},\frac{{U}}{d}\right)$.
Since

$\displaystyle\min\left\\{\frac{1}{(f(d)-f(d-1))^{2}},\frac{(d-1-{L})^{2}}{(f(d-1)-f({L}))^{2}}\right\\}$
$\displaystyle\leq\frac{1+(d-1-{L})^{2}}{(f(d)-f(d-1))^{2}+(f(d-1)-f({L}))^{2}}$
$\displaystyle\leq\frac{2(d-{L})^{2}}{(f(d)-f({L}))^{2}},$ (130)

it follows that

$\displaystyle{\hat{\Gamma}}({q}_{0})$
$\displaystyle\leq\min\left\\{125339\times\left(\frac{d-1-{L}}{f(d-1)-f({L})}\right)^{2}d\log\left(\frac{2n}{\varepsilon}\right),\frac{266.45}{(f(d)-f(d-1))^{2}}d\log\left(\frac{2n}{\varepsilon}\right)\right\\}$
$\displaystyle\leq
125339\times\min\left\\{\frac{1}{(f(d)-f(d-1))^{2}},\frac{(d-1-{L})^{2}}{(f(d-1)-f({L}))^{2}}\right\\}\times
d\log\left(\frac{2n}{\varepsilon}\right)$ $\displaystyle\leq
250678\times\frac{(d-{L})^{2}}{(f(d)-f({L}))^{2}}d\log\left(\frac{2n}{\varepsilon}\right)$
$\displaystyle=250678\times\frac{1}{{\beta}^{2}}\left(\frac{{U}-{L}}{f({U})-f({L})}\right)^{2}d\log\left(\frac{2n}{\varepsilon}\right)$
$\displaystyle\leq{376017\times\frac{1}{{\beta}^{2}}\left(\frac{{U}-{L}}{f({U})-f({L})}\right)^{2}d\log\left(\frac{2n}{\varepsilon}\right)}$
(131)

for some ${q}_{0}\in\left(\frac{{L}}{d},\frac{{U}}{d}\right)$.

Case iv): For $0={L}<{U}=d$, we have ${\beta}=1$ by definition (119). The
proof is similar to Case ii). Consider three sub-cases:

  * •

$d=1$: In this sub-case, the two bounds in Proposition 6 are identical and
give

$\displaystyle{\hat{\Gamma}}({q}_{0})$
$\displaystyle\leq\frac{266.45}{(f(1)-f(0))^{2}}d\log\left(\frac{2n}{\varepsilon}\right)$
$\displaystyle\leq{376017\times\frac{1}{{\beta}^{2}}\left(\frac{{U}-{L}}{f({U})-f({L})}\right)^{2}d\log\left(\frac{2n}{\varepsilon}\right)}$
(132)

for ${q}_{0}=\frac{1}{d+1}\in\left(\frac{{L}}{d},\frac{{U}}{d}\right)$.

  * •

$d=2$: From Proposition 6 we see that