Related Experiment Video
Updated: Oct 19, 2025
Selecting Multiple Biomarker Subsets with Similarly Effective Binary Classification Performances
Published on: October 11, 2018
A binary search scheme for determining all contaminated specimens
1Department of Mathematics, National Technical University of Athens, Zografou Campus, 157 80, Athens, Greece. papanico@math.ntua.gr.
Abstract:
Specimens are collected from N different sources. Each specimen has probability p of being contaminated (in the case of a disease, e.g., p is the prevalence rate), independently of the other specimens. Suppose we can apply group testing, namely take small portions from several specimens, mix them together, and test the mixture for contamination, so that if the test turns positive, then at least one of the samples in the mixture is contaminated. In this paper we give a detailed probabilistic analysis of a binary search scheme, we propose, for determining all contaminated specimens. More precisely, we study the number T(N) of tests required in order to find all the contaminated specimens, if this search scheme is applied. We derive recursive and, in some cases, explicit formulas for the expectation, the variance, and the characteristic function of T(N). Also, we determine the asymptotic behavior of the moments of T(N) as [Formula: see text] and from that we obtain the limiting distribution of T(N) (appropriately normalized), which turns out to be normal.
Insights
This study introduces a binary search scheme for group testing to identify contaminated specimens efficiently. The proposed method analyzes the number of tests required, providing formulas for its statistical properties and demonstrating a normal limiting distribution.
Area of Science:
- Statistics
- Applied Mathematics
- Biostatistics
Background:
- Specimen contamination is a concern in various fields, including disease surveillance.
- Traditional individual testing can be inefficient when dealing with a large number of specimens.
- Group testing offers a method to pool specimens, potentially reducing the number of tests required.
Purpose of the Study:
- To introduce and analyze a novel binary search scheme for group testing.
- To determine the probabilistic performance of this scheme in identifying contaminated specimens.
- To derive statistical properties of the number of tests needed.
Main Methods:
- Probabilistic analysis of a proposed binary search algorithm for group testing.
- Derivation of recursive and explicit formulas for the expectation, variance, and characteristic function of the number of tests.
- Asymptotic analysis of the moments of the test count.
Main Results:
- The study provides a detailed probabilistic analysis of the binary search scheme.
- Formulas for the expectation and variance of the number of tests (T(N)) were derived.
- The asymptotic behavior of T(N) moments was determined, leading to a normal limiting distribution.
Conclusions:
- The proposed binary search scheme is a statistically sound approach for identifying contaminated specimens using group testing.
- The derived formulas and asymptotic analysis offer valuable insights into the efficiency of the method.
- The finding of a normal limiting distribution aids in understanding the test requirements for large-scale applications.
