<p>The following is a rather straight-forward <span class="math-container">$O(n \log n)$</span> toss algorithm.</p>

<p>Assume <span class="math-container">$1-\exp(-n)$</span> is the error probability we are aiming for. Let <span class="math-container">$N$</span> be some power of <span class="math-container">$2$</span> that is between say <span class="math-container">$100n$</span> and <span class="math-container">$200n$</span> (just some big enough constant times <span class="math-container">$n$</span>). We maintain a candidate set of coins, <span class="math-container">$C$</span>. Initially, we put <span class="math-container">$N$</span> coins in <span class="math-container">$C$</span>.</p>

<p>Now for <span class="math-container">$i=1,\dots,\log N$</span>, do the following:<br>
Toss each coin in <span class="math-container">$C$</span> for <span class="math-container">$D_i = 2^i  10^{10}$</span> times (just some big enough constant).<br>
Keep the <span class="math-container">$N/2^i$</span> coins with most heads.</p>

<p>The proof is based on a couple of Chernoff bounds. The main idea is that we half the number of candidates each time and thus can afford twice as many tosses of each coin.</p>

CC BY-SA 3.0
2015-06-24T14:14:35.127Z
(1) It would be nice to write down the proof in more detail - much of the difficulty in this problem is in where to place the threshold for the Chernoff bound (how many heads do you expect to see from the 0.9 bias coins?). (2) Can you show that nlogn coin tosses are necessary?
Dana Moshkovitz
CC BY-SA 3.0
2015-06-24T16:17:18.693Z
The subtlety is this: you start with n coins, and except with prob exp small in n, there are at least 0.6n coins of bias 0.9. Now there's constant prob that the 0.9 bias coins lose the competition to: 1 coin with bias less than 0.8 (may happened to fall on head all the time!), 2 coins with bias 0.8+1/logn,..., n/10 coins with bias 0.9 - 1/log n. Continue in a similar manner, where the bias of the chosen coins degrades with each iteration, until you're left with the coin of bias < 0.8.
Dana Moshkovitz
CC BY-SA 3.0
2015-06-24T18:22:15.367Z
Hi. Was just on my way to head out the door earlier. I see your point in the last comment. The proof I did was only for 0.8 bias vs 0.9 bias in which case you set all Chernoff bound cut-off to 0.85 times number of tosses pr coin. It's not obvious how to make it work for your example. One thing that should work is to do $2^i \cdot \log^2 n \cdot 1000$ tosses per coin and then argue that a large fraction of surviving coins have bias at least $0.9(1-1/(100 \log n))^i$. This unfortunately gives an $O(n \log^3 n)$ toss algorithm. If you would like the full proof for this, I'm sure I can write it up
Kasper Green Larsen
CC BY-SA 3.0
2015-06-24T18:23:53.877Z
Which sadly isn't what we are after. I'm not sure whether you can prove that the above algorithm actually works with $O(n \log n)$  tosses after seeing your example. It needs more subtle ideas. Sorry :)
Kasper Green Larsen
CC BY-SA 3.0
2015-06-24T20:53:57.653Z
This is more or less the Median Elimination algorithm of Evan-Dar et. al. As shown by Mannor and Tsitsiklis in [The
Sample Complexity of Exploration in the Multi-Armed Bandit Problem](http://www.jmlr.org/papers/volume5/mannor04b/mannor04b.pdf) it can be used to get expected $O(n)$ coin tosses when the the target bias is known as in this case.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2015-06-24T23:41:55.363Z
Thanks for the reference! I'm interested in the max number of coin tosses one needs, and for this case they show an n^2 lower bound. However, the problem they consider is different from mine. They have n coins, there might only be one that is most biased, and they want to find a coin with a similar bias. In my setup I know that there are at least 0.6n coins with acceptable bias (except with prob exponentially small in n).
Dana Moshkovitz
CC BY-SA 3.0
2015-06-25T00:53:50.707Z
There's a protocol with ~ n(logn)^2 coin tosses when you consider just one coin at a time, and keep pushing down a little each time the threshold for the fraction of heads that's acceptable.
Dana Moshkovitz
CC BY-SA 3.0
2015-06-25T05:21:42.363Z
I guess expected $O(n)$ tosses is easy for our problem: Start with the first coin and do $m=\Theta(n)$ tosses for some big constant in the $\Theta(\cdot)$-notation. If that comes out heads at least $0.85m$ times, return it. Otherwise continue to the next coin. The correctness probability is $1-\exp(-n)$ and by the input coins being 0.9 bias independently with probability $2/3$, the probability of reaching the $i$'th coin is less than $(1/2)^i$ and thus the expected number of tosses is $\sum_{i=0}^\infty m/2^i = O(m) = O(n)$.
Kasper Green Larsen
CC BY-SA 3.0
2015-06-25T05:22:43.007Z
With an $O(n \log^2 n)$-toss algorithm, I suppose there is no point in posting the proof for the $O(n \log^3 n)$ algorithm above. What are the exact details for $O(n \log^2 n)$?
Kasper Green Larsen
CC BY-SA 3.0
2015-06-25T14:42:42.263Z
@KasperGreenLarsen is the correctness probability really $1-\exp(-n)$ for this simple procedure? How would you show it?
usul
CC BY-SA 3.0
2015-06-25T15:48:55.627Z
Conceptually think of the algorithm as tossing the first $10n$ coins each $m$ times (even though it doesn't always). Say that a coin errs if it is bias <=0.8 but we has more than 0.85m heads, or if it is bias 0.9 and has less than 0.85m heads. By Chernoff bound, a coin errs with probability $\exp(-2n)$ if $m$ is some sufficiently large constant times $n$. Now by a union bound over the $10n$ first coins, one of them errs with prob. at most $10n \cdot \exp(-2n) < \exp(-1.5n)$. Now, conditioned on not err'ing on the first $10n$ coins, the algorithm only reaches the $10n+1$'st coin if there are no
Kasper Green Larsen
CC BY-SA 3.0
2015-06-25T15:50:28.250Z
0.9 bias coins amongst the $10n$ first coins. But this happens with probability $(1/3)^{10n} < \exp(-1.5n)$. So the probability of making an error is at most $2 \exp(-1.5n) < \exp(-n)$.
Kasper Green Larsen
CC BY-SA 4.0
2015-06-24T08:47:13.820Z
2019-01-24T09:02:13.173Z
2019-01-24T09:02:13.173Z
Kasper Green Larsen
<p>The following problem came up during research, and it's surprisingly clean:</p>

<p>You have a source of coins. Each coin has a bias, namely a probability that it falls on "head". 
For each coin independently there's probability 2/3 that it has bias at least 0.9, and with the rest of the probability its bias can be any number in [0,1]. You don't know the biases of the coins. All you can do at any step is toss a coin and observe the outcome.</p>

<p>For a given n, your task is to find a coin with bias at least 0.8 with probability at least $1-\exp(-n)$. Can you do that using only O(n) coin tosses?</p>

CC BY-SA 3.0
2015-06-23T01:03:19.717Z
Seems very unlikely to me, since $O(n)$ tosses seem to be required just to determine if a given coin is high-bias or not with confidence $1-\exp(-n)$. (We may as well assume that each coin has bias either $0.9$ or $0.8-\epsilon$.) Do you have anything better than $O(n^2)$ tosses?
usul
CC BY-SA 3.0
2015-06-23T01:20:21.020Z
@usul You might get some more power by looking at a coin with the maximum number of heads. E.g.: Take $m$ coins, flip each of them $k$ times (where $mk$ is $O(n)$) and take the coin with the max number of heads, breaking ties arbitrarily or something. I suspect this might be doable with a careful selection of $m$ and $k$.
mhum
CC BY-SA 3.0
2015-06-23T01:26:36.833Z
@mhum, what is the chance that all $m$ coins you toss are low-bias? It's $(1/3)^m = e^{-\Theta(m)}$, in other words, unless $m = \Omega(n)$, there is at least an $\exp(-n)$ chance that every single coin touched is low-bias. So $k$ would have to be constant. Perhaps the algorithm could start like that, but stop flipping any coin as soon as it comes up tails, ending by picking the coin with the longest streak of heads....
usul
CC BY-SA 3.0
2015-06-23T01:47:19.320Z
@usul That's a good point. In the case of constant $k$, as $n$ increases, so too does the risk of ties. In that case, we'd probably need a somewhat smarter way to break ties. Maybe something like keep flipping all the tied winners in rounds of $k$ flips until no one is tied. So long as the number of tied winners per round decreases fast enough (which it maybe does?), then I think this might be ok.
mhum
CC BY-SA 3.0
2015-06-23T07:31:45.980Z
I didn't check the math, but the following idea looks promising: For each coin (in succession) do the following test. Pick a parameter $p$, say $0.85$ and perform a random walk on the line using the coin. At *every* step $i$, if the drift away from $0$ is less than $p \cdot i$, discard the coin. Coins with bias .9 should pass this test with constant probability, and failing coins should fail after O(1) steps in expectation, except for the coins with bias very close to $p$. Picking $p$ at random between $.84$ and $.86$ for each coin might fix this.
daniello
CC BY-SA 3.0
2015-06-23T09:04:35.963Z
Don't multiplicative Chernoff bounds let you reject coins whose bias is less than 0.8 but that "look" better than 0.81 with confidence $1-\exp(-n)$ in $O(n)$ tosses? And then, since such "good" coins are non-vanishingly (in fact, highly) likely, you'll find one in $O(1)$ time?
Aryeh
CC BY-SA 3.0
2015-06-23T12:43:11.220Z
@Aryeh: you'll find one with high (constant) probability -- but you need to find one with probability $1-\exp(-n)$.
Clement C.
CC BY-SA 3.0
2015-06-23T12:56:59.800Z
@ClementC. oh I see -- the time I have to wait to find a good coin is distributed Geometrically with parameter 2/3, so it has a small expectation, but that's not good enough.
Aryeh
CC BY-SA 3.0
2015-06-23T13:00:40.713Z
One possible way (suggested by a friend) is to see if the techniques from [this paper](http://arxiv.org/abs/1402.4746.pdf) (Appendix B, on the Modified-Scheffé tournament) could be applied... note that they only get a dependence $\log(1/\delta)$, not $\log^2(1/\delta)$). It's not the exact same problem, but the approach may lead to something that works in your setting.
Clement C.
CC BY-SA 3.0
2015-06-23T13:55:00.120Z
Would $O(n\log n)$ be okay? Do you know a solution with $o(n^2)$ tosses?
Robin Kothari
CC BY-SA 3.0
2015-06-23T14:45:10.460Z
Observation #1: If you knew that all coins either have bias at least 0.9 or at most 0.8, it would have been possible to find a coin with bias at least 0.9 with probability 1-exp(-n) using O(n) tosses: take a coin, for i=1,2,3,..., toss the coin for 2^i times and check whether the fraction of heads is at least 0.89. If not, restart with a new coin. The key lemma: if restart at phase i, then had less than 2^{i+1} coin tosses, and the prob is at most exp(-\Omega(i)).
Dana Moshkovitz
CC BY-SA 3.0
2015-06-23T14:48:26.430Z
@DanaMoshkovitz: seconding Robin's question, the goal is really linear here -- not, say, $\tilde{O}(n)$?
Clement C.
CC BY-SA 3.0
2015-06-23T14:50:54.337Z
It's quite possible that O(nlogn) flips are necessary and sufficient - but we don't have a proof for that yet.
Dana Moshkovitz
CC BY-SA 3.0
2015-06-23T14:59:50.947Z
I *think* I can get $O(n\log n\log\log n)$, although it is very sketchy (and would need to withstand doublechecks). Is it worth writing, or do you already have such an upper bound?
Clement C.
CC BY-SA 3.0
2015-06-24T14:19:46.350Z
Consider asking this on Cross Validated: http://stats.stackexchange.com/ .  If you post, please cross-link both ways.
Zsbán Ambrus
CC BY-SA 3.0
2015-06-26T08:34:05.720Z
@DanaMoshkovitz: are the coins the only source of randomness, or are randomized strategies (using other randomness sources) ok? In that case, do you care about the number of random bits used from these other sources?
daniello
<ds.algorithms><pr.probability>
Finding a biased coin using a few coin tosses
Dana Moshkovitz
# Finding a biased coin using a few coin tosses

(Asked by: username_0 on 2015-06-22)

The following problem came up during research, and it's surprisingly clean:

You have a source of coins. Each coin has a bias, namely a probability that it falls on "head".
For each coin independently there's probability 2/3 that it has bias at least 0.9, and with the rest of the probability its bias can be any number in [0,1]. You don't know the biases of the coins. All you can do at any step is toss a coin and observe the outcome.

For a given n, your task is to find a coin with bias at least 0.8 with probability at least $1-\exp(-n)$. Can you do that using only O(n) coin tosses?

**Tags:** ds.algorithms, pr.probability
> **Comments:**
> **username_1**: Seems very unlikely to me, since $O(n)$ tosses seem to be required just to determine if a given coin is high-bias or not with confidence $1-\exp(-n)$. (We may as well assume that each coin has bias either $0.9$ or $0.8-\epsilon$.) Do you have anything better than $O(n^2)$ tosses?  
> **username_2**: @usul You might get some more power by looking at a coin with the maximum number of heads. E.g.: Take $m$ coins, flip each of them $k$ times (where $mk$ is $O(n)$) and take the coin with the max number of heads, breaking ties arbitrarily or something. I suspect this might be doable with a careful selection of $m$ and $k$.  
> **username_1**: @mhum, what is the chance that all $m$ coins you toss are low-bias? It's $(1/3)^m = e^{-\Theta(m)}$, in other words, unless $m = \Omega(n)$, there is at least an $\exp(-n)$ chance that every single coin touched is low-bias. So $k$ would have to be constant. Perhaps the algorithm could start like that, but stop flipping any coin as soon as it comes up tails, ending by picking the coin with the longest streak of heads....  
> **username_2**: @usul That's a good point. In the case of constant $k$, as $n$ increases, so too does the risk of ties. In that case, we'd probably need a somewhat smarter way to break ties. Maybe something like keep flipping all the tied winners in rounds of $k$ flips until no one is tied. So long as the number of tied winners per round decreases fast enough (which it maybe does?), then I think this might be ok.  
> **username_3**: I didn't check the math, but the following idea looks promising: For each coin (in succession) do the following test. Pick a parameter $p$, say $0.85$ and perform a random walk on the line using the coin. At *every* step $i$, if the drift away from $0$ is less than $p \cdot i$, discard the coin. Coins with bias .9 should pass this test with constant probability, and failing coins should fail after O(1) steps in expectation, except for the coins with bias very close to $p$. Picking $p$ at random between $.84$ and $.86$ for each coin might fix this.  
> **username_4**: Don't multiplicative Chernoff bounds let you reject coins whose bias is less than 0.8 but that "look" better than 0.81 with confidence $1-\exp(-n)$ in $O(n)$ tosses? And then, since such "good" coins are non-vanishingly (in fact, highly) likely, you'll find one in $O(1)$ time?  
> **username_5**: @Aryeh: you'll find one with high (constant) probability -- but you need to find one with probability $1-\exp(-n)$.  
> **username_4**: @ClementC. oh I see -- the time I have to wait to find a good coin is distributed Geometrically with parameter 2/3, so it has a small expectation, but that's not good enough.  
> **username_5**: One possible way (suggested by a friend) is to see if the techniques from [this paper](http://arxiv.org/abs/1402.4746.pdf) (Appendix B, on the Modified-Scheffé tournament) could be applied... note that they only get a dependence $\log(1/\delta)$, not $\log^2(1/\delta)$). It's not the exact same problem, but the approach may lead to something that works in your setting.  
> **username_6**: Would $O(n\log n)$ be okay? Do you know a solution with $o(n^2)$ tosses?  
> **username_0**: Observation #1: If you knew that all coins either have bias at least 0.9 or at most 0.8, it would have been possible to find a coin with bias at least 0.9 with probability 1-exp(-n) using O(n) tosses: take a coin, for i=1,2,3,..., toss the coin for 2^i times and check whether the fraction of heads is at least 0.89. If not, restart with a new coin. The key lemma: if restart at phase i, then had less than 2^{i+1} coin tosses, and the prob is at most exp(-\Omega(i)).  
> **username_5**: @DanaMoshkovitz: seconding Robin's question, the goal is really linear here -- not, say, $\tilde{O}(n)$?  
> **username_0**: It's quite possible that O(nlogn) flips are necessary and sufficient - but we don't have a proof for that yet.  
> **username_5**: I *think* I can get $O(n\log n\log\log n)$, although it is very sketchy (and would need to withstand doublechecks). Is it worth writing, or do you already have such an upper bound?  
> **username_7**: Consider asking this on Cross Validated: http://stats.stackexchange.com/ .  If you post, please cross-link both ways.  
> **username_3**: @DanaMoshkovitz: are the coins the only source of randomness, or are randomized strategies (using other randomness sources) ok? In that case, do you care about the number of random bits used from these other sources?  

---

## 1 answers

### Answer by username_8 on 2015-06-24. Score: 10

The following is a rather straight-forward $O(n \log n)$ toss algorithm.

Assume $1-\exp(-n)$ is the error probability we are aiming for. Let $N$ be some power of $2$ that is between say $100n$ and $200n$ (just some big enough constant times $n$). We maintain a candidate set of coins, $C$. Initially, we put $N$ coins in $C$.

Now for $i=1,\dots,\log N$, do the following:  
Toss each coin in $C$ for $D\_i = 2^i 10^{10}$ times (just some big enough constant).  
Keep the $N/2^i$ coins with most heads.

The proof is based on a couple of Chernoff bounds. The main idea is that we half the number of candidates each time and thus can afford twice as many tosses of each coin.

> **Comments:**
> **username_0**: (1) It would be nice to write down the proof in more detail - much of the difficulty in this problem is in where to place the threshold for the Chernoff bound (how many heads do you expect to see from the 0.9 bias coins?). (2) Can you show that nlogn coin tosses are necessary?  
> **username_0**: The subtlety is this: you start with n coins, and except with prob exp small in n, there are at least 0.6n coins of bias 0.9. Now there's constant prob that the 0.9 bias coins lose the competition to: 1 coin with bias less than 0.8 (may happened to fall on head all the time!), 2 coins with bias 0.8+1/logn,..., n/10 coins with bias 0.9 - 1/log n. Continue in a similar manner, where the bias of the chosen coins degrades with each iteration, until you're left with the coin of bias < 0.8.  
> **username_8**: Hi. Was just on my way to head out the door earlier. I see your point in the last comment. The proof I did was only for 0.8 bias vs 0.9 bias in which case you set all Chernoff bound cut-off to 0.85 times number of tosses pr coin. It's not obvious how to make it work for your example. One thing that should work is to do $2^i \cdot \log^2 n \cdot 1000$ tosses per coin and then argue that a large fraction of surviving coins have bias at least $0.9(1-1/(100 \log n))^i$. This unfortunately gives an $O(n \log^3 n)$ toss algorithm. If you would like the full proof for this, I'm sure I can write it up  
> **username_8**: Which sadly isn't what we are after. I'm not sure whether you can prove that the above algorithm actually works with $O(n \log n)$  tosses after seeing your example. It needs more subtle ideas. Sorry :)  
> **username_9**: This is more or less the Median Elimination algorithm of Evan-Dar et. al. As shown by Mannor and Tsitsiklis in [The Sample Complexity of Exploration in the Multi-Armed Bandit Problem](http://www.jmlr.org/papers/volume5/mannor04b/mannor04b.pdf) it can be used to get expected $O(n)$ coin tosses when the the target bias is known as in this case.  
> **username_0**: Thanks for the reference! I'm interested in the max number of coin tosses one needs, and for this case they show an n^2 lower bound. However, the problem they consider is different from mine. They have n coins, there might only be one that is most biased, and they want to find a coin with a similar bias. In my setup I know that there are at least 0.6n coins with acceptable bias (except with prob exponentially small in n).  
> **username_0**: There's a protocol with ~ n(logn)^2 coin tosses when you consider just one coin at a time, and keep pushing down a little each time the threshold for the fraction of heads that's acceptable.  
> **username_8**: I guess expected $O(n)$ tosses is easy for our problem: Start with the first coin and do $m=\Theta(n)$ tosses for some big constant in the $\Theta(\cdot)$-notation. If that comes out heads at least $0.85m$ times, return it. Otherwise continue to the next coin. The correctness probability is $1-\exp(-n)$ and by the input coins being 0.9 bias independently with probability $2/3$, the probability of reaching the $i$'th coin is less than $(1/2)^i$ and thus the expected number of tosses is $\sum_{i=0}^\infty m/2^i = O(m) = O(n)$.  
> **username_8**: With an $O(n \log^2 n)$-toss algorithm, I suppose there is no point in posting the proof for the $O(n \log^3 n)$ algorithm above. What are the exact details for $O(n \log^2 n)$?  
> **username_1**: @KasperGreenLarsen is the correctness probability really $1-\exp(-n)$ for this simple procedure? How would you show it?  
> **username_8**: Conceptually think of the algorithm as tossing the first $10n$ coins each $m$ times (even though it doesn't always). Say that a coin errs if it is bias <=0.8 but we has more than 0.85m heads, or if it is bias 0.9 and has less than 0.85m heads. By Chernoff bound, a coin errs with probability $\exp(-2n)$ if $m$ is some sufficiently large constant times $n$. Now by a union bound over the $10n$ first coins, one of them errs with prob. at most $10n \cdot \exp(-2n) < \exp(-1.5n)$. Now, conditioned on not err'ing on the first $10n$ coins, the algorithm only reaches the $10n+1$'st coin if there are no  
> **username_8**: 0.9 bias coins amongst the $10n$ first coins. But this happens with probability $(1/3)^{10n} < \exp(-1.5n)$. So the probability of making an error is at most $2 \exp(-1.5n) < \exp(-n)$.  

---

