Fundamental Limits of Non-Adaptive Group Testing with Markovian Correlation

Aditya Narayan Ravi, Ilan Shomorony

Abstract

We study a correlated group testing model where items are infected according to a Markov chain, which creates bursty infection patterns. Focusing on a very sparse infections regime, we propose a non-adaptive testing strategy with an efficient decoding scheme that is nearly optimal. Specifically, it achieves asymptotically vanishing error with a number of tests that is within a $1/\ln(2) \approx 1.44$ multiplicative factor of the fundamental entropy bound—a result that parallels the independent group testing setting. We show that the number of tests reduces with an increase in the expected burst length of infected items, quantifying the advantage of exploiting correlation in test design.

Introduction

Group testing is a classic problem in information theory aimed at identifying a small subset of "infected" items within a large population by pooling samples into groups. A negative test result indicates all items in the pool are healthy, while a positive result indicates at least one infected item. While most research assumes independent infection statuses, real-world scenarios—such as viral transmission in households or spatial transcriptomics in genetics—exhibit strong correlations.

In high-throughput laboratory settings, non-adaptive testing (where all tests are designed upfront) is preferred over adaptive testing due to physical constraints. This paper addresses the challenge of designing efficient non-adaptive strategies that exploit "bursty" infection patterns to minimize the total number of tests.

Infection Model

The authors model the infection status of $n$ items as a two-state Markov chain. This model captures the tendency of infections to occur in contiguous "bursts."

A two-state Markov chain modeling the infection status of items, where 1 represents infected and 0 represents healthy.

In this model, the parameter $\beta$ represents the probability of transitioning from an infected state (1) to a healthy state (0). The expected length of an infection burst is given by $1/\beta$. When $\beta$ is small, infections appear in longer, more predictable sequences.

Proposed Testing Strategy

To exploit these correlations, the paper introduces a Two-Stage Randomized Block Testing framework. Instead of sampling individual items uniformly at random, the population is partitioned into contiguous blocks.

The two-stage randomized block testing strategy, showing how population blocks are sampled to exploit bursty infection patterns.
  1. Test Design: Blocks are randomly selected for inclusion in a test. Within these selected blocks, items are then randomly sampled. This hierarchical structure aligns the testing matrix with the expected burst size of the infections.
  2. Decoding: A computationally efficient "per-item" decoder is used. It first screens out items present in any negative test and then applies a threshold to the remaining items based on their frequency in positive tests.

Key Results and Insights

The theoretical analysis focuses on the "very sparse" regime, where the number of infections $k$ scales logarithmically with the population size $n$.

  • Correlation Advantage: A primary finding is that correlation simplifies the testing problem. The required number of tests $T$ is directly proportional to $\beta$. Since $\beta < 1$ in bursty scenarios, fewer tests are needed compared to the independent case.
  • The 1.44 Optimality Gap: The proposed strategy achieves a testing rate within a factor of $1/\ln(2) \approx 1.44$ of the fundamental information-theoretic limit. This mirrors the performance gap seen in independent group testing, suggesting that the block-based approach effectively handles Markovian noise.
  • Fundamental Bounds: The authors establish a converse bound showing that any strategy requires at least $T \ge \beta n q_n \log n$ tests, while their achievable scheme succeeds with $T \approx 1.44 \beta n q_n \log n$ tests.

Conclusion

This work demonstrates that exploiting Markovian correlation can significantly reduce the overhead of group testing. The proposed non-adaptive strategy is both efficient and near-optimal. Future research directions include extending these results to denser sparsity regimes (e.g., $k \approx n^\theta$) and investigating more complex correlation structures, such as higher-order Markov chains or graph-based dependencies.

Summary updated

Abstract

We study a correlated group testing model where items are infected according to a Markov chain, which creates bursty binfection patterns. Focusing on a very sparse infections regime, we propose a non adaptive testing strategy with an efficient decoding scheme that is nearly optimal. Specifically, it achieves asymptotically vanishing error with a number of tests that is within a $1/\ln(2) \approx 1.44$ multiplicative factor of the fundamental entropy bound a result that parallels the independent group testing setting. We show that the number of tests reduces with an increase in the expected burst length of infected items, quantifying the advantage of exploiting correlation in test design.
BibTeX
@inproceedings{ravi2026fundamental,
  author = {Aditya Narayan Ravi and Ilan Shomorony},
  title = {{Fundamental Limits of Non-Adaptive Group Testing with Markovian Correlation}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2026},
  url = {https://openreview.net/forum?id=NphUpyXrv3},
}
Figure