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