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

Benjamin Doerr

TL;DR

This paper provides elementary proofs for a fundamental property of binomial random variables: the probability that such a variable exceeds its expected value. The authors derive new, tighter bounds and demonstrate that these bounds can be achieved with surprisingly simple mathematical tools, offering a more accessible understanding of this important statistical phenomenon.

What Problem Does This Paper Address?

The expectation of a binomial random variable, $E[X] = np$, is a central parameter. Intuitively, one might expect the variable $X$ to often be close to its expectation. However, rigorously proving that $X$ exceeds $E[X]$ with a non-trivial probability, especially for general parameters $n$ and $p$, has been surprisingly challenging. While some results existed for specific ranges of $p$, a general, elementary proof was lacking. This paper aims to fill this gap by providing accessible proofs and improved bounds for the probability $P(X > E[X])$. This is particularly relevant in fields like machine learning and randomized algorithms where understanding the tail behavior of binomial distributions is crucial.

Methods

The authors leverage a combination of elementary techniques, avoiding complex approximations like the Camp-Paulson normal approximation used in prior work. Key methods include:

  • Stochastic Domination: Lemma 7 establishes a crucial stochastic domination property: if $p < q$, then $Bin(n, p)$ is "smaller" than $Bin(n, q)$ in a specific probabilistic sense. This allows transferring bounds from a simpler distribution to a more complex one.
  • Combinatorial Arguments and Inequalities: The proofs rely on careful manipulation of binomial coefficients and inequalities, often derived from basic calculus and series expansions (e.g., for logarithms).
  • Stirling's Approximation: Theorem 4 and Corollary 5 provide estimates for binomial coefficients, which are then used to bound probabilities of specific outcomes.
  • Case Analysis: For certain ranges of parameters, detailed case distinctions are employed to prove the bounds, especially for "small" values of $n$ and $k$.

What's novel is the elementary nature of these proofs. They avoid advanced statistical machinery, making the results more broadly understandable and applicable.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis of a probability distribution, not empirical evaluation on datasets.

Key Insights and Ideas

  • Elementary Proofs are Possible: The most significant insight is that fundamental results about binomial tail probabilities can be proven using relatively simple mathematical tools, contrary to previous assumptions that required more advanced techniques.
  • Stochastic Domination is Powerful: Lemma 7's stochastic domination property is a cornerstone, enabling the transfer of bounds and simplifying the analysis.
  • Tight Bounds from Simple Tools: The paper demonstrates that even basic inequalities and combinatorial arguments can yield tight and useful lower bounds for $P(X > E[X])$.
  • Asymptotic Behavior: The derived bounds show that as $np$ and $n(1-p)$ tend to infinity, the probability $P(X > E[X])$ approaches $1/2$, which aligns with intuition.

Key Results

The paper establishes several key quantitative results:

  • Theorem 10: For $p$ in a certain range related to $\ln(1)/n$, $P(X > E[X]) \ge 1/2$. This is a significant improvement over previous bounds for a broad range of parameters.
  • Theorem 12(c): For $n \ge 3$ and $1/n < p < 1 - 1/n$, the probability that $X$ exceeds its expectation by more than one is at least $0.0370$. This provides a non-trivial lower bound for a stronger condition.
  • Improved Bounds: The paper presents new lower bounds for $P(X > E[X])$ (e.g., Lemma 8 and Theorem 10) and $P(X > E[X] + 1)$ (Theorem 12) that are often superior to existing ones, especially for certain parameter ranges.

Limitations and Future Work

  • "Small Cases" Analysis: While the proofs are elementary, some parts, particularly for proving Theorem 10, involve extensive case analysis for small values of $n$ and $k$. The authors acknowledge that these could be checked computationally but prefer a "human-readable proof."
  • Comparability of Bounds: The paper notes that their bounds are not always directly comparable to previous ones (e.g., Figure 1 and 3 comparisons). While their bounds are often superior or more uniform, specific scenarios might favor older results.
  • Extension to Smaller $p$: The authors suggest that their elementary result (Lemma 8) could be extended to smaller values of $p$ by possibly lowering the constant, as long as $p$ is at least some $\epsilon > 0$.
  • Generalization of "More Than One": Theorem 12 provides a bound for exceeding the expectation by more than one. Future work could explore bounds for exceeding the expectation by $m$ for general $m$.

Summary updated

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.
BibTeX
@misc{doerr2017elementary,
  author = {Benjamin Doerr},
  title = {{An Elementary Analysis of the Probability That a Binomial Random Variable Exceeds Its Expectation}},
  year = {2017},
  eprint = {1712.00519},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1712.00519},
}

Loading related content...

Figure