Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-23T09:37:33.294Z Has data issue: false hasContentIssue false
  • English
  • Français

Entropy-based Optimal Group-testing Procedures

Published online by Cambridge University Press:  27 July 2009

Pinyuen Chen ,
Lifang Hsu  and
Miltons Sobel
Pinyuen Chen
Affiliation:
Department of MathematicsSyracuse University, Syracuse, New York 13244
Lifang Hsu
Affiliation:
Department of Mathematics SUNY at Oswego Oswego, New York 13126
Miltons Sobel
Affiliation:
Department of MathematicsUniversity of California at Santa Barbara, Santa Barbara, California 93106
Get access Rights & Permissions [Opens in a new window]

Abstract

Two procedures for the group-testing problem based on the Shannon-entropy criteria are proposed. The model considered is that the N units are realizations of N Bernoulli independent and identically distributed (i.i.d.) chance variables with common, known probability q of an arbitrary unit being good and p =1 – q of it being defective. Both the algorithms introduced have low design complexity and yet provide near-optimal result. For N ≤ 5, one of the procedures introduced is optimal for selected values of q.

Type
Articles
Information
Probability in the Engineering and Informational Sciences , Volume 1 , Issue 4 , October 1987 , pp. 497 - 509
Copyright
Copyright © Cambridge University Press 1987

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

Dorfman, R. (1943). The detection of defective members of large population. Ann. Math. Stat. 14: 436–440.CrossRefGoogle Scholar
Friedman, S. (1982). The optimal solution of the group-testing problem. Personal manuscript.Google Scholar
Hsu, L. (1983). New procedures in group-testing problems based on Huffman lower bound and Shannon-entropy criteria. Ph.D. Thesis, University of California, Santa Barbara.Google Scholar
Huffman, D.A. (1952). A method for the construction of minimum redundancy codes. Proc. I.R.E. 40: 1098–1103.Google Scholar
Sobel, M. & Groll, P.A. (1959). Group testing to eliminate efficiently all defectives in a binomial sample. Bell System Tech. J 38: 1179–1252.CrossRefGoogle Scholar
Sobel, M. (1960). Group testing to classify all defectives in binomial sample. In Machol, R. E. (ed.), A contribution in Information and Decision Processes. New York: McGraw-Hill, pp. 127–161.Google Scholar
Sobel, M. (1967). Optimal group testing. Proceedings of the Colloquium on Information Theory. Organized by the Bolyai Mathematical Society, Debrecen (Hungary), 411–488.Google Scholar
Ungar, P. (1959). Cutoff point for group testing. Comm. on Pure and Applied Math. 13: 49–54.CrossRefGoogle Scholar