Finding a biased coin using a few coin tosses 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?
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.