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

arXiv: https://arxiv.org/abs/1306.1433 · HTML: https://mlsanity.com/paper/1306.1433/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jun 2013.

## Built on by (most cited first, 7 of 7)

- [ktexttt-experts -- Online Policies and Fundamental Limits](https://mlsanity.com/paper/2110.07881/) (2021)
- [On the design-dependent suboptimality of the Lasso](https://mlsanity.com/paper/2402.00382/) (2024)
- [Uniform Risk Bounds for Learning with Dependent Data Sequences](https://mlsanity.com/paper/2303.11650/) (2023)
- [Improving Generalization Bounds for VC Classes Using the Hypergeometric Tail Inversion](https://mlsanity.com/paper/2111.00062/) (2021)
- [Rule Enforcing Through Ordering](https://mlsanity.com/paper/2303.17971/) (2023)
- [Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits](https://mlsanity.com/paper/2306.01995/) (2023)
- [On the Optimality of the Median-of-Means Estimator under Adversarial Contamination](https://mlsanity.com/paper/2510.07867/) (2025)

## Abstract (arXiv)

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.