Handy formulas for binomial moments

Maciej SkorskiModern Stochastics: Theory and Applications 2024 · OpenReview

TL;DR

This paper introduces a new, simpler, and more numerically stable way to calculate higher-order moments of the binomial distribution. By expressing these moments as polynomials of the variance (instead of the success probability), the authors provide more practical formulas and algorithms, along with a Python implementation, which are useful for theoretical analysis and obtaining sharper bounds.

What Problem Does This Paper Address?

The binomial distribution is fundamental in probability and statistics, yet its higher-order moments (beyond the variance) are surprisingly complex and difficult to work with. Existing formulas are often not general enough, lack a clear structure, or suffer from numerical instability, making them impractical for applications like deriving theoretical guarantees on probability tails. This paper aims to rectify this by providing more "handy" and computationally friendly formulas for these moments.

Methods

The authors employ a novel approach that combines a combinatorial argument with algebraic simplifications rooted in symmetrization theory. Instead of expressing moments as polynomials in the success probability 'p', they cleverly reformulate them as polynomials in the variance, $\sigma^2 = p(1-p)$. This leads to simpler expressions, especially for central moments. They also present two algorithms for deriving these variance-based formulas, one leveraging the fundamental theorem of symmetric polynomials and another using Gröbner bases and elimination theory. Working implementations in Python's SymPy library are provided.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Variance is King: The most significant insight is that expressing binomial moments in terms of the variance ($\sigma^2$) rather than the success probability ($p$) leads to substantially simpler and more structured formulas.
  • Symmetry Unlocks Simplicity: Exploiting the inherent symmetry of the binomial distribution is key to deriving these elegant variance-based formulas.
  • Positive Polynomials for Stability: The new formulas for central moments consist of sums of positive terms, making them more numerically stable and easier to analyze compared to previous alternating sum formulas.
  • Sharper Bounds: The new formulas enable the derivation of asymptotically sharp bounds for central binomial moments, improving upon existing results and offering better theoretical guarantees.

Key Results

  • Novel Formulas: The paper presents new, explicit formulas for both raw and central binomial moments, expressed as polynomials in the variance $\sigma^2$.
  • Algorithmic Derivation: Two algorithms are provided to compute these variance-based formulas, implemented in Python using SymPy.
  • Asymptotically Sharp Bounds: The authors derive improved upper and lower bounds for normalized central binomial moments, showing they grow as $\Theta(n\sigma^2)^{d/2}$ under certain conditions, matching the behavior predicted by the Central Limit Theorem.
  • Numerical Stability: The proposed formulas are noted to be superior in their numerical properties compared to prior works.

Limitations and Future Work

The paper focuses on deriving exact formulas and their applications to asymptotic bounds. While algorithms and implementations are provided, further exploration of their computational efficiency for extremely high orders of moments could be a future direction. The authors also mention that their approach can be extended to other discrete distributions, suggesting a broader applicability of their methods.

Summary updated

Abstract

Publisher: VTeX - Solutions for Science Publishing, Journal: Modern Stochastics - Theory and Applications, Title: Handy formulas for binomial moments, Authors: Maciej Skorski , Abstract: Despite the relevance of the binomial distribution for probability theory and applied statistical inference, its higher-order moments are poorly understood. The existing formulas are either not general enough, or not structured and simplified enough for intended applications. This paper introduces novel formulas for binomial moments in the form of polynomials in the variance rather than in the success probability. The obtained formulas are arguably better structured, simpler and superior in their numerical properties compared to prior works. In addition, the paper presents algorithms to derive these formulas along with working implementation in Python’s symbolic algebra package. The novel approach is a combinatorial argument coupled with clever algebraic simplifications which rely on symmetrization theory. As an interesting byproduct asymptotically sharp estimates for central binomial moments are established, improving upon previously known partial results.
BibTeX
@inproceedings{skorski2024handy,
  author = {Maciej Skorski},
  title = {{Handy formulas for binomial moments}},
  booktitle = {Modern Stochastics: Theory and Applications},
  year = {2024},
  url = {https://openreview.net/forum?id=QdSlOED7OZ},
}
Figure