A Sharp Uniform Bound for the Distribution of Sums of Bernoulli Trials

Jean-Bernard Baillon, Roberto Cominetti, José VaismanComb. Probab. Comput 2016 · OpenReview

TL;DR

This paper establishes a tight, universal upper bound on the probability of a specific outcome for sums of independent Bernoulli trials. This bound, which is shown to be asymptotically achieved by Poisson distributions, has implications for understanding the behavior of sums of random variables and has direct applications in analyzing the convergence rates of iterative algorithms.

What Problem Does This Paper Address?

The paper tackles the problem of bounding the probability mass function of a sum of independent Bernoulli random variables, $S_n = X_1 + \dots + X_n$, where each $X_i$ is a Bernoulli trial with a potentially different success probability $p_i$. While the central limit theorem describes the asymptotic behavior of such sums, it doesn't provide tight bounds on the probability of specific outcomes, especially for finite $n$. Existing bounds, like those from large deviation theory, are effective for tail probabilities (far from the mean) but less precise near the mean. The authors aim to find a sharp, uniform bound that holds for all possible values of $n$, $j$, and $p_i$, and to identify the conditions under which this bound is met.

Methods

The core of the paper is the derivation of a uniform bound using the generating function of $S_n$. By analyzing the integral of the absolute value of the characteristic function of $S_n$ over the unit circle, they establish the inequality:

$\sigma_n P(S_n = j) \le \eta$

where $\sigma_n$ is the standard deviation of $S_n$ and $\eta$ is a universal constant. A significant contribution is the precise computation of this constant $\eta$ as:

$\eta = \max_{\lambda \ge 0} \sqrt{2\lambda} P(N_\lambda = N'_\lambda)$

where $N_\lambda$ and $N'_\lambda$ are independent Poisson random variables with parameter $\lambda$. This constant is numerically found to be approximately $0.4688$. The paper then delves into proving the sharpness of this bound by constructing specific Bernoulli trial configurations that approach $\eta$. They also explore how this bound extends to limits of sums and differences of Bernoulli variables, including Poisson distributions, and investigate the behavior of the bound for fixed $n$ and $j$.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • A Universal Bound: The paper provides a single, overarching bound for the probability mass function of sums of Bernoulli trials, regardless of the number of trials or individual probabilities. This is a powerful generalization.
  • The Role of Poisson Distributions: The authors demonstrate that Poisson distributions are the "worst-case" scenario, meaning they are the distributions that achieve the sharpest bound $\eta$. This is a crucial insight into the behavior of sums of Bernoulli variables.
  • Sharpness is Key: The paper doesn't just provide a bound; it proves its sharpness. This means the bound is as tight as possible, and no better universal bound can exist.
  • Connection to Iterative Methods: A key application is shown in estimating the rate of convergence for Mann's fixed-point iterations, demonstrating the practical relevance of these theoretical bounds.
  • Beyond Simple Binomials: The bound holds not only for sums of Bernoulli trials but also for limits of sums and differences, encompassing a broader class of random variables.

Key Results

  • The Main Bound: $\sigma_n P(S_n = j) \le \eta$, where $\eta \approx 0.4688$.
  • Optimal Constant: $\eta = \max_{\lambda \ge 0} \sqrt{2\lambda} P(N_\lambda = N'_\lambda) \approx 0.4688$.
  • Sharpness Demonstrated: The bound is shown to be asymptotically attained by specific configurations of Bernoulli trials, particularly those that converge to Poisson distributions.
  • Extension to Limits: The bound holds for limits of sums and differences of Bernoulli variables, including Poisson distributions.
  • Application to Fixed-Point Iterations: The paper provides a bound on the rate of convergence for Mann's fixed-point iterations, with a constant related to $\eta$. For affine maps, they show the convergence constant is $2\eta \approx 0.9376$.

Limitations and Future Work

  • Uniformity vs. Specificity: While the bound is uniform, the paper notes that for fixed $n$ and $j$, the optimal probabilities $p_i$ that achieve the bound can be quite specific. The paper explores this in detail, showing that for $n=2a$ and $j=a$, the optimal configuration involves half the $p_i$ being $\alpha$ and the other half $1-\alpha$.
  • Generalization: The paper raises the question of whether similar uniform bounds hold for more general distributions beyond those derived from Bernoulli sums. This remains an open area for future research.
  • Conjectures: The authors propose conjectures about the structure of optimal solutions for fixed $n$ and $j$, suggesting that the maximizers of $V_n^j$ (a related quantity) take on at most two distinct values. This is explored further, with a conjecture that these values are $\alpha$ and $\beta$ such that $n-j$ components are $\alpha$ and $j$ are $\beta$.

Summary updated

Abstract

In this note we establish a uniform bound for the distribution of a sum Sn=X1+···+Xn of independent non-homogeneous Bernoulli trials. Specifically, we prove that σn(Sn = j) ≤ η, where σn denotes the standard deviation of Sn, and η is a universal constant. We compute the best possible constant η ~ 0.4688 and we show that the bound also holds for limits of sums and differences of Bernoullis, including the Poisson laws which constitute the worst case and attain the bound. We also investigate the optimal bounds for n and j fixed. An application to estimate the rate of convergence of Mann's fixed-point iterations is presented.
BibTeX
@inproceedings{baillon2016sharp,
  author = {Jean-Bernard Baillon and Roberto Cominetti and José Vaisman},
  title = {{A Sharp Uniform Bound for the Distribution of Sums of Bernoulli Trials}},
  booktitle = {Comb. Probab. Comput},
  year = {2016},
  url = {https://openreview.net/forum?id=2quQqOMnyl},
}

Loading related content...

Figure