2026-07-26T19:18:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20218 2024-07-02T07:52:52Z ddc:004 open_access

Sharp Noisy Binary Search with Monotonic Probabilities Gretta, Lucas Price, Eric fine-grained algorithms randomized/probabilistic methods sublinear/streaming algorithms noisy binary search We revisit the noisy binary search model of [Karp and Kleinberg, 2007], 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 ε) of a target value τ. This generalized the fixed-noise model of [Burnashev and Zigangirov, 1974], in which p_i = 1/2 ± ε, to a setting where coins near the target may be indistinguishable from it. It was shown in [Karp and Kleinberg, 2007] that Θ(1/ε² 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 1/C_{τ, ε} ⋅ (log₂ n + O(log^{2/3} n log^{1/3} 1/(δ) + log 1/(δ))) samples, where C_{τ, ε} is the optimal such constant achievable. For δ > n^{-o(1)} this is within 1 + o(1) of optimal, and for δ ≪ 1 it is the first bound within constant factors of optimal. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lucas Gretta and Eric Price 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.75 urn:nbn:de:0030-drops-202188 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.75 eng https://creativecommons.org/licenses/by/4.0/legalcode