Suppose I give you $n$ labelled coins $C_1, \cdots, C_n$ of unknown bias. I promise you thatYour task is to find an approximately unbiased coin. That is, you must find $i_*$ such that $\mathbb{P}[C_{i_*}=1] \in [\frac13,\frac23]$. To do this, you should flip as few coins as possible.
- the coins have been sorted by bias (i.e. $\forall i~~\mathbb{P}[C_i=1]\leq\mathbb{P}[C_{i+1}=1]$) and
- at least one of the coins is unbiased (i.e. $\exists i~~\mathbb{P}[C_i=1]=\frac12$).
Here is an algorithm that completes the task by flipping $O(\log n \cdot \log \log n)$ coins: Perform a binary search over the coins - this takes $O(\log n)$ steps. For each step, flip the coin $O(\log \log n)$ times so that the bias of the coin can be approximated to within $0.1$ with probability at least $1-1/O(\log n)$. A union bound shows that this will be correct with high probabiliy.
Can we do this using $O(\log n)$ coin flips?