29
$\begingroup$

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?

Improve this question
$\endgroup$
16
  • 1
    $\begingroup$ 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? $\endgroup$
    – usul
    Jun 23 '15 at 1:03
  • 1
    $\begingroup$ 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. $\endgroup$
    – daniello
    Jun 23 '15 at 7:31
  • 1
    $\begingroup$ Would $O(n\log n)$ be okay? Do you know a solution with $o(n^2)$ tosses? $\endgroup$
    – Robin Kothari
    Jun 23 '15 at 13:55
  • 4
    $\begingroup$ 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)). $\endgroup$
    – Dana Moshkovitz
    Jun 23 '15 at 14:45
  • 1
    $\begingroup$ It's quite possible that O(nlogn) flips are necessary and sufficient - but we don't have a proof for that yet. $\endgroup$
    – Dana Moshkovitz
    Jun 23 '15 at 14:50
10
$\begingroup$

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.

Improve this answer
$\endgroup$
12
  • 2
    $\begingroup$ (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? $\endgroup$
    – Dana Moshkovitz
    Jun 24 '15 at 14:14
  • 3
    $\begingroup$ 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. $\endgroup$
    – Dana Moshkovitz
    Jun 24 '15 at 16:17
  • 3
    $\begingroup$ 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 it can be used to get expected $O(n)$ coin tosses when the the target bias is known as in this case. $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Jun 24 '15 at 20:53
  • 2
    $\begingroup$ 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). $\endgroup$
    – Dana Moshkovitz
    Jun 24 '15 at 23:41
  • 3
    $\begingroup$ 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)$. $\endgroup$
    – Kasper Green Larsen
    Jun 25 '15 at 5: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.