<p>A good old trick is that it's sufficient to give an algorithm that achieves this with $O(\log n)$ <em>expected number</em> 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.</p>

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

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

<p>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.</p>

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

CC BY-SA 3.0
2016-02-02T23:55:56.283Z
Could you maybe flesh this out a bit?
usul
CC BY-SA 3.0
2016-02-03T06:42:50.210Z
I didn't do any deeper calculations, the OP or anyone is welcome to do it (and reveal the mistakes in my argument ;)!
domotorp
CC BY-SA 3.0
2016-02-04T07:06:39.143Z
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?
Thomas Steinke
CC BY-SA 3.0
2016-02-04T07:29:34.323Z
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.
domotorp
CC BY-SA 3.0
2016-02-04T16:21:34.137Z
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?
Thomas Steinke
CC BY-SA 3.0
2016-02-04T20:35:09.990Z
This is what also seems tricky to me: arguing about the probability of success of the algorithm.
usul
CC BY-SA 3.0
2016-02-05T08:49:03.473Z
Imagine that we walk in a binary tree where some of the leaves are "good," forming a consecutive interval. Each step takes us towards these leaves whp, and in the wrong direction if an "error" occurs. Then we soon reach (and spend most time around) the good leaves.
domotorp
CC BY-SA 3.0
2016-02-02T21:39:17.497Z
2016-02-02T21:39:17.497Z
domotorp
<blockquote>
Suppose I give you $n$ labelled coins $C_1, \cdots, C_n$ of unknown bias. I promise you that
<ul>
<li>the coins have been sorted by bias (i.e. $\forall i~~\mathbb{P}[C_i=1]\leq\mathbb{P}[C_{i+1}=1]$) and</li>
<li>at least one of the coins is unbiased (i.e. $\exists i~~\mathbb{P}[C_i=1]=\frac12$).</li>
</ul>
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.
</blockquote>

<p>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.</p>

<p>Can we do this using $O(\log n)$ coin flips?</p>

CC BY-SA 3.0
2016-04-19T16:59:13.187Z
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](http://dl.acm.org/citation.cfm?id=196817), [Adler et al 1994](http://dl.acm.org/citation.cfm?id=314650)
usul
<search-problem>
Binary Search with Errors
Thomas Steinke
# Binary Search with Errors

(Asked by: username_0 on 2016-02-02)

> 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?

**Tags:** search-problem
> **Comments:**
> **username_1**: 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](http://dl.acm.org/citation.cfm?id=196817), [Adler et al 1994](http://dl.acm.org/citation.cfm?id=314650)  

---

## 1 answers

### Answer by username_2 on 2016-02-02. Score: 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).

> **Comments:**
> **username_1**: Could you maybe flesh this out a bit?  
> **username_2**: I didn't do any deeper calculations, the OP or anyone is welcome to do it (and reveal the mistakes in my argument ;)!  
> **username_0**: 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?  
> **username_2**: 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.  
> **username_0**: 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?  
> **username_1**: This is what also seems tricky to me: arguing about the probability of success of the algorithm.  
> **username_2**: Imagine that we walk in a binary tree where some of the leaves are "good," forming a consecutive interval. Each step takes us towards these leaves whp, and in the wrong direction if an "error" occurs. Then we soon reach (and spend most time around) the good leaves.  

---

