In the group testing problem we aim to identify a small number of infected individuals within a large population. We avail ourselves to a procedure that can test a group of multiple individuals, with the test result coming out positive iff at least one individual in the group is infected. With all tests conducted in parallel, what is the least number of tests required to identify the status of all individuals? In a recent test design [ 2016] the individuals are assigned to test groups randomly, with every individual joining an equal number of groups. We pinpoint the sharp threshold for the number of tests required in this randomised design so that it is information-theoretically possible to infer the infection status of every individual. Moreover, we analyse two efficient inference algorithms. These results settle conjectures from [ 2014, 2019].
Dorfman's original group testing scheme, intended to test the American army for syphilis, was adaptive . In a first round of tests each soldier would be allocated to precisely one test group. If the test result came out negative, none of the soldiers in the group were infected. In a second round the soldiers whose group was tested positively would then be tested individually. Of course, Dorfman's scheme was not information-theoretically optimal. An optimal adaptive scheme that involves several test stages, with the tests conducted in the present stage governed by the results from the previous stages, is known @cite_38 . In the adaptive scenario the information-theoretic threshold works out to be The lower bound, i.e., that no adaptive design gets by with @math tests, follows from a very simple information-theoretic consideration. Namely, with a total of @math tests at our disposal there are merely @math possible test outcomes, and we need this number to exceed the count @math of possible vectors @math .
@cite_38
2226661047
In the (d,n) group testing problem n items have to be identified as either good or defective and the number of defective items is known to be d. A test on an arbitrary group (subset) of items reveals either that all items in the group are good or that at least one of the items is defective, but not how many or which items are defective. We present a new algorithm which in the worst case needs less than @math tests more than the information lower bound @math for n d≥2. For n d≥38, the difference decreases to less than @math tests. For d≥10, this is a considerable improvement over the d−1 additional tests given for the best previously known algorithm by Hwang. We conjecture that the behaviour for large n and d of the difference is optimal for @math . This implies that the @math tests per defective given in the bound above are the best possible.