Optimal Dorfman Group Testing for Symmetric Distributions

Nicholas C. Landolfi, Sanjay Lall

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.

The evolution of group testing models from classical IID assumptions to the exchangeable framework introduced in this paper.

Methodology: The Power of Symmetry

The authors bridge the gap between oversimplified IID models and computationally intractable general models by introducing two key innovations:

  1. 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.
  2. 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.
  3. 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

Abstract

We study Dorfman's classical group testing protocol in a novel setting where individual specimen statuses are modeled as exchangeable random variables. We are motivated by infectious disease screening. In that case, specimens which arrive together for testing often originate from the same community and so their statuses may exhibit positive correlation. Dorfman's protocol screens a population of n specimens for a binary trait by partitioning it into non-overlapping groups, testing these, and only individually retesting the specimens of each positive group. The partition is chosen to minimize the expected number of tests under a probabilistic model of specimen statuses. We relax the typical assumption that these are independent and identically distributed and instead model them as exchangeable random variables. In this case, their joint distribution is symmetric in the sense that it is invariant under permutations. We give a characterization of such distributions in terms of a function q where q(h) is the marginal probability that any group of size h tests negative. We use this interpretable representation to show that the set partitioning problem arising in Dorfman's protocol can be reduced to an integer partitioning problem and efficiently solved. We apply these tools to an empirical dataset from the COVID-19 pandemic. The methodology helps explain the unexpectedly high empirical efficiency reported by the original investigators.
BibTeX
@article{landolfi2024optimal,
  author = {Nicholas C. Landolfi and Sanjay Lall},
  title = {{Optimal Dorfman Group Testing for Symmetric Distributions}},
  journal = {SIAM J. Math. Data Sci.},
  year = {2024},
  doi = {10.1137/23m1595138},
}
Figure