Fundamental Limits of Non-Adaptive Group Testing with Markovian Correlation
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912202130194432 |
|---|---|
| author | Ravi, Aditya Narayan Shomorony, Ilan |
| author_facet | Ravi, Aditya Narayan Shomorony, Ilan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_12588 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fundamental Limits of Non-Adaptive Group Testing with Markovian Correlation Ravi, Aditya Narayan Shomorony, Ilan Information Theory 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. |
| title | Fundamental Limits of Non-Adaptive Group Testing with Markovian Correlation |
| topic | Information Theory |
| url | https://arxiv.org/abs/2501.12588 |