PaperlayerView exact revision on arXiv

Source-linked AI summary

Group Testing with Prior Statistics

Tongxin Li, Chun Lam Chan, Wenhao Huang, Tarik Kaced, Sidharth Jaggi

arXiv:1401.3667v8cs.ITmath.IT

TL;DR

Group testing with independent but non-identically distributed items has known item-specific defect probabilities, but uniform-prior guarantees do not establish performance for this setting or ensure entropy-scale test counts. The paper develops adaptive and non-adaptive algorithms and reports expected test bounds within constant factors of the entropy lower bound, with concentration under mild assumptions.

Abstract

from arXiv · show

We consider a new group testing model wherein each item is a binary random variable defined by an a priori probability of being defective. We assume that each 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 classes of algorithms: (1) adaptive algorithms with tests based either on a maximum entropy principle, or on a Shannon-Fano/Huffman code; (2) non-adaptive algorithms. Under loose assumptions and with high probability, our algorithms only need a number of measurements that is close to the information-theoretic lower bound, up to an explicitly-calculated universal constant factor. We provide simulations to support our results.

I. INTRODUCTION

The paper studies group testing with known, item-specific defect probabilities for independent items, and develops adaptive and non-adaptive algorithms for recovering the population vector. It identifies entropy as the relevant lower-bound benchmark and explains why existing uniform-prior results do not directly settle performance in this setting.

I. INTRODUCTION

  • Prior statistics can vary across subpopulations, while earlier probabilistic group-testing analyses often assume identical item probabilities.The paper frames known prevalence differences, such as by demographic characteristics, as motivation for using item-specific priors.Source: §I · p. 1, A. Related Work · p. 3

1) Model and Notations:

  • Items are independent but may have distinct prior defect probabilities; the expected number of defectives is their probability sum, and the paper assumes this expectation is sparse relative to population size.The model's goal is to recover the binary population vector using disjunctive tests while keeping the error probability small.Source: §I · pp. 1–2, 1) Model and Notations · pp. 4–5

I. INTRODUCTION

  • Uniform-prior probabilistic group testing guarantees do not automatically extend to nonuniform priors, and a test bound proportional to µ log2(n) need not track the entropy lower bound.The paper notes that distributions can have constant µ but arbitrarily small H(X).Source: §I · p. 2

A. Related Work

  • Earlier work includes structured-prior non-adaptive algorithms and nested plans for identical Bernoulli priors, but the latter recursive design is exponential in n and lacks an explicit test-count bound.The prior-information setting in restricts items within each part to a uniform fixed-size subset.Source: A. Related Work · pp. 2–3
  • The paper notes that its independent-item model does not cover finer structures such as neighboring-variable correlations or geography- and social-structure constraints.These richer probabilistic models are described as ongoing areas of investigation.Source: A. Related Work · p. 2

B. Contributions

  • The paper gives explicit adaptive and non-adaptive algorithms whose expected test counts are within computed constant factors of the information-theoretic lower bound, with high-probability concentration under mild distributional assumptions.The adaptive designs connect group testing with source codes such as Shannon-Fano and Huffman codes.Source: B. Contributions · p. 3

2) Pre-partition Model:

The pre-partition procedure sorts item probabilities into subsets with controlled properties and assigns different testing treatments to the tails and the remaining groups. The section also gives an entropy-based lower bound on the tests required for probabilistic group testing.

2) Pre-partition Model:

  • The pre-partition sorts item probabilities and divides items into L disjoint subsets, with two unbounded tails and L−2 remaining subsets that are well-balanced and γ-bounded.The number L depends on the error threshold, probability vector, and population size.Source: 2) Pre-partition Model · p. 5
  • Ample subsets are tested separately, undersized subsets and the final unbounded subset are combined for individual testing, and the first tail is treated as non-defective without tests.The first-tail assignment relies on small probabilities and a union-bound error control.Source: 2) Pre-partition Model · p. 6, Figure 1 · p. 6

