Fundamental Limits of Non-Adaptive Group Testing With Markovian Correlation

Aditya Narayan Ravi, Ilan Shomorony
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:2305-2313, 2026.

Abstract

We study a correlated group testing model where $n$ items are infected according to a Markov chain, which creates bursty infection patterns. In the sparse infections regime, where the expected number of infections scales as $O(n^{\theta})$ with $\theta \in (0,1)$, we propose a non-adaptive testing strategy with an efficient decoding algorithm. Our approach outperforms an optimal yet computationally inefficient independent testing and decoding scheme (one that disregards correlation), under certain parameter regimes. At a high level, we use randomized block testing, where we first sample contiguous blocks of correlated items and then subsample items within selected blocks. Decoding then proceeds in two stages: a coarse elimination step to rule out items appearing in negative tests, followed by a fine thresholding step that declares an item infected if its test participation count exceeds a predefined threshold. Notably, when $\theta \to 0$, our method achieves asymptotically vanishing error while using 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. Further, 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-ravi26a, title = { Fundamental Limits of Non-Adaptive Group Testing With Markovian Correlation }, author = {Ravi, Aditya Narayan and Shomorony, Ilan}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {2305--2313}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/ravi26a/ravi26a.pdf}, url = {https://proceedings.mlr.press/v300/ravi26a.html}, abstract = { We study a correlated group testing model where $n$ items are infected according to a Markov chain, which creates bursty infection patterns. In the sparse infections regime, where the expected number of infections scales as $O(n^{\theta})$ with $\theta \in (0,1)$, we propose a non-adaptive testing strategy with an efficient decoding algorithm. Our approach outperforms an optimal yet computationally inefficient independent testing and decoding scheme (one that disregards correlation), under certain parameter regimes. At a high level, we use randomized block testing, where we first sample contiguous blocks of correlated items and then subsample items within selected blocks. Decoding then proceeds in two stages: a coarse elimination step to rule out items appearing in negative tests, followed by a fine thresholding step that declares an item infected if its test participation count exceeds a predefined threshold. Notably, when $\theta \to 0$, our method achieves asymptotically vanishing error while using 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. Further, 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. } }
Endnote
%0 Conference Paper %T Fundamental Limits of Non-Adaptive Group Testing With Markovian Correlation %A Aditya Narayan Ravi %A Ilan Shomorony %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-ravi26a %I PMLR %P 2305--2313 %U https://proceedings.mlr.press/v300/ravi26a.html %V 300 %X We study a correlated group testing model where $n$ items are infected according to a Markov chain, which creates bursty infection patterns. In the sparse infections regime, where the expected number of infections scales as $O(n^{\theta})$ with $\theta \in (0,1)$, we propose a non-adaptive testing strategy with an efficient decoding algorithm. Our approach outperforms an optimal yet computationally inefficient independent testing and decoding scheme (one that disregards correlation), under certain parameter regimes. At a high level, we use randomized block testing, where we first sample contiguous blocks of correlated items and then subsample items within selected blocks. Decoding then proceeds in two stages: a coarse elimination step to rule out items appearing in negative tests, followed by a fine thresholding step that declares an item infected if its test participation count exceeds a predefined threshold. Notably, when $\theta \to 0$, our method achieves asymptotically vanishing error while using 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. Further, 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.
APA
Ravi, A.N. & Shomorony, I.. (2026). Fundamental Limits of Non-Adaptive Group Testing With Markovian Correlation . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:2305-2313 Available from https://proceedings.mlr.press/v300/ravi26a.html.

Related Material