29

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?

Dana Moshkovitz
  • 10,979
  • 1
  • 50
  • 77
  • 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? – usul Jun 23 '15 at 01:03
  • @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 Jun 23 '15 at 01:20
  • @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 Jun 23 '15 at 01:26
  • @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 Jun 23 '15 at 01:47
  • 1
    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 Jun 23 '15 at 07:31
  • 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 Jun 23 '15 at 09:04
  • @Aryeh: you'll find one with high (constant) probability -- but you need to find one with probability $1-\exp(-n)$. – Clement C. Jun 23 '15 at 12:43
  • @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 Jun 23 '15 at 12:56
  • One possible way (suggested by a friend) is to see if the techniques from this paper (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. Jun 23 '15 at 13:00
  • 1
    Would $O(n\log n)$ be okay? Do you know a solution with $o(n^2)$ tosses? – Robin Kothari Jun 23 '15 at 13:55
  • 4
    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 Jun 23 '15 at 14:45
  • @DanaMoshkovitz: seconding Robin's question, the goal is really linear here -- not, say, $\tilde{O}(n)$? – Clement C. Jun 23 '15 at 14:48
  • 1
    It's quite possible that O(nlogn) flips are necessary and sufficient - but we don't have a proof for that yet. – Dana Moshkovitz Jun 23 '15 at 14:50
  • 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. Jun 23 '15 at 14:59
  • Consider asking this on Cross Validated: http://stats.stackexchange.com/ . If you post, please cross-link both ways. – Zsbán Ambrus Jun 24 '15 at 14:19
  • @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 Jun 26 '15 at 08:34

1 Answers1

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.

Kasper Green Larsen
  • 101
  • 3
  • 2
    (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 Jun 24 '15 at 14:14
  • 3
    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 Jun 24 '15 at 16:17
  • 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 Jun 24 '15 at 18:22
  • 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 Jun 24 '15 at 18:23
  • 3
    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. – Kristoffer Arnsfelt Hansen Jun 24 '15 at 20:53
  • 2
    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 Jun 24 '15 at 23:41
  • 1
    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 Jun 25 '15 at 00:53
  • 3
    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 Jun 25 '15 at 05:21
  • 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 Jun 25 '15 at 05:22
  • @KasperGreenLarsen is the correctness probability really $1-\exp(-n)$ for this simple procedure? How would you show it? – usul Jun 25 '15 at 14:42
  • 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 Jun 25 '15 at 15:48
  • 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 Jun 25 '15 at 15:50