B. Fundamental Limits

  • At most (1 − Pe)H(X) tests are required as a lower bound for any noiseless probabilistic group-testing algorithm with error probability at most Pe.The paper relates this entropy benchmark to the lower bound on expected code length.Source: B. Fundamental Limits · pp. 6–7
  • The entropy lower bound serves as a simulation benchmark for the paper's adaptive and non-adaptive algorithms.The paper presents the bound as analogous to the coding lower bound for expected code length.Source: B. Fundamental Limits · p. 7

III. MAIN RESULTS

The section introduces adaptive laminar testing trees and a maximum-entropy construction that chooses tests using conditional defective probabilities. Both adaptive constructions achieve the same upper bound in Theorem 2.

A. (Adaptive) Laminar Algorithms

1) Maximum Entropy-based Laminar Algorithm:

2) Shannon-Fano/Huffman Coding-based Laminar Algorithm:

The coding-based adaptive construction builds testing trees using item probabilities as source-code weights. The section also bounds the expected test count and describes partitioning independent subsets to concentrate the actual count.

2) Shannon-Fano/Huffman Coding-based Laminar Algorithm:

3) Concentration of the Number of Tests:

B. (Non-adaptive) Block Algorithm

The block algorithm applies CCA within a pre-partition to address nonuniform prior distributions, and its test bound scales with the entropy of the population vector.

B. (Non-adaptive) Block Algorithm

  • Non-adaptive tests are fixed in advance and can be run in parallel, which is convenient for hardware design.The tests are represented by a Boolean matrix whose rows are measurements and columns are items.Source: B. (Non-adaptive) Block Algorithm · p. 10

1) Coupon Collector Algorithm:

  • CCA samples g items with replacement according to bpi = (1 − pi)/(n − µ), but its bound can be worse than the PGT information-theoretic lower bound when p is nonuniform.The sampling parameter g is chosen by optimization based on the probability vector p.Source: 1) Coupon Collector Algorithm · p. 10

2) Block Design based on the Pre-partition Model:

  • The block design uses CCA independently on ample subsets, sets all items in N1 to 0, and tests items individually in non-ample subsets and NL.The construction assumes a suitable pre-partition; its definitions cover a broad class of nonuniform distributions, though not all distributions.Source: 2) Block Design based on the… · pp. 10–11, Figure 3 · p. 11

C. Upper Bounds on the Number of Tests T

IV. EXPERIMENTAL RESULTS

The experiments examine laminar and block algorithms across uniform, linear, and exponential prior-probability vectors. For laminar algorithms, expected test counts grow linearly with entropy across the tested points.

IV. EXPERIMENTAL RESULTS

  • The experiments cover uniform, linear, and exponential prior-probability vectors for both laminar and block algorithms.For laminar algorithms, both maximum-entropy and Huffman constructions were tested.Source: §IV · p. 13
  • Expected laminar-algorithm tests grow linearly with H(X) across the tested entropy points and probability-vector types.The simulations used 200 entropy points and 200 independent trials at each point.Source: §IV · p. 13, Figure 4 · p. 14, Figure 5 · p. 14
  • For the block algorithm, simulated error probabilities are compared with theoretical Pe across three prior types and μ values 8, 16, and 32.Each condition uses 200 independent trials.Source: §IV · p. 13, Figure 6 · p. 14

V. APPENDIX

The proof of Theorem 1 bounds recovery information through the noiseless test outcomes, using the Markov structure and Fano’s inequality.

V. APPENDIX

  • The input X, noiseless outcome B, and estimate Y form the Markov chain X → B → Y.This sets up the proof’s information-theoretic bound.Source: A. Proof of Theorem 1 · p. 16
  • Fano’s inequality bounds conditional entropy by H(Pe) + PeH(X) using the error event E.The proof first defines E, then applies the inequality to X conditioned on Y.Source: A. Proof of Theorem 1 · p. 16
  • The information in the test outcomes is at most T, since I(X; B) ≤ H(B) ≤ log2 |B| = T.The proof invokes data processing to obtain the bound.Source: A. Proof of Theorem 1 · p. 16

