Sharp Noisy Binary Search with Monotonic Probabilities. (arXiv:2311.00840v1 [cs.DS])

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. …

arxiv binary coins probability search value