Abstract
We study Dorfman's classical group testing protocol in a novel setting where individual specimen statuses are modeled as exchangeable random variables. This approach is motivated by infectious disease screening, where specimens arriving together often originate from the same community and exhibit positive correlation. We relax the typical assumption of independent and identically distributed (IID) statuses, instead modeling them as exchangeable random variables—meaning their joint distribution is invariant under permutations. We characterize these distributions using a function $q(h)$, representing the marginal probability that a group of size $h$ tests negative. This representation allows us to reduce the set partitioning problem in Dorfman's protocol to an efficiently solvable integer partitioning problem. Applying these tools to an empirical COVID-19 dataset, we explain the unexpectedly high efficiency reported in practice and suggest further optimizations.
Introduction: Beyond the IID Assumption
Group testing—pooling multiple samples into a single test to conserve resources—is a cornerstone of public health diagnostics. The most prominent method is the Dorfman procedure: a pool is tested; if negative, all individuals are cleared; if positive, every individual in the pool is re-tested separately.
Historically, mathematical analysis of this protocol has relied on the assumption that specimen statuses are Independent and Identically Distributed (IID). However, real-world samples are rarely independent. Individuals arriving at a testing site often share households, workplaces, or social circles. If one person is positive, their neighbors in the testing queue are statistically more likely to be positive as well. Standard IID models fail to capture this "clumping" effect, leading to sub-optimal group sizes and a failure to predict the high efficiency observed in field applications.
Methodology: The Power of Symmetry
The authors bridge the gap between oversimplified IID models and computationally intractable general models by introducing two key innovations:
- Modeling Exchangeability (Symmetry): By assuming specimen statuses are exchangeable, the model recognizes that the probability of a specific set of outcomes depends only on the number of positives, not their specific identities. This captures natural correlations without requiring a complete map of social networks.
- The $q(h)$ Representation: The authors prove that any symmetric distribution can be characterized by a function $q(h)$, the probability that a group of size $h$ tests negative. This interpretable representation simplifies the underlying probability space.
- Optimization via Integer Partitioning: Finding the optimal grouping for $n$ people is typically a "set partitioning" problem, which is computationally prohibitive for large $n$. The authors demonstrate that for symmetric distributions, this reduces to an integer partitioning problem. They provide a Dynamic Programming (DP) algorithm with $O(n^2)$ complexity, enabling the rapid calculation of optimal group sizes for large populations.
Empirical Validation: COVID-19 Case Study
The theory was validated using a large-scale dataset from the Hebrew University-Hadassah COVID-19 Diagnosis Team, comprising 133,816 specimens across 17,945 pools. This dataset was notable for showing efficiency levels that standard Dorfman theory could not explain.
Key Insights
- Correlation as an Advantage: Positive correlation actually improves group testing efficiency. When positive cases clump together, they leave more pools entirely negative, saving more tests than if positives were distributed randomly.
- Explaining the "Unexpected": At a prevalence of 1.695%, the IID model predicted a theoretical efficiency of 3.96. The actual empirical efficiency was 4.59. The authors' symmetric model predicted 4.38, providing a much more accurate reflection of reality.
- Optimizing Practice: While the original medical team used pools of size 8, the authors' optimization tool suggested that pools of size 10 would have achieved an even higher empirical efficiency of 4.75.
Discussion and Future Work
While this framework significantly advances group testing theory, it currently assumes a "noiseless" environment where tests have perfect sensitivity and specificity. Future research could extend this to "noisy" testing models that account for dilution effects or false results. Additionally, the authors suggest using machine learning—specifically permutation-invariant neural networks—to estimate the $q(h)$ function directly from patient features like age, symptoms, or geographic location to further refine testing strategies.
Summary updated