B. Proof of Theorem 2

Theorem 2’s proof bounds expected tests for maximum-entropy and Shannon-Fano/Huffman constructions, using coding-based branch lengths and the testing procedure.

B. Proof of Theorem 2

  • The proof establishes expected-test bounds for both maximum-entropy and Shannon-Fano/Huffman constructions.The Shannon-Fano/Huffman procedure is argued to be well-defined when prior probabilities within each subset sum to at most 1.Source: B. Proof of Theorem 2 · pp. 16–17
  • For maximum-entropy construction, the group design bounds the branch length associated with each prior probability.The proof introduces probabilities involved in a test at stage k before bounding branch length.Source: B. Proof of Theorem 2 · p. 16
  • The proof extends the branch-length inequality to Shannon-Fano coding and supplies a lemma to establish the coding procedure’s validity.It then uses the lemma’s inequality and a geometric-sum expansion.Source: B. Proof of Theorem 2 · p. 17
  • In the testing procedure, a positive outcome triggers two additional tests, one for each child.For an item on a branch of length ℓ_i, the text bounds its required tests by 2ℓ_i when it is defective.Source: B. Proof of Theorem 2 · p. 18

C. Proof of Corollary 1

The proof of Corollary 1 establishes concentration of the adaptive test count by partitioning items, bounding tests per subset, and applying Hoeffding’s inequality.

C. Proof of Corollary 1

  • For each subset N_s, the expected test count satisfies E[T_s] ≤ 2H(X_s) + 6μ_s.The bound is attributed to Theorem 2.Source: C. Proof of Corollary 1 · p. 18
  • The subset test counts T_1, …, T_K are independent because the item variables are independent, and T is their sum.This independence supports applying Hoeffding’s inequality.Source: C. Proof of Corollary 1 · p. 18
  • The proof sets K = n^3/4 subsets, each of size n^1/4, and relates the aggregate bound to H(X) and μ.The passage gives the aggregate inequality as μ_s ≤ 2H(X) + 6μ.Source: C. Proof of Corollary 1 · p. 18

D. Proof of Theorem 3

The proof recasts identifying non-defective items as coupon collection through negative tests, then combines stopping-time and tail bounds to control the required tests.

D. Proof of Theorem 3

  • The proof maps non-defective items to coupons and negative tests that reveal them to a coupon-collection chain.This is the framework used to identify all non-defective items in the universal set.Source: D. Proof of Theorem 3 · p. 18
  • The stopping-time expression is bounded by (n + μ) ln n.The bound follows after substituting into the earlier expression and optimizing g.Source: D. Proof of Theorem 3 · p. 20
  • A Chernoff bound and a coupon-collector tail estimate combine two error events to yield a high-probability bound.The tail estimate bounds the probability that collection requires more than βE[T] coupons; the proof applies a union bound.Source: D. Proof of Theorem 3 · p. 20

E. Proof of Theorem 4

The proof separates tests for ample and non-ample subsets, bounds their combined total, and controls error using subset-level results and a union bound.

E. Proof of Theorem 4

  • Non-ample subsets require at most (L − 2)(Γγ − 1) + 2μ tests.The bound covers at most L − 2 subsets and the items in NL.Source: E. Proof of Theorem 4 · p. 21
  • For each ample subset, Theorem 3 bounds the test count T1 with error probability at most 2n^-δ.The passage introduces the per-subset bound, whose expression is not included here.Source: E. Proof of Theorem 4 · p. 21
  • The proof bounds H(X_s) by e ln n log2(1/γ)(1 + δ)H(X), then uses a union bound in deriving the total-test bound.It also bounds misclassification in the first subset by Pe/2.Source: E. Proof of Theorem 4 · p. 22
  • The total test count T is bounded by an entropy-dependent ample-subset term plus Γ2.The displayed bound is T = Tample + Tnon ≤ e ln n log2(1/γ)(1 + δ)H(X) + Γ2.Source: E. Proof of Theorem 4 · pp. 21–22
Loading 1401.3667v8…