Sharp and Simple Bounds for the raw Moments of the Binomial and Poisson\n Distributions

Thomas D. AhlearXiv 2021 · DOI · arXiv

This paper, authored by Thomas D. Ahle, provides a significant refinement to a fundamental problem in probability theory: finding tight upper bounds for the raw moments of common distributions like the Binomial and Poisson.

TL;DR

The paper introduces a new, "sharp and simple" upper bound for the $k$-th moments of sub-Poissonian random variables. By utilizing properties of the Lambert-W function, the author improves upon previous bounds by an exponential factor in $k$, providing a formula that is both more accurate and easier to apply in theoretical computer science and statistics.

What Problem Does This Paper Address?

In fields like randomized algorithms and sample-efficient statistics, researchers often need to bound the "raw moments" of a random variable—essentially, the expected value of the variable raised to the power of $k$ ($E[X^k]$). For the Binomial and Poisson distributions, these moments are well-studied but surprisingly difficult to bound tightly and simply.

Existing bounds, such as the Rosenthal bound or those proposed by Latala and Pinelis, often include a constant factor $C^k$. While mathematically sound, this factor grows exponentially with $k$, making the bounds "loose" for many practical applications. The challenge addressed here is to find a uniform bound that remains tight even when $k$ is small relative to the mean ($\mu$), effectively removing that exponential overhead.

Methods

The author focuses on sub-Poissonian random variables—those whose moment-generating function (MGF) is bounded by that of a Poisson distribution. This class includes the Poisson distribution itself, the Binomial distribution, and sums of independent Bernoulli trials (even with different probabilities).

The core of the proof involves:

  1. Moment-Generating Functions: Starting with the standard inequality $E[X^k] \le m(t) (k/et)^k$, where $m(t)$ is the MGF.
  2. Lambert-W Function: The author identifies that the "optimal" value for $t$ in this inequality is related to the Lambert-W function (the inverse of $f(w) = we^w$).
  3. New Inequalities: The paper proves a new lemma regarding the Lambert-W function to simplify the resulting expression into a manageable algebraic form.
  4. Free Parameters: By introducing a free parameter $\alpha$, the author creates a family of bounds, allowing for specific corollaries that are optimized for different ranges of $k$ and $\mu$.

Datasets

Not discussed in the paper. This is a theoretical mathematical work; the results are proven analytically rather than through empirical testing on datasets.

Key Insights and Ideas

  • Exponential Improvement: The most significant insight is that the $C^k$ factor in previous literature was unnecessary. The new bound replaces this with a factor that approaches $1 + o(1)$ when $k$ is small relative to the square root of the mean ($k = o(\sqrt{\mu})$).
  • The "Sub-Poissonian" Umbrella: The paper elegantly shows that these bounds apply to any sum of independent variables bounded in $[0, 1]$. This makes the result highly applicable to the analysis of "Chernoff-style" concentrations.
  • Simplicity vs. Sharpness: While the "sharpest" version of the bound involves the Lambert-W function, the author provides a very simple corollary: $E[(X/\mu)^k] \le \exp(k^2/(2\mu))$. This is remarkably easy to use in a quick "back-of-the-envelope" calculation while remaining much tighter than previous general-purpose bounds.
  • Lower Bound Matching: The author demonstrates that the new upper bound matches the asymptotic behavior of the lower bound for small $k$, proving that the result is nearly as tight as mathematically possible.

Key Results

The primary result is the inequality: $$E[(X/\mu)^k] \le \left( \frac{k/\mu}{\log(1+k/\mu)} \right)^k$$ From this, the author derives several useful corollaries, including:

  • The Quadratic Bound: $E[(X/\mu)^k] \le \exp\left(\frac{k^2}{2\mu}\right)$, which is tight for small $k^2/\mu$.
  • Large $k$ Asymptotics: For large $k/\mu$, the bound matches the known behavior of Bell numbers, which describe the moments of the Poisson distribution.

Qualitatively, this work bridges the gap between complex, exact expressions (like those involving Stirling numbers) and loose, general-purpose bounds, providing a "middle ground" that is both mathematically rigorous and practically useful.

Limitations and Future Work

  • Non-Sub-Poissonian Distributions: The current bounds do not apply to "heavy-tailed" distributions. The author notes that the geometric distribution, for example, is not sub-Poissonian, though they suggest that similar MGF-based techniques might be adapted for it.
  • Large $k$ Gap: For very large $k$ relative to $\mu$, the author notes a potential gap of a factor of $e^{-k}$ compared to certain lower bounds. They conjecture a tighter bound involving Bell numbers that could potentially close this gap.
  • Conjecture 1: The paper concludes with a conjecture regarding a matching upper bound in terms of Bell numbers for all $k > 0$ and $\mu \ge 1$, which remains an open problem for future researchers to prove.

Summary updated

Abstract

We prove the inequality $E[(X/\\mu)^k]\n \\le\n (\\frac{k/\\mu}{\\log(k/\\mu+1)})^k\n \\le\n \\exp(k^2/(2\\mu))$ for sub-Poissonian random variables, such as Binomially or\nPoisson distributed random variables with mean $\\mu$. The asymptotics\n$1+O(k^2/\\mu)$ can be shown to be tight for small $k$.\n This improves over previous uniform bounds for the raw moments of those\ndistributions by a factor exponential in $k$.\n
BibTeX
@misc{ahle2021sharp,
  author = {Thomas D. Ahle},
  title = {{Sharp and Simple Bounds for the raw Moments of the Binomial and Poisson\textbackslash\{\}n Distributions}},
  year = {2021},
  eprint = {2103.17027},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2103.17027},
}
Figure