Group Testing with Prior Statistics

Authors:
  • TLTongxin Li
    Tongxin Li
  • CCChun Lam Chan
    Chun Lam Chan
  • WHWenhao Huang
    Wenhao Huang
  • TKTarik Kaced
    Tarik Kaced
  • SJSidharth Jaggi
    Sidharth Jaggi
Preprint
Publisher website
Google Scholar
Abstract
We consider a new model where each item is a binary random variable defined by an a priori probability of being defective. We assume each that probability is small and that items are independent, but not necessarily identically distributed. The goal of group testing algorithms is to identify with high probability the subset of defectives via non-linear (disjunctive) binary measurements. Our main contributions are two algorithms: one with adaptive measurements based on Shannon-Fano/Huffman source codes, and one using non-adaptive measurements. Under loose assumptions on prior statistics, our algorithms only need a number of measurements that is close to the information-theoretic entropy lower bound, up to an explicit universal constant factor. We also provide simulations to support our results.