#### Spencer Greenberg and Mehryar Mohri

#### Tight Lower Bound on the Probability of a
Binomial Exceeding its Expectation

Abstract:

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.