Conservative two-stage group testing in the linear regime

1.1 Group testing

• The linear regime fixes prevalence p as n grows, unlike the sparse regime where p tends to zero, making confirmation costs mathematically important.Source: §1.1 · p. 2, §1.2 · p. 4

1.3 Main results

• The study assumes perfectly accurate tests and notes that integer design parameters create jumps producing crooked aspect-ratio lines and bumpy rate curves.Source: §1.1 · p. 2, §1.3 · pp. 5, 7

1.2 Conservative two-stage testing

• Two-stage testing offers parallel execution within each stage, trading the speed of nonadaptive testing against the test savings and slowness of fully adaptive schemes.Source: §1.2 · pp. 2–3
• Conservative testing uses pooled first-stage tests only to identify definite nondefectives, then individually tests every item whose status remains unknown.Every defective must be certified by appearing alone in a positive second-stage test, providing a gold-standard confirmation.Source: §1.2 · pp. 3–4

1.3 Main results

• Dorfman’s algorithm is best among the considered schemes for 0.121 < p < 0.307, while individual testing is provably best for p ≥ (3 − √5)/2 = 0.382.Source: §1.3 · pp. 4–5
• The doubly constant design is the best considered for all prevalences and is extremely close to the lower bound.For p > 0.307, it uses no first-stage tests; for 0.121 < p < 0.307, it uses r = 1 and recovers Dorfman’s algorithm.Source: §1.3 · p. 5
• The paper derives a new lower bound for conservative two-stage testing and a further lower bound for usual non-conservative two-stage testing.Source: §1.3 · p. 5
• The theoretical comparisons use expected tests per item and information rate against individual testing, the counting bound, and Theorem 6’s lower bound.The rate is nH(p)/ET, while the aspect ratio is ET/n.Source: §1.3 · p. 5

• The simulated algorithms used parameters optimized for p = 0.027 in the large-n limit, including r = 4 tests per item for both constant designs.The doubly constant design used s = 25 items per test and T1 = 160 first-stage tests; the constant tests-per-item design used T1 = 160.Source: §2 · p. 7
• The simulations used n = 1000 items, prevalence p = 0.027, and 1000 repetitions, comparing empirical means and deciles with large-n theory evaluated at n = 1000.The prevalence was chosen to match an estimate for UK covid-19 prevalence at the time of the simulations.Source: §2 · p. 7, Table 1 · p. 8
• Four-fold reductions in average tests versus individual testing were achieved by constant tests-per-item and doubly constant designs.All four group-testing algorithms achieved at least a three-fold reduction; the constant tests-per-item and doubly constant designs achieved four-fold reductions.Source: §2 · p. 7, Table 1 · p. 8
• The constant tests-per-item and doubly constant designs improved substantially over Dorfman’s algorithm, while their difference was small.The simulations support the theoretical prediction that constant tests-per-item designs are very close to optimal at this prevalence.Source: §2 · p. 7
• Dorfman’s results closely matched theoretical predictions, whereas the Bernoulli, constant tests-per-item, and doubly constant designs used about 6 more tests on average.The discrepancy was attributed to rare simulations with unusually large defective populations when pn = 27.Source: §2 · pp. 7–8

3.2 Dorfman’s algorithm

• Dorfman’s algorithm uses groups of size s, optimally s ∼ 1/√p as p →0, yielding ET ∼ 2√p n and a rate tending to zero.Its rate is 3√3 = 0.307, and s = 2 is never optimal.Source: §3.2 · pp. 8–9

3.3 Bernoulli first stage

• Bernoulli first-stage testing is close to optimal but not optimal, with optimal π = 1/(np) when prevalence is known.It achieves rate 1/(e ln 2) = 0.531 and reverts to individual testing above p = 1/(e + 1) = 0.269.Source: §3.3 · pp. 9–11

3 Algorithms for conservative two-stage testing

• The analysis uses a fixed-k prior as a proof convenience, with results transferring to the i.i.d. prior in the large-n limit.The algorithms do not exploit exact knowledge of k.Source: §3.3 · pp. 9–10

3.4 Constant tests-per-item first stage

• Constant tests-per-item designs achieve rates approaching ln 2 and are optimal as p tends to zero.For known prevalence, r and σ can be numerically optimized.Source: §3.4 · p. 11

3.5 Doubly constant first stage

• Doubly constant designs achieve the same p →0 asymptotic behavior as constant tests-per-item designs.The sparse-limit choice is s = (ln 2)/p and r = log2 1/p, up to integer rounding.Source: §3.5 · p. 13

3.6 Comparison to a multi-stage scheme of Mutesa et al.

• The compared Mutesa et al. multi-stage scheme has sparse-limit rate 1/(e ln 2) = 0.531, below the constant tests-per-item and doubly constant designs.Unlike the paper’s schemes, it may require further stages when an initial pool contains multiple defectives.Source: §3.6 · p. 14

4.1 Lower bound for two-stage testing

• Theorem 5 lower-bounds usual two-stage testing by bounding hidden items, defined as items whose every first-stage test contains another defective item.The proof uses the probability that an item is hidden and optimizes the first-stage test count.Source: §4.1 · pp. 15, 17
• For usual two-stage testing, optimizing the first-stage test count yields T1 = n 1/f(p) ln f(p) and total expected tests at least n 1/f(p) (ln f(p) + 1).Source: §4.1 · p. 17

4.2 Lower bound for conservative two-stage testing

• Theorem 6 gives conservative-testing bounds based on two counts of items requiring second-stage tests: all items in only positive tests, or all defectives plus hidden nondefectives.Bound 2 counts every item appearing solely in positive tests; Bound 3 counts the average pn defectives plus nondefectives appearing solely in positive tests.Source: §4.2 · p. 17
• The conservative lower-bound rate is at most ln 2 = 0.693 as p →0.Source: §4.2 · pp. 17, 19
• Testing with a doubly constant first stage is very close to optimal for all p and extremely close to optimal for p ≤ 1/4.The comparison is made against the lower bounds derived in this section and the algorithms’ results in Figure 1.Source: §4.2 · p. 17
• In the limit p →0, constant tests-per-item and doubly constant designs achieve the optimal rate.Source: §4.2 · p. 17