4
$\begingroup$
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?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ This is slightly different, but there's oldish literature on binary search where each comparison is correct with probability $\frac{1}{2} + \epsilon$ and incorrect otherwise. Maybe that can be useful. Feige et al 1994, Adler et al 1994 $\endgroup$ – usul Apr 19 '16 at 16:59
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Could you maybe flesh this out a bit? $\endgroup$ – usul Feb 2 '16 at 23:55
  • $\begingroup$ I didn't do any deeper calculations, the OP or anyone is welcome to do it (and reveal the mistakes in my argument ;)! $\endgroup$ – domotorp Feb 3 '16 at 6:42
  • $\begingroup$ I don't see how to complete the analysis. I presume you want to apply Azuma's inequality to the log of the length of the active interval. You argue that it decreases in expectation, conditioned on the active interval being correct. But what if it is not correct? Then the length will increase. How do you handle that case? $\endgroup$ – Thomas Feb 4 '16 at 7:06
  • $\begingroup$ No Azuma. If an unbiased coin is in the interval, then it gets shorter whp, so with, say 90% probability we "go ahead" one step, with 10% we "step back" and there are $\log n$ ahead steps to be made, thus we need $O(\log n)$ steps in expectation. $\endgroup$ – domotorp Feb 4 '16 at 7:29
  • $\begingroup$ Given that the active interval is correct, it keeps getting shorter. But if it is not correct, how do you argue that we continue to make progress? $\endgroup$ – Thomas Feb 4 '16 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.