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) = _2 1p + _2 2 + 2 + f(_2 1p + _2 2) + 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).