Binary Search with Errors

Question

Suppose I give you $n$ labelled coins $C_1, \cdots, C_n$ of unknown bias. I promise you that

• 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$).

Your 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.

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?

Answer 1

A good old trick is that it's sufficient to give an algorithm that achieves this with $O(\log n)$ expected number of coin flips and $99\%$ probability, as if we are exceeding the expected running time a lot, we can just output anything, using Markov's inequality this won't ruin our error much. And this we can do as follows.

Always keep an active interval that is supposed to contain an approximately unbiased coin (but might not). Then repeat the following.

1, Halve the size of the active interval by flipping its middle coin a couple of times. Update the active interval (if the middle coin showed no bias, then arbitrarily).

2, Flip both ends of the active interval a couple of times to check that we made no errors. If an error is detected, then go back to the previous active interval.

This way, with a constant number of coin tosses we halve the size of our active interval with high probability and double it with small probability. Thus, in $O(\log n)$ expected time, we reach size $1$, which means one coin. We can check this coin with $\log n$ further coin tosses (though I'm not sure if this is necessary).