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?
Finding a biased coin using a few coin tosses
ds.algorithms;pr.probability