|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'503'724
Articles rated: 2609
23 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Group Testing with Random Pools: optimal two-stage algorithms | | Marc Mezard
; Cristina Toninelli
; | | Date: |
21 Jun 2007 | | Abstract: | We study Probabilistic Group Testing of a set of N items each of which is
defective with probability p. We focus on the double limit of small defect
probability, p<<1, and large number of variables, N>>1, taking either p->0
after $N oinfty$ or $p=1/N^{eta}$ with $etain(0,1/2)$. In both settings
the optimal number of tests which are required to identify with certainty the
defectives via a two-stage procedure, $ar T(N,p)$, is known to scale as
$Np|log p|$. Here we determine the sharp asymptotic value of $ar
T(N,p)/(Np|log p|)$ and construct a class of two-stage algorithms over which
this optimal value is attained. This is done by choosing a proper bipartite
regular graph (of tests and variable nodes) for the first stage of the
detection. Furthermore we prove that this optimal value is also attained on
average over a random bipartite graph where all variables have the same degree,
while the tests have Poisson-distributed degrees. Finally, we improve the
existing upper and lower bound for the optimal number of tests in the case
$p=1/N^{eta}$ with $etain[1/2,1)$. | | Source: | arXiv, arxiv.0706.3104 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER