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 $p_i$ that we can flip. The coins are sorted by increasing $p_i$, and we would like to find where the probability crosses (to within $\epsilon$) of a target value $\tau$. This generalized the fixed-noise model of Burnashev and Zigangirov , in which $p_i=\frac{1}{2}\pm \epsilon$, to a setting where coins near the target may be indistinguishable from it. Karp and Kleinberg showed that $\mathrm{\Theta }(\frac{1}{{\epsilon }^2}\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-\delta$ from $$\frac{1}{C_{\tau ,\epsilon }}\cdot (\lg n+O({\log }^{2\mathrm{/}3}n{\log }^{1\mathrm{/}3}\frac{1}{\delta }+\log \frac{1}{\delta }))$$ samples, where $C_{\tau ,\epsilon }$ is the optimal such constant achievable. For $\delta >n^{-o(1)}$ this is within $1+o(1)$ of optimal, and for $\delta \ll 1$ it is the first bound within constant factors of optimal.