グループテスト
The concept of group testing was first introduced by Robert Dorfman in 1943 in a short report published in the Notes section of Annals of Mathematical Statistics. Dorfman's report – as with all the early work on group testing – focused on the probabilistic problem, and aimed to use the novel idea of group testing to reduce the expected number of tests needed to weed out all syphilitic men in a given pool of soldiers. The method was simple: put the soldiers into groups of a given size, and use individual testing (testing items in groups of size one) on the positive groups to find which were infected.
Here a {\displaystyle {\textbf {a}}} is ' d {\displaystyle d} sparse', which means that at most d ≪ N {\displaystyle d\ll N} of its entries are 1 {\displaystyle 1} . The aim is to construct an approximation to f {\displaystyle f} using t {\displaystyle t} point evaluations, where t {\displaystyle t} is as small as possible. (Exactly recovering f {\displaystyle f} corresponds to zero-error algorithms, whereas f {\displaystyle f} is approximated by algorithms that have a non-zero probability of error.)
In this problem, recovering f {\displaystyle f} is equivalent to finding a {\displaystyle {\textbf {a}}} .
However, in the more likely case that only a very small proportion of the men are infected, a much more efficient testing scheme can be achieved. The feasibility of a more effective testing scheme hinges on the following property: the soldiers can be pooled into groups, and in each group the blood samples can be combined together. The combined sample can then be tested to check if at least one soldier in the group has syphilis. This is the central idea behind group testing. If one or more of the soldiers in this group has syphilis, then a test is wasted (more tests need to be performed to find which soldier(s) it was).
There are many ways to extend the problem of group testing. One of the most important is called noisy group testing, and deals with a big assumption of the original problem: that testing is error-free. A group-testing problem is called noisy when there is some chance that the result of a group test is erroneous (e.g. comes out positive when the test contained no defectives). The Bernoulli noise model assumes this probability is some constant, q {\displaystyle q} , but in general it can depend on the true number of defectives in the test and the number of items tested. For example, the effect of dilution can be modelled by saying a positive result is more likely when there are more defectives (or more defectives as a fraction of the number tested), present in the test.