Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-26T04:57:51.916Z 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: [email protected]; [email protected].
Nicholas Pippenger
Affiliation:
Harvey Mudd College, 301 Platt Blvd., Claremont, CA 91711, USA E-mail: [email protected]; [email protected].
Get access Rights & Permissions [Opens in a new window]

Abstract

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).

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 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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