Chernoff Bounds

Chernoff Bounds

Mathematical Definition

Let X be the sum of n independent Bernoulli trials, all with success probability p. Then X has a binomial distribution, mean np and variance np(1 − p). The selected event is inclusive: X ≥ k includes exactly k successes.

For t > 0, exponentiation preserves the event’s order. Markov’s inequality applied to the positive random variable e^tX gives:

The value at t = 0 is the trivial bound 1 and agrees with the limit as t decreases to zero. Capping an upper bound at 1 is valid because probabilities cannot exceed 1. The slider explores selected finite tilts; the optimized answer is the analytic infimum over every nonnegative t, including limits beyond the slider.

Key Concepts

Why the logarithm helps

For 0 < p < 1 and np < k < n, write q = k/n. The logarithm of the uncapped expression is L(t) = n ln(1 − p + pe^t) − tk. This is convex in t. Setting its derivative to zero gives a positive finite minimizer:

D is the relative entropy between Bernoulli distributions, using natural logarithms. This is the optimized binomial MGF bound. Looser mean-only multiplicative bounds and Hoeffding’s inequality are related consequences; they are different expressions. The KL expression alone must not be used to claim a better upper-tail bound when k lies below the mean.

One checked example

For 20 fair trials and k = 15, the exact upper-tail numerator is C(20,15) + … + C(20,20) = 21700. Dividing by 2²⁰ gives 5425/262144, about 0.020695. Here q = 3/4 and t_* = ln 3. The optimized bound is (2/3)¹⁵2⁵ = 1048576/14348907, about 0.07308. The guarantee is larger than the actual probability. Moving the trial tilt near ln 3 tightens the selected bound; changing t does not change the underlying experiment or exact tail.

For four trials with p = 1/4 and k = 3, the exact probability is 13/256 while the optimized bound is 1/9. The interior optimum is ln 9. These examples show why a valid upper bound should be read as “at most,” rather than as an estimate of equality.

Endpoints and limiting optima

• At or below the mean: k ≤ np has optimized upper bound 1. Choosing t = 0 is a minimizer; deterministic cases can have other minimizing tilts too.
• All successes: With 0 < p < 1 and k = n > 0, B_t approaches pⁿ as t grows. The infimum equals the true all-success probability, but no finite minimizing tilt is claimed.
• Impossible events: k > n, or p = 0 with k > 0, has exact probability and optimized infimum 0. A selected finite-t expression can still be positive.
• Empty and deterministic experiments: n = 0 or p = 0 gives X = 0. At p = 1, X = n. Evaluate these cases directly so logarithms of zero do not produce a fictitious value.

Reading the explorer

The tail chart compares inclusive tails at integer thresholds from 0 to n + 1; connecting lines help reading and do not introduce fractional count events. The mass chart shows the actual PMF and colors bars belonging to X ≥ k. The threshold remains editable above the support, where the event is impossible. Its reference line is omitted if it lies beyond the displayed chart. The vertical probability axes run linearly from 0 to 1, so tiny positive values can be visually unresolved; the numeric cards use scientific notation to preserve them.

The demonstration uses integer trial counts up to 100, whole percentage probabilities and thresholds up to 101. “Exact tail” means direct evaluation of the binomial PMF with double-precision arithmetic, rather than a concentration approximation. Coefficients are constructed as integers before conversion. Blank, fractional and out-of-range model inputs hide stale results until corrected.

Historical Context

Exponential bounds are part of the development of large-deviation theory and probability inequalities. The name Chernoff bound covers a method and a family of related inequalities. Their usefulness comes from replacing a potentially long tail sum with a tractable exponential expression whose parameter can be optimized.

Real-world Applications

• Randomized algorithms: Bound unusually large counts of independent failures or collisions under an appropriate probabilistic model.
• Sampling: Quantify how unlikely a large deviation in empirical success frequency is when the independent identical-trial assumptions hold.
• Reliability: Obtain conservative tail guarantees for a bounded count model. Dependence or changing success probabilities require a separately justified inequality.

Related Concepts

• Moment Generating Functions — transform independent sums into products.
• Law of Large Numbers — describes concentration qualitatively; an exponential bound adds a finite-sample guarantee.
• Hypergeometric Distribution — models sampling without replacement, with different dependence assumptions.
• Entropy & Information Theory — Bernoulli relative entropy measures the cost of the selected deviation.

References

• UC San Diego CSE103, Chernoff Bounds, pp. 1–3 — Bernoulli MGF, optimizing the tilt and the KL form.
• Garrett Thomas, Concentration Inequalities — exponential Markov inequality and the general infimum strategy.
• Ben Lynn, The Chernoff Bound — independent Bernoulli product MGFs and related inequalities.
• SciPy, Binomial distribution — PMF, support and survival probabilities.