グループテスト
The result vector, y = ( y 1 , y 2 , ... , y t ) {\displaystyle \mathbf {y} =(y_{1},y_{2},\dots ,y_{t})} , is a binary vector of length t {\displaystyle t} (that is, y ∈ { 0 , 1 } t {\displaystyle \mathbf {y} \in \{0,1\}^{t}} ) such that y i = 1 {\displaystyle y_{i}=1} if and only if the result of the i -th {\displaystyle i{\textrm {-th}}} test was positive (i.e. contained at least one defective).
With these definitions, the non-adaptive problem can be reframed as follows: first a testing matrix is chosen, M {\displaystyle M} , after which the vector y {\displaystyle \mathbf {y} } is returned. Then the problem is to analyse y {\displaystyle \mathbf {y} } to find some estimate for x {\displaystyle \mathbf {x} } .
A lower bound on the number of tests needed can be described using the notion of sample space, denoted S {\displaystyle {\mathcal {S}}} , which is simply the set of possible placements of defectives. For any group testing problem with sample space S {\displaystyle {\mathcal {S}}} and any group-testing algorithm, it can be shown that t ≥ ⌈ log 2  | S | ⌉ {\displaystyle t\geq \lceil \log _{2}{|{\mathcal {S}}|}\rceil } , where t {\displaystyle t} is the minimum number of tests required to identify all defectives with a zero probability of error.
(This is not the same as M {\displaystyle M} being k {\displaystyle k} -separable for every k ≤ d {\displaystyle k\leq d} .)
When M {\displaystyle M} is a testing matrix, the property of being d {\displaystyle d} -separable ( d ̄ {\displaystyle {\bar {d}}} -separable) is equivalent to being able to distinguish between (up to) d {\displaystyle d} defectives. However, it does not guarantee that this will be straightforward. A stronger property, called d {\displaystyle d} -disjunctness does.
A binary matrix, M {\displaystyle M} is called d {\displaystyle d} -disjunct if the Boolean sum of any d {\displaystyle d} columns does not contain any other column.
Here, a test on a set of users corresponds to those users attempting a transmission. The results of the test are the number of users that attempted to transmit, 0 , 1 , {\displaystyle 0,1,} and 2 + {\displaystyle 2^{+}} , corresponding respectively to no active users, exactly one active user (message successful) or more than one active user (message collision). Therefore, using an adaptive group testing algorithm with outcomes { 0 , 1 , 2 + } {\displaystyle \{0,1,2^{+}\}} , it can be determined which users wish to transmit in the epoch. Then, any user that has not yet made a successful transmission can now be assigned a slot to transmit, without wastefully assigning times to inactive users.
) However, this is very inefficient, since it will assign transmission slots to users that may not have a message, and it is usually assumed that only a few users will want to transmit at any given time – otherwise a multiaccess channel is not practical in the first place.
In the context of group testing, this problem is usually tackled by dividing time into 'epochs' in the following way. A user is called 'active' if they have a message at the start of an epoch. (If a message is generated during an epoch, the user only becomes active at the start of the next one.) An epoch ends when every active user has successfully transmitted their message. The problem is then to find all the active users in a given epoch, and schedule a time for them to transmit (if they have not already done so successfully).
There is an open question as to when individual testing is minmax. Hu, Hwang and Wang showed in 1981 that individual testing is minmax when n ≤ ⌊ ( 5 d + 1 ) / 2 ⌋ {\displaystyle n\leq \lfloor (5d+1)/2\rfloor } , and that it is not minmax when n > 3 d {\displaystyle n>3d} . It is currently conjectured that this bound is sharp: that is, individual testing is minmax if and only if n ≤ 3 d {\displaystyle n\leq 3d} . Some progress was made in 2000 by Ricccio and Colbourn, who showed that for large n {\displaystyle n} , individual testing is minmax when d ≥ n / log 3 / 2  ( 3 ) ≈ 0.369 n {\displaystyle d\geq n/\log _{3/2}(3)\approx 0.369n} .
A noisy algorithm will always have a non-zero probability of making an error (that is, mislabeling an item).
Group testing can be extended by considering scenarios in which there are more than two possible outcomes of a test. For example, a test may have the outcomes 0 , 1 {\displaystyle 0,1} and 2 + {\displaystyle 2^{+}} , corresponding to there being no defectives, a single defective, or an unknown number of defectives larger than one. More generally, it is possible to consider the outcome-set of a test to be 0 , 1 , ... , k + {\displaystyle {0,1,\ldots ,k^{+}}} for some k ∈ N {\displaystyle k\in \mathbb {N} } .
In the noisy case, one relaxes the requirement in the original COMP algorithm that the set of locations of ones in any column of M {\displaystyle M} corresponding to a positive item be entirely contained in the set of locations of ones in the result vector. Instead, one allows for a certain number of “mismatches” – this number of mismatches depends on both the number of ones in each column, and also the noise parameter, q {\displaystyle q} . This noisy COMP algorithm requires no more than 4.36 ( δ + 1 + δ ) 2 ( 1 − 2 q ) − 2 d log 2  n {\displaystyle 4.36({\sqrt {\delta }}+{\sqrt {1+\delta }})^{2}(1-2q)^{-2}d\log _{2}{n}} tests to achieve an error probability at most n − δ {\displaystyle n^{-\delta }} .
The generality of the theory of group testing lends it to many diverse applications, including clone screening, locating electrical shorts; high speed computer networks; medical examination, quantity searching, statistics; machine learning, DNA sequencing; cryptography; and data forensics. This section provides a brief overview of a small selection of these applications.
The other classification, adaptivity, concerns what information can be used when choosing which items to group into a test. In general, the choice of which items to test can depend on the results of previous tests, as in the above lightbulb problem. An algorithm that proceeds by performing a test, and then using the result (and all past results) to decide which next test to perform, is called adaptive. Conversely, in non-adaptive algorithms, all tests are decided in advance. This idea can be generalised to multistage algorithms, where tests are divided into stages, and every test in the next stage must be decided in advance, with only the knowledge of the results of tests in previous stages.