A New Upper Bound for Finding Defective Samples in Group Testing

Jin-Taek SEONG  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E103-D   No.5   pp.1164-1167
Publication Date: 2020/05/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2019EDL8187
Type of Manuscript: LETTER
Category: Fundamentals of Information Systems
Keyword: 
defective samples,  group testing,  probability of error,  upper bound,  

Full Text: PDF(109.5KB)>>
Buy this Article




Summary: 
The aim of this paper is to show an upper bound for finding defective samples in a group testing framework. To this end, we exploit minimization of Hamming weights in coding theory and define probability of error for our decoding scheme. We derive a new upper bound on the probability of error. We show that both upper and lower bounds coincide with each other at an optimal density ratio of a group matrix. We conclude that as defective rate increases, a group matrix should be sparser to find defective samples with only a small number of tests.