Probabilistic Bisection Algorithm Provably Achieves Exponential Convergence

The probabilistic bisection algorithm (PBA) extends the classical binary search to settings with noisy responses, and is a foundational algorithm commonly used in basic problems such as root-finding. Despite its strong empirical success, its theoretical property, particularly the convergence rate, remains unclear. This paper establishes that PBA converges at a geometric rate, providing a rigorous justification for its empirical efficiency. Notably, this rate is optimal in the sense that it matches the performance of classical binary search under noiseless responses. The core of our analysis lies in directly characterizing the dynamics of PBA queries, which had not been examined in the prior literature. We show that the queries oscillate around the truth but steadily draw closer, thus leading to an estimator that rapidly concentrates on the truth. Beyond resolving the long-standing question of PBA’s convergence, our developed techniques offer new tools for analyzing PBA's dynamics, which may be of independent interest.

When searching for an answer using binary search, real-world feedback is often noisy or unreliable. The probabilistic bisection algorithm (PBA) is a popular method designed to handle this uncertainty and is widely used in applications such as root-finding and optimization. Despite its strong practical performance, researchers have long lacked a rigorous understanding of how quickly it converges to the correct answer. In this work, we prove that PBA converges exponentially fast, matching the optimal speed of classical binary search in noiseless settings. Our analysis reveals that the algorithm’s queries naturally oscillate around the true solution while steadily moving closer over time. This explains why PBA performs so efficiently in practice. Beyond resolving this long-standing theoretical question, our techniques also provide new mathematical tools for analyzing noisy search algorithms more broadly.