Exploiting Statistical Correlations in Group Testing

60 concepts25 papers1 proposal

Group testing is a classic combinatorial problem: given a large population of items containing a small number of "defectives" (such as infected individuals in a pandemic or faulty nodes in a network), how can we identify all defectives using as few pooled tests as possible?

For decades, the standard theoretical benchmark relied on a simplifying assumption: that the status of each item is independent and identically distributed (i.e.d.). However, as Tongxin Li et al. note in Group Testing with Prior Statistics, this "one-size-fits-all" independence assumption fails to capture real-world clustering, such as localized disease outbreaks within households. When we ignore these correlations, our mathematical models yield highly pessimistic estimates of testing efficiency, failing to explain why pooled testing often performs much better in practice than theory predicts (Nicholas C. Landolfi et al. in Optimal Dorfman Group Testing for Symmetric Distributions).

A rapidly growing body of research addresses this gap by abandoning the independence assumption. By modeling statistical correlations—whether derived from social networks, spatial proximity, or temporal bursts—researchers are designing algorithms that drastically reduce the number of tests required to identify defectives.

The Intuition: Collapsing the Search Space

Why does correlation make group testing more efficient? The answer lies in how correlation restricts the combinatorial search space.

If individual infection statuses are independent, every item carries an isolated piece of uncertainty. But in the real world, pathogens spread through contact networks, creating highly correlated clusters. As Hesam Nikpey et al. demonstrate in Group Testing With Correlation Under Edge-Faulty Graphs, exploiting these correlations allows a single test to provide information about multiple items simultaneously, rather than treating each as an independent unit.

Consider a population where infections occur in "bursts" or follow a Markov chain, a scenario analyzed by Aditya Narayan Ravi et al. in Fundamental Limits of Non-Adaptive Group Testing with Markovian Correlation. Because the infections are locally concentrated, the total entropy of the system is lower than it would be under a uniform distribution. Similarly, Ivan Lau et al. show in Model-Based and Graph-Based Priors for Group Testing that when items are known to cluster in groups of size $q$, the information-theoretic limit for the number of tests can be reduced by a factor proportional to the cluster size. By restricting the set of possible defective combinations to those that align with known structural dependencies, the decoder requires far fewer physical tests to resolve the population's state.

Independent Framework (High Entropy):
[ ] [ ] [+] [ ] [ ] [+] [ ] [ ] [+] [ ]  -> Defectives scattered randomly;
                                            pools must probe blindly.

Correlated Framework (Low Entropy):
[ ] [ ] [ ]  [+] [+] [+]  [ ] [ ] [ ]    -> Defectives cluster in blocks;
                                            one negative test clears a whole block.

Hierarchical and Community-Aware Pooling

To translate this information-theoretic advantage into practical testing protocols, algorithms must align their pooling strategies with the underlying population structure.

In Adaptive Group Testing on Networks with Community Structure, Ayfer Ozgur et al. introduce a "Stochastic Block Infection Model" and propose a strategy called hierarchical unit abstraction. Instead of testing individuals randomly, the algorithm treats entire communities (e.g., households or classrooms) as single entities during the initial screening phase. Because infections are highly correlated within these communities, a single negative test on a pooled community sample can rule out dozens of individuals at once. Only communities that return a positive result are subjected to fine-grained individual testing.

This shifts the fundamental complexity of the problem: the number of required tests scales with the number of infected clusters rather than the number of infected individuals (Pavlos Nikolopoulos et al. in Group testing for connected communities). The authors demonstrate in Community-Aware Group Testing that this community-aware approach reduces test requirements by 55% to 75% compared to community-agnostic methods. They achieve this using a composite matrix structure where one sub-matrix identifies infected groups while a second block-structured matrix pinpoints individuals within those groups, enabling efficient parallelized testing.

Other structural properties offer similar leverage. For example, Thach V. Bui et al. exploit the fact that positive and inhibitor items often appear in contiguous blocks in Group Testing with Blocks of Positives and Inhibitors, designing specialized encoding and decoding schemes that drastically accelerate processing times.

