Group testing

In statistics and combinatorial mathematics, group testing refers to any procedure which breaks up the task of locating elements of a set which have certain properties into tests on groups of items, rather than on individual elements. First studied by Robert Dorfman in 1943, group testing is a relatively new field of applied mathematics that is an active area of research today, and has a large amount of utility in a wide range of practical applications.

A familiar example of group testing involves a string of lightbulbs connected series, where we know exactly one of the bulbs is broken. The objective is to find the broken bulb using the smallest number of tests (a test is when we connect some of the bulbs to a power supply). A simple approach is to test each bulb individually. However, when there are a large number of bulbs we can be much more efficient if we pool the bulbs into groups. For example, if we connect the first half of the bulbs at once, we can determine which half the broken bulb is in, ruling out half of the bulbs in just one test.

Schemes for carrying out such group testing can be simple or complex and the tests involved at each stage may be different. Schemes in which the tests for the next stage depend on the results of the previous stages are called adaptive procedures, while schemes designed so that all the tests are known beforehand are called non-adaptive procedures. The structure of the scheme of the tests involved in a non-adaptive procedure is known as a pooling design.

Group testing has applications in statistics, biology, computer science medicine and engineering. Modern interest in these testing schemes has been rekindled by the Human Genome Project.

Unlike many areas of Mathematics, the origins of group testing can be traced back to a single report written by a single person: Robert Dorfman. The motivation arose during the Second World War when the United States Public Health Service and the Selective service embarked upon a large scale project to weed out all syphilitic men called up for induction. Testing an individual for syphilis involves drawing a blood sample from them and then analysing the sample to determine the presence or absence of syphilis. However, at the time, performing this test was expensive, and testing every soldier individually would have been very cost heavy and inefficient.

...
Wikipedia