# Sharp Noisy Binary Search with Monotonic Probabilities

arXiv: https://arxiv.org/abs/2311.00840 · HTML: https://mlsanity.com/paper/2311.00840/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 15 references that are in the map.
- First posted on arXiv 1 Nov 2023.

## Builds on (most cited first, 5 of 5)

- [Optimal Identity Testing with High Probability](https://mlsanity.com/paper/1708.02728/) (2017)
- [Optimal Bounds for Noisy Sorting](https://mlsanity.com/paper/2302.12440/) (2023)
- [Deterministic and Probabilistic Binary Search in Graphs](https://mlsanity.com/paper/1503.00805/) (2015)
- [A Framework for Searching in Graphs in the Presence of Errors](https://mlsanity.com/paper/1804.02075/) (2018)
- [Noisy Adaptive Group Testing via Noisy Binary Search](https://mlsanity.com/paper/2106.12193/) (2021)

## Built on by (most cited first, 3 of 3)

- [Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes](https://mlsanity.com/paper/2604.07796/) (2026)
- [Sequential 1-bit Mean Estimation with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2509.21940/) (2025)
- [Batched Stochastic Linear Bandits with 1-Bit Communication Constraints](https://mlsanity.com/paper/2605.30976/) (2026)

## Abstract (arXiv)

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.