Fundamental Limits of Non-Adaptive Group Testing With Markovian Correlation

Aditya Narayan Ravi, Ilan Shomorony · 2025

Read Fundamental Limits of Non-Adaptive Group Testing With Markovian Correlation by Aditya Narayan Ravi, Ilan Shomorony (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-12588.txt.

Introduction

Aditya Narayan Ravi and Ilan Shomorony worked out in 2025 how few pooled tests can find infections that arrive in bursts. Group testing mixes samples to save tests, but classic designs assume each item's state is independent. Here infections follow a Markov chain, so positives cluster together. In the very sparse regime, the authors give a fixed test design with an efficient decoder.

Their scheme's error fades to zero while using a test count within a factor of about 1.44 of the information-theoretic floor. That matches the quality known for the independent case. Longer expected bursts mean fewer tests, which prices the value of exploiting correlation. The authors frame the bound as the fundamental limit for this setting. The results guide screening designs where cases cluster, from disease outbreaks to fault hunts.

Catalog record

CREATORAditya Narayan Ravi, Ilan Shomorony
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE42 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-12588

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Fundamental Limits of Non-Adaptive Group Testing With Markovian Correlation Aditya Narayan Ravi, Ilan Shomorony Abstract THIS PAPER IS ELIGIBLE FOR THE STUDENT PAPER AWARD. 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 ) ≈ 1.44 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. I Introduction Consider a correlated group testing problem where the infection status of an item is correlated with the infection status of the item before it. We are interested in non-adaptive group testing strategies [ 1 ] to detect the infected items. Classical group testing, introduced by Dorfman [ 2 ] , often employs the combinatorial model, a widely used framework. In this model, a population of size n contains exactly k infected individuals, chosen uniformly at random from all possible subsets of size k . An alternative approach is the probabilistic i.i.d. model, which assumes that each individual is independently infected with probability q_{n} . Importantly, these two models are largely equivalent [ 3 ] . This framework has been extensively explored in the literature [ 4 , 5 , 6 , 7 , 3 ] . In this setting, when infections are sparse, group testing can dramatically reduce the number of tests required. However, this assumption of independence is rarely reflective of real-world infection dynamics. Recent studies have begun to acknowledge this limitation and have explored the potential of leveraging known community structures [ 8 , 9 , 10 , 11 , 12 , 13 ] to enhance group testing efficiency. Moreover, in many practical scenarios, infections are not uniformly distributed but tend to occur in bursts [ 14 ] . For example, people living in the same living space or neighborhood are more likely to get infected and tested together. Such bursty infection patterns are naturally captured by correlated infection models. Another important motivation for our work arises from imaging-based spatial transcriptomics technologies such as MERFISH [ 15 ] and Xenium [ 16 ] . These technologies use barcoded “probes” to simultaneously test the expression of a group of genes. If any of the genes tested are being expressed in a certain location on a tissue, that location lights up when an image is captured under a fluorescence microscope. The design of these probes can be cast as a group testing problem, where we can target multiple genes during each testing/imaging round. Furthermore, the genes that are tested often exhibit strong local dependencies, where genes involved in the same regulatory pathways or located near each other on a chromosome tend to activate together [ 17 ] , once again resulting in bursty patterns. This “co-regulation” has been exploited previously [ 18 ] , with correlated genes being measured together to reduce the number of tests required. Understanding correlated group testing can thus provide insights into how an optimal design of these probes could take advantage of gene co-regulation, reducing the number of testing rounds. Note that once the probes are designed and introduced in spatial transcriptomics experiments, modifying or adapting the experimental setup is infeasible. This further motivates the need for non-adaptive group testing strategies for this setting. Delving into the problem more formally, consider a set of n distinct items labeled \{1,2,\dots,n\} . Each item i is assigned a binary random variable U_{i}\in\{0,1\} , where U_{i}=1 indicates that item i is infected, and U_{i}=0 otherwise. The collective infection status of all items is represented by the infection vector U^{n}=(U_{1},U_{2},\dots,U_{n}) . The objective is to estimate U^{n} using the outcomes of T non-adaptive group tests. Each test simultaneously tests a subset of items. A test returns a positive result if at least one infected item is included in the group; otherwise, the result is negative. To build intuition, consider the classical independent group testing problem, where each item in a population of size n is independently infected with probability q_{n} . This problem is categorized into three regimes [ 3 ] based on the expected number of infected items nq_{n} . In the very sparse regime [ 3 , 6 ] , the expected number scales slower than any polynomial in n (e.g., nq_{n}\sim O(\log n) or O(1) ). In the sparse regime [ 7 , 5 ] , it grows sub-linearly, but faster than logarithmic rates (e.g., nq_{n}\sim O(n^{\theta}),\theta<1 ). In the dense regime , the number of infected items scales linearly with n , i.e., q_{n}\in(0,1) is a constant. Group testing is known to provide significant gains in the very sparse and sparse regimes, where the number of infections are relatively low [ 3 ] . Consider a very sparse regime, where U_{i} ’s are independent and distributed as \text{Bernoulli}(q_{n}) , where q_{n}=k\log(n)/n for some constant k>0 . Now, consider testing strategies that employ per-item decoding (which is sometimes referred to as separate decoding of items [ 3 ] ). In this approach, the infection status of each item is determined solely based on the information of which tests contain that item and the test outcomes. In contrast, joint decoding [ 3 , 5 , 4 ] considers the infection status of all items simultaneously, leveraging the entire set of items tested in each test to jointly decode the infection status of the items. It can be shown that a per-item testing and decoding scheme [ 19 , 6 ] can achieve a vanishing probability of error as n\to\infty if the number of tests T(n) satisfies \displaystyle T(n)>\frac{nq_{n}\log{n}}{\ln{2}}. (1) To achieve this bound, the testing matrix (which specifies which items are included in each test) can be designed in a random fashion, by including each item in each test independently, with a probability p=\nu/nq_{n} [ 6 ] , where \nu is a constant. Moreover \nu is optimized and set to \nu=\ln(2) to obtain the bound. This is followed by Maximum Likelihood (ML) decoding, where each item is decoded independently based on the ML rule. Surprisingly, this simple scheme is optimal (under per-item decoding) in the independent case [ 6 ] . In contrast, the correlated group testing problem presents a significantly greater challenge compared to the independent case. Independent testing strategies become suboptimal in this setting because they ignore the information the infection status of an item provides about other correlated items. As a result, applying independent testing in correlated settings fails to reduce the number of tests. Prior work [ 8 , 11 , 9 , 10 ] has introduced well-designed adaptive strategies that effectively exploit these correlations to reduce the number of required tests. However, developing non-adaptive strategies that achieve similar improvements remains difficult. For example, [ 10 ] proposes a non-adaptive method that reduces the number of tests but only when a false positive error is

Read the complete text