Sharp Noisy Binary Search with Monotonic Probabilities

We revisit the noisy binary search model of Karp and Kleinberg, in which we have n coins with unknown probabilities pi that we can flip. The coins are sorted by increasing pi, and we would like to find where the probability crosses (to within varepsilon) of a target value τ. This generalized the fixed-noise model of Burnashev and Zigangirov , in which pi = frac12 ± varepsilon, to a setting where coins near the target may be indistinguishable from it. Karp and Kleinberg showed that Theta(frac1varepsilon2 log n) samples are necessary and sufficient for this task. We produce a practical algorithm by solving two theoretical challenges: high-probability behavior and sharp constants. We give an algorithm that succeeds with probability 1-δ from [ frac1Cτ, varepsilon · left(lg n + O(log2/3 n log1/3 frac1δ + log frac1δ)right) ] samples, where Cτ, varepsilon is the optimal such constant achievable. For δ > n-o(1) this is within 1 + o(1) of optimal, and for δ ll 1 it is the first bound within constant factors of optimal.