Tight Lower Bound on the Probability of a Binomial Exceeding its Expectation
Not on the map. Why?
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.
Key facts. Cited by 7 papers in the map (data through 14 Oct 2026). First posted on arXiv 6 Jun 2013.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 2; 2022: 0; 2023: 3; 2024: 1; 2025: 1.
7 papers.
- 2021ktexttt-experts -- Online Policies and Fundamental Limitscited by 8
- 2024On the design-dependent suboptimality of the Lassocited by 3
- 2023Uniform Risk Bounds for Learning with Dependent Data Sequencescited by 1
- 2021Improving Generalization Bounds for VC Classes Using the Hypergeometric Tail Inversioncited by 0
- 2023Rule Enforcing Through Orderingcited by 0
- 2023Asymptotically Optimal Pure Exploration for Infinite-Armed Banditscited by 0
- 2025On the Optimality of the Median-of-Means Estimator under Adversarial Contaminationcited by 0
- 2025On the Optimality of the Median-of-Means Estimator under Adversarial Contamination9 Oct 2025
- 2024On the design-dependent suboptimality of the Lasso1 Feb 2024
- 2023Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits3 Jun 2023
- 2023Rule Enforcing Through Ordering31 Mar 2023
- 2023Uniform Risk Bounds for Learning with Dependent Data Sequences21 Mar 2023
- 2021Improving Generalization Bounds for VC Classes Using the Hypergeometric Tail Inversion29 Oct 2021
- 2021ktexttt-experts -- Online Policies and Fundamental Limits15 Oct 2021