グループテスト
One of the key insights in non-adaptive group testing is that significant gains can be made by eliminating the requirement that the group-testing procedure be certain to succeed (the "combinatorial" problem), but rather permit it to have some low but non-zero probability of mis-labelling each item (the "probabilistic" problem). It is known that as the number of defective items approaches the total number of items, exact combinatorial solutions require significantly more tests than probabilistic solutions — even probabilistic solutions permitting only an asymptotically small probability of error. O \left(d^2\log_d n\right) for deterministic designs, compared to t = O(d\log_2 n) for designs that allow arbitrarily small probabilities of error (as d \to \infty and n \to \infty).
In this vein, Chan et al. (2011) introduced COMP, a probabilistic algorithm that requires no more than t = ed(1+\delta)\ln(n) tests to find up to d defectives in n items with a probability of error no more than n^{-\delta}. This is within a constant factor of the t = O(d\log_2 n) lower bound.
Chan et al. (2011) also provided a generalisation of COMP to a simple noisy model, and similarly produced an explicit performance bound, which was again only a constant (dependent on the likelihood of a failed test) above the corresponding lower bound. In general, the number of tests required in the Bernoulli noise case is a constant factor larger than in the noiseless case.
Aldridge, Baldassini and Johnson (2014) produced an extension of the COMP algorithm that added additional post-processing steps. They showed that the performance of this new algorithm, called DD, strictly exceeds that of COMP, and that DD is 'essentially optimal' in scenarios where d^2 \geq n, by comparing it to a hypothetical algorithm that defines a reasonable optimum. The performance of this hypothetical algorithm suggests that there is room for improvement when d^2 < n, as well as suggesting how much improvement this might be.
This section formally defines the notions and terms relating to group testing.
The input vector, \mathbf{x} = (x_1, x_2, \dots, x_n), is defined to be a binary vector of length n (that is, \mathbf{x} \in \{0,1\}^n), with the j-th item being called defective if and only if x_j= 1. Further, any non-defective item is referred called a 'good' item.
\mathbf{x} is intended to describe the (unknown) set of defective items. The key property of \mathbf{x} is that it is an implicit input. That is to say, there is no direct knowledge of what the entries of \mathbf{x} are, other than that which can be inferred via some series of 'tests'. This leads on to the next definition.
Let \mathbf{x} be an input vector. A set, S \subseteq \{ 1, 2, \dots, n \} is called a test. When testing is noiseless, the result of a test is positive when there exists j \in S such that x_j = 1, and the result is negative otherwise.
Therefore, the goal of group testing is to come up with a method for choosing a 'short' series of tests that allow \mathbf{x} to be determined, either exactly or with a high degree of certainty.
A group-testing algorithm is said to make an error if it incorrectly labels an item (that is, labels any defective item as non-defective or vice versa). This is not the same thing as the result of a group test being incorrect. An algorithm is called zero-error if the probability that it makes an error is zero.One must be careful to distinguish between when a test reports a false result and when the group-testing procedure fails as a whole. It is both possible to make an error with no incorrect tests and to not make an error with some incorrect tests. Most modern combinatorial algorithms have some non-zero probability of error (even with no erroneous tests), since this significantly decreases the number of tests needed.
t(d, n) denotes the minimum number of tests required to always find d defectives among n items with zero probability of error by any group-testing algorithm. For the same quantity but with the restriction that the algorithm is non-adaptive, the notation \bar{t}(d, n) is used.
Since it is always possible to resort to individual testing by setting S_j = \{j\} for each 1 \leq j \leq n, it must be that that \bar{t}(d, n) \leq n. Also, since any non-adaptive testing procedure can be written as an adaptive algorithm by simply performing all the tests without regard to their outcome, t(d, n) \leq \bar{t}(d, n). Finally, when 0 \neq d \neq n, there is at least one item whose defectiveness must be determined (by at least one test), and so 1 \leq t(d, n).
In summary (when assuming 0 \neq d \neq n), 1 \leq t(d,n) \leq \bar{t}(d, n) \leq n .In fact it is possible to do much better. For example, Li's s-stage algorithm gives an explicit construction were t \leq \frac{e}{\log_2 e} d \log_2{(n/d)}.
A lower bound on the number of tests needed can be described using the notion of sample space, denoted \mathcal{S}, which is simply the set of possible placements of defectives. For any group testing problem with sample space \mathcal{S} and any group-testing algorithm, it can be shown that t \geq \lceil \log_2 \rceil, where t is the minimum number of tests required to identify all defectives with a zero probability of error. This is called the information lower bound. This bound is derived from the fact that after each test, \mathcal{S} is split into two disjoint subsets, each corresponding to one of the two possible outcomes of the test.
However, the information lower bound itself is usually unachievable, even for small problems. This is because the splitting of \mathcal{S} is not arbitrary, since it must be realisable by some test.
In fact, the information lower bound can be generalised to the case where there is a non-zero probability that the algorithm makes an error. In this form, the theorem gives us an upper bound on the probability of success based on the number of tests. For any group-testing algorithm that performs t tests, the probability of success, \mathbb{P}(\textrm{success}), satisfies \mathbb{P}(\textrm{success}) \leq t/\log_2{n \choose d}. This can be strengthened to: \mathbb{P}(\textrm{success}) \leq \frac{2^t}n \choose d.
Algorithms for non-adaptive group testing consist of two distinct phases. First, it is decided how many tests to perform and which items to include in each test.  In the second phase, often called the decoding step, the results of each group test are analysed to determine which items are likely to be defective. The first phase is usually encoded in a matrix as follows.
Suppose a non-adaptive group testing procedure for n items consists of the tests S_1, S_2, \dots, S_t for some t \in \mathbb{N}_{\geq 0}. The testing matrix for this scheme is the t \times n binary matrix, M, where (M)_{ij} = 1 if and only if j \in S_i (and is zero otherwise).
Thus each column of M represents an item and each row represents a test, with a 1 in the (i,j)\textrm{-th} entry indicating that the i\textrm{-th} test included the j\textrm{-th} item and a 0 indicating otherwise.
As well as the vector \mathbf{x} (of length n) that describes the unknown defective set, it is common to introduce the result vector, which describes the results of each test.
Let t be the number of tests performed by a non-adaptive algorithm. The result vector, \mathbf{y} = (y_1, y_2, \dots, y_t), is a binary vector of length t (that is, \mathbf{y} \in \{0,1\}^t) such that y_i= 1 if and only if the result of the i\textrm{-th} test was positive (i.e. contained at least one defective). M\mathbf {x}, where multiplication is logical AND (\wedge) and addition is logical OR (\vee). Here, \mathbf {y} will have a 1 in position i if and only if (M)_{i,j} and \mathbf {x} _{j} are both 1 for any j. That is, if and only if at least one defective item was included in the i\textrm{-th} test.
With these definitions, the non-adaptive problem can be reframed as follows: first a testing matrix is chosen, M, after which the vector \mathbf{y} is returned. Then the problem is to analyse \mathbf{y} to find some estimate for \mathbf{x}.
In the simplest noisy case, where there is a constant probability, q, that a group test will have an erroneous result, one considers a random binary vector, \mathbf{v}, where each entry has a probability q of being 1, and is 0 otherwise. The vector that is returned is then \hat{\mathbf{y} = \mathbf{y} + \mathbf{v}, with the usual addition on (\mathbb{Z}/2\mathbb{Z})^n (equivalently this is the element-wise XOR operation). A noisy algorithm must estimate \mathbf{x} using \hat{\mathbf{y} (that is, without direct knowledge of \mathbf{y}).
The matrix representation makes it possible to prove some bounds on non-adaptive group testing. The approach mirrors that of many deterministic designs, where d-separable matrices are considered, as defined below.
A binary matrix, M, is called d-separable if every Boolean sum (logical OR) of any d of its columns is distinct. Additionally, the notation \bar{d}-separable indicates that every sum of any of up to d of M's columns is distinct. (This is not the same as M being k-separable for every k \leq d.)
When M is a testing matrix, the property of being d-separable (\bar{d}-separable) is equivalent to being able to distinguish between (up to) d defectives. However, it does not guarantee that this will be straightforward. A stronger property, called d-disjunctness does.
A binary matrix, M is called d-disjunct if the Boolean sum of any d columns does not contain any other column. (In this context, a column A is said to contain a column B if for every index where B has a 1, A also has a 1.)
A useful property of d-disjunct testing matrices is that, with up to d defectives, every non-defective item will appear in at least one test whose outcome is negative. This means there is a simple procedure for finding the defectives: just remove every item that appears in a negative test.
Using the properties of d-separable and d-disjunct matrices the following can be shown for the problem of identifying d defectives among n total items.
The number of tests needed for an asymptotically small average probability of error scales as O(d\log_2 n).
The number of tests needed for an asymptotically small maximum probability of error scales as O(d^2 \log_2 n).
The number of tests needed for a zero probability of error scales as O \left(\frac{d^2 \log_2 n}{\log_2 d} \right).
The generalised binary-splitting algorithm is an essentially-optimal adaptive group-testing algorithm that finds d or fewer defectives among n items as follows:
If n \leq 2d - 2, test the n items individually. Otherwise, set l = n - d + 1 and \alpha = \lfloor \log_2{l/d} \rfloor.
Test a group of size 2^\alpha. If the outcome is negative, every item in the group is declared to be non-defective; set n := n - 2^\alpha and go to step 1. Otherwise, use a binary search to identify one defective and an unspecified number, called x, of non-defective items; set n := n - 1 - x and d := d - 1. Go to step 1.
The generalised binary-splitting algorithm requires no more than T tests where
T = \begin{cases}
n & n \leq 2d-2\\
(\alpha+2)d + p - 1 & n \geq 2d - 1
\end{cases}
.
For n/d large, it can be shown that T \rightarrow d \log_2(n/d), which compares favorably to the t = \frac{e}{\log_2 e}d\log_2 \left( \frac{n}{d} \right) tests required for Li's s-stage algorithm. In fact, the generalised binary-splitting algorithm is close to optimal in the following sense. When d \geq 2 it can be shown that T - B_I(d,n) \leq (d-1), where B_I(d,n) = \left\lceil \log_2 \sum_{i=0}^d {n \choose i} \right\rceil is the information lower bound.
Non-adaptive group-testing algorithms tend to assume that the number of defectives, or at least a good upper bound on them, is known. This quantity is denoted d in this section. If no bounds are known, there are non-adaptive algorithms with low query complexity that can help estimate d.