An Instance-Based Algorithm for Deciding the Bias of a Coin

Abstract

Let $q\in (0,1)$ and $\delta \in (0,1)$ be real numbers, and let $C$ be a coin that comes up heads with an unknown probability $p$, such that $p\ne q$. We present an algorithm that, on input $C$, $q$, and $\delta$, decides, with probability at least $1-\delta$, whether $p<q$ or $p>q$. The expected number of coin flips made by this algorithm is $O\left(\frac{\log \log (1/\epsilon )+\log (1/\delta )}{{\epsilon }^2}\right)$, where $\epsilon =|p-q|$.