  We give the proof of a tight lower bound on the probability that a binomial
random variable exceeds its expected value. The inequality plays an important
role in a variety of contexts, including the analysis of relative deviation
bounds in learning theory and generalization bounds for unbounded loss
functions.
