An Elementary Analysis of the Probability That a Binomial Random Variable Exceeds Its Expectation

Abstract

We give an elementary proof of the fact that a binomial random variable $X$ with parameters $n$ and $0.29/n\le p<1$ with probability at least $1/4$ strictly exceeds its expectation. We also show that for $1/n\le p<1-1/n$, $X$ exceeds its expectation by more than one with probability at least $0.0370$. Both probabilities approach $1/2$ when $np$ and $n(1-p)$ tend to infinity.

v2: Minor change in the presentation of previous works (took into account the new version of Pel[16]). v3: Minor change in the presentation of previous works (the proof of Lemma 6.4 in [RT11] gives a significantly stronger result than what is stated in the Lemma itself). v4: Minor changes (typos, mentioned the work of Slud)

References in corpus (1)

• The (1+$\lambda$) Evolutionary Algorithm with Self-Adjusting Mutation Rate

Cited by in corpus (11)

• Probabilistic Tools for the Analysis of Randomized Optimization Heuristics
• The (1+$\lambda$) Evolutionary Algorithm with Self-Adjusting Mutation Rate
• Working Principles of Binary Differential Evolution
• Multiplicative Up-Drift
• A Rigorous Runtime Analysis of the $(1+(\lambda ,\lambda ))$ GA on Jump Functions
• Improved quantum data analysis
• Lower bounds on binomial and Poisson tails: an approach via tail conditional expectations
• Runtime Analysis for Self-adaptive Mutation Rates
• A Tight Runtime Analysis for the $(\mu +\lambda )$ EA
• Improving Generalization Bounds for VC Classes Using the Hypergeometric Tail Inversion
• On the Chvatal-Janson conjecture