Bennett Bernoulli Tail Budget
Compare rare-event probabilities with a bound that uses both variance and support.
By Riano · Published · Updated · Report a correction
Bennett Bernoulli Tail Budget
The Bennett inequality is a concentration bound for sums of independent random variables. Unlike simpler bounds like Hoeffding, which only depend on the bounded range of the variables, Bennett's inequality utilizes the variance budget. For a sum of Bernoulli random variables (a Binomial distribution), this produces a strictly tighter bound when the variance is small compared to the support limit.
Worked Example
Consider a Binomial sum with n = 20 trials, p = 0.1, and we wish to bound the probability of seeing S ≥ 3. We center the variables, finding X_i - p ≤ 1 - p = 0.9. The variance V = np(1-p) = 20(0.1)(0.9) = 1.8, and threshold t = 3 - 2 = 1.0. This produces a highly constrained variance budget. We can trace the numerical calculation step by step:
| b | 0.9 |
| V | 1.8 |
| t | 1.0 |
| h(u) | 0.1082 |
| Bound | 0.786 |
b = 0.9 V = 1.8 t = 1.0 h(u) = (1+u)log(1+u) - u, with u = bt/V = 0.9(1)/1.8 = 0.5 h(0.5) ≈ 0.1082 Bound = exp(-V/b^2 * h(bt/V)) = exp(-1.8/0.81 * 0.1082) ≈ 0.786
The exact tail probability is approximately 0.323.
Experiment
In the interactive module, you can select the total Trials, the Success probability, and the Tail threshold. The visualizer calculates the exact upper tail, the variance budget, the centered threshold t = k - np, and applies Bennett's upper bound formula. You will see on the chart how the Bennett bound is influenced by the limited variance budget, keeping probabilities significantly lower than bounds that ignore variance. To use the module:
- Change the Trials and Success probability controls to alter the binomial distribution.
- Adjust the Tail threshold to observe how the exact upper tail probability compares to the Bennett bound on the visualization.
Limitations
The Bennett bound is valid for independent random variables with an explicit upper bound on the maximum deviation, but it often does not capture the true binomial dropoff for extreme k as tightly as the full Chernoff bound. In particular, for k > n, the exact probability is strictly 0, but the non-degenerate Bennett formula remains positive and approaches 0 asynchronously. For non-positive deviations (t ≤ 0), we revert to a trivial bound of 1.
References
For further details on concentration inequalities, variance budgets, and the derivation of Bennett's inequality:
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Bennett Bernoulli Tail Budget module.
Try Bennett Bernoulli Tail Budget on Riano →