Integrating Network Side Information

Rather than inferring clusters blindly, modern group testing frameworks directly integrate auxiliary data—such as contact tracing graphs or digital proximity logs—as mathematical priors.

Arlei Lopes da Silva et al. formalize this in Group Testing on a Network as a graph partitioning task. By using transmission network data to guide pool formation, they concentrate infected individuals into the same pools. This maximizes the utility of each test: a positive pool is highly likely to contain multiple infected members, reducing the "waste" of testing healthy individuals in mixed pools.

Network-Informed Pooling:
  (Infected Node) --- (Close Contact)      ==> Place in the SAME pool

  (Healthy Node)  --- (Healthy Node)       ==> Place in separate/clear pools

When these network relationships are known, they can be injected directly into message-passing decoders. Ritesh Goenka et al. show in Contact Tracing Enhances the Efficiency of Covid-19 Group Testing that individual infection probabilities derived from contact history function beautifully as Bayesian priors. This concept is fully realized by Shu-Jie Cao et al. in Group Testing with Side Information via Generalized Approximate Message Passing, where a Generalized Approximate Message Passing (GAMP) algorithm weights individuals based on their exposure history. Because the algorithm requires less evidence from pooled samples to confirm a case when a high-risk interaction is known beforehand, it resolves health statuses with far fewer physical tests. Furthermore, Stratis Tsirtsis et al. extend this to overdispersed transmission environments in Pooled testing of traced contacts under superspreading dynamics, using dynamic programming to optimize pool sizes specifically for contact networks shaped by superspreading events.

Broadening the Framework: Alternative Distributions and Objectives

Embracing dependency also demands new probabilistic foundations and optimization objectives.

For instance, the rate of defectives in real-world streams is rarely static. To address this, Amin Emad introduces Poisson Group Testing: A Probabilistic Model for Boolean Compressed Sensing, modeling the number of defective items via a Poisson distribution. This framework accommodates scenarios like streaming data or evolving epidemics where the underlying rate of defectives fluctuates over time.

When resources are severely constrained, the goal often shifts from flawless individual identification to broader public health utility. Balram Rai et al. highlight this operational reality in Pool Testing for COVID-19: Suitable Splitting Procedure and Pool Size for India, demonstrating how mathematically optimizing pool splitting based on localized prevalence preserves diagnostic accuracy in resource-limited settings.

Taking a macro-level view, Georg Pichler et al. apply information-theoretic rate-distortion theory in Modelling the Utility of Group Testing for Public Health Surveillance to minimize the societal and economic costs of testing errors rather than aiming for perfect reconstruction. This utility-driven perspective is echoed by Edwin Lock et al. in Welfare-Maximizing Pooled Testing, where they show that simple, non-overlapping test designs achieve near-optimal social welfare when pool compositions are tailored to correlated risks in shared workplaces or housing. Finally, to navigate these complex, multi-objective trade-offs, Xueqiao Peng et al. leverage machine learning in Using Reinforcement Learning for Multi-Objective Cluster-Level Optimization of Non-Pharmaceutical Interventions for Infectious Disease. By pairing reinforcement learning with a supervised learning decoder, their approach explicitly accounts for the collective history of disease clusters, outperforming traditional, static public health guidelines.

Key Foundational Work

Group testing with prior statistics (2014) — contributed 2 concept elements to this direction.
Poisson Group Testing: A Probabilistic Model for Boolean Compressed Sensing (2015) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 24 papers
  2. Version 1 · 2026-10-04 · 27 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_independent_infection_assumption_4ebaef32,
  title = {independent infection assumption},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/independent-infection-assumption/rdr_4ebaef32fc404b5b975984c84200e83f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 2, frozen text):

@misc{lacuna_independent_infection_assumption_4ebaef32_v2,
  title = {independent infection assumption},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/independent-infection-assumption/rdr_4ebaef32fc404b5b975984c84200e83f/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake