论文标题
一种基于实例的算法，用于决定硬币的偏差
An Instance-Based Algorithm for Deciding the Bias of a Coin
论文作者
论文摘要
令$ q \ in（0,1）$和$δ\ in（0,1）$为实数，让$ c $是带有未知概率$ p $的硬币，这样$ p \ neq q $。我们提出了一种算法，该算法在输入$ c $，$ q $和$δ$上，决定，概率至少$ 1-δ$，无论是$ p <q $还是$ p> q $。该算法进行的预期硬币翻转数为$ o \ left（\ frac {\ log \ log \ log \ log（1/\ varepsilon） + \ log（1/δ）} {\ varepsilon^2} \ right）
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|$.
