ASYMPTOTIC ANALYSIS OF OPTIMAL NESTED GROUP-TESTING PROCEDURES. Issue 4 (29th June 2016) - Zaman, Nabil; Pippenger, Nicholas
Abstract : We analyze a construction for optimal nested group-testing procedures, and show that, when individuals are independently positive with probability p, the expected number of tests per positive individual, F *( p ), has, as p →0, the asymptotic behavior $$F^{*}(p) = \log_2 {1\over p} + \log_2 \log 2 + 2 + f\left(\log_2 {1\over p} + \log_2 \log 2\right) + O(p), $$ where $$f(z) = 4× 2^{-2^{1-\{z\}}} - \{z\} - 1, $$ and { z }= z −⌊ z ⌋ is the fractional part of z . The function f ( z ) is a periodic function (with period 1) that exhibits small oscillations (with magnitude <0.005) about an even smaller average value (<0.0005).