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

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