Hostname: page-component-6898cfcb55-kwdml Total loading time: 0 Render date: 2026-11-11T18:50:38.397Z Has data issue: false hasContentIssue false
  • English
  • Français

ASYMPTOTIC ANALYSIS OF OPTIMAL NESTED GROUP-TESTING PROCEDURES

Published online by Cambridge University Press:  29 June 2016

Nabil Zaman and
Nicholas Pippenger
Nabil Zaman
Affiliation:
Harvey Mudd College, 301 Platt Blvd., Claremont, CA 91711, USA E-mail: nzaman@g.hmc.edu; njp@math.hmc.edu.
Nicholas Pippenger
Affiliation:
Harvey Mudd College, 301 Platt Blvd., Claremont, CA 91711, USA E-mail: nzaman@g.hmc.edu; njp@math.hmc.edu.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We analyze a construction for optimal nested group-testing procedures, and show that, when individuals are independently positive with probability p, the expected number of tests per positive individual, F*(p), has, as p→0, the asymptotic behavior

$$F^{\ast}(p) = \log_2 {1\over p} + \log_2 \log 2 + 2 + f\left(\log_2 {1\over p} + \log_2 \log 2\right) + O(p),$$
where
$$f(z) = 4\times 2^{-2^{1-\{z\}}} - \{z\} - 1,$$
and {z}=z−⌊z⌋ is the fractional part of z. The function f(z) is a periodic function (with period 1) that exhibits small oscillations (with magnitude <0.005) about an even smaller average value (<0.0005).

Information

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 30 , Issue 4 , October 2016, pp. 547 - 552
Copyright
Copyright © Cambridge University Press 2016 

References

1. Chen, P., Hsu, L., & Sobel, M. (1987). Entropy-based optimal group testing procedures. Probability in the Engineering and Informational Sciences 1: 497–509.Google Scholar
2. Dorfman, R. (1943). The detection of defective members of a large population. Annals of Mathematical Statistics 14: 436–440.Google Scholar
3. Gallager, R.G. & Van Voorhis, D.C. (1975). Optimal source codes for geometrically distributed integer alphabets. IEEE Transactions on Information Theory 21: 228–229.Google Scholar
4. Golomb, S.W. (1966). Run-length encodings. IEEE Transactions on Information Theory 12: 399–401.Google Scholar
5. Huffman, D. (1952). A method for the construction of minimum redundancy codes. Proceding of the IRE 40: 1098–1103.Google Scholar
6. Hwang, F.K. (1976). An optimum nested procedure in binomial group testing. Biometrics 32: 939–943.Google Scholar
7. Pólya, G. & Szegö, G. (1972). Problems and theorems in analysis. Berlin: Springer-Verlag.Google Scholar
8. Shannon, C.E. (1948). A mathematical theory of communication. Bell System Technical Journal 127: 379–423, 623–656.Google Scholar
9. Sobel, M. & Groll, P.A. (1959). Group testing to eliminate efficiently all defectives in a binomial sample. Bell System Technical Journal 38: 1179–1252.CrossRefGoogle Scholar
10. Sterrett, A. (1957). On the detection of defective members of a large population. Annals of Mathematical Statistics 28: 1033–1036.CrossRefGoogle Scholar
11. Ungar, P. (1960). The cutoff point for group testing. Communications in Pure and Applied Mathematics 13: 49–54.Google Scholar
12. Wolf, J. (1985). Born again group testing: multiaccess communications. IEEE Transactions on Information Theory 31: 185–191.Google Scholar