Sharp Noisy Binary Search with Monotonic Probabilities
Lucas Gretta Eric Price
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 $\varepsilon$) of a target value $\tau$. This generalized
the fixed-noise model of Burnashev and Zigangirov , in which $p_i = \frac{1}{2}
\pm \varepsilon$, to a setting where coins near the target may be
indistinguishable from it. Karp and Kleinberg showed that
$\Theta(\frac{1}{\varepsilon^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, \varepsilon}} \cdot \left(\lg n + O(\log^{2/3} n \log^{1/3}
\frac{1}{\delta} + \log \frac{1}{\delta})\right)
  \]
  samples, where $C_{\tau, \varepsilon}$ 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.