2020/11/11 by da Silveira, Luís Fernando Schultz Xavier, Smid, Michiel
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2011.05502
Let q ∈ (0,1) and δ∈ (0,1) be real numbers, and let C be a coin that comes up heads with an unknown probability p, such that p ≠ q. We present an algorithm that, on input C, q, and δ, decides, with probability at least 1-δ, whether pq. The expected number of coin flips made by this algorithm is O ( (loglog(1/ε) + log(1/δ))/(ε2) ), where ε = |p-q|.