Amplification for Randomized Algorithms
Use the median instead of the mean. The median can only be bad if more than half the samples are bad.

The problem with the mean is that the mean could be bad from a lot of the samples being a little bit bad, or from a few of the samples being really bad. However, in general, you don't know the probabilities of different degrees of sample badness; just the probability of bad-versus-good.