The Optimality of a Nested Generalized Pairwise Group Testing Procedure
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913900883083264 |
|---|---|
| author | Malinovsky, Yaakov Skorniakov, Viktor |
| author_facet | Malinovsky, Yaakov Skorniakov, Viktor |
| contents | We study the problem of identifying defective units in a finite population of \( n \) units, where each unit \( i \) is independently defective with known probability \( p_i \). This setting is referred to as the \emph{Generalized Group Testing Problem}. A testing procedure is called optimal if it minimizes the expected number of tests. It has been conjectured that, when all probabilities \( p_i \) lie within the interval \( \left[1 - \frac{1}{\sqrt{2}},\, \frac{3 - \sqrt{5}}{2} \right] \), the \emph{generalized pairwise testing {algorithm}}, applied to the \( p_i \) arranged in nondecreasing order, constitutes the optimal nested testing strategy among all such order-preserving nested strategies. In this work, we confirm this conjecture and establish the optimality of the procedure within the specified regime. Additionally, we provide a complete structural characterization of the procedure and derive a closed-form expression for its expected number of tests. These results offer new insights into the theory of optimal nested strategies in generalized group testing. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_15797 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Optimality of a Nested Generalized Pairwise Group Testing Procedure Malinovsky, Yaakov Skorniakov, Viktor Statistics Theory Information Theory Probability 68P30, 68Q25, 90C27, 94A15, 05C85 We study the problem of identifying defective units in a finite population of \( n \) units, where each unit \( i \) is independently defective with known probability \( p_i \). This setting is referred to as the \emph{Generalized Group Testing Problem}. A testing procedure is called optimal if it minimizes the expected number of tests. It has been conjectured that, when all probabilities \( p_i \) lie within the interval \( \left[1 - \frac{1}{\sqrt{2}},\, \frac{3 - \sqrt{5}}{2} \right] \), the \emph{generalized pairwise testing {algorithm}}, applied to the \( p_i \) arranged in nondecreasing order, constitutes the optimal nested testing strategy among all such order-preserving nested strategies. In this work, we confirm this conjecture and establish the optimality of the procedure within the specified regime. Additionally, we provide a complete structural characterization of the procedure and derive a closed-form expression for its expected number of tests. These results offer new insights into the theory of optimal nested strategies in generalized group testing. |
| title | The Optimality of a Nested Generalized Pairwise Group Testing Procedure |
| topic | Statistics Theory Information Theory Probability 68P30, 68Q25, 90C27, 94A15, 05C85 |
| url | https://arxiv.org/abs/2506.15797 |