Bounded randomness concentrates exponentially fast. For independent variables in [0,1], the sample mean sits within t of its expectation except with probability at most 2·exp(−2·m·t²) — a tail that shrinks like a Gaussian, with no assumption beyond boundedness. This engine simulates the mean over fixed-seed samples and checks the empirical exceedance against the closed-form bound, live.
Let X₁,…,Xₘ be independent, each in [0,1], with mean μ = E[X]. Write the sample mean X̄ = (1/m)ΣXᵢ.
The proof: bound the moment generating function of a bounded centered variable (Hoeffding’s lemma, E[e^{sY}] ≤ e^{s²/8} for Y in a unit interval), multiply over the m independent terms, then optimise the exponent with a Chernoff argument. The only input is the range width — not the mean, not the variance, not the shape.
This is the-law-of-large-numbers handed an exponential rate. LLN says X̄ → μ; Hoeffding says how fast — the failure probability decays like e^(−2mt²), so accuracy t needs only m ≈ ln(1/δ)/(2t²) samples.
It is the concentration engine sitting inside the-uniform-convergence, the-pac-learning, and every generalization bound: replace “one mean” with “the worst mean over a hypothesis class” via a union bound, and this inequality is what makes the empirical risk track the true risk.
Live re-run of selfcheck() — exact-decay identity, the two-sided constant, Hoeffding-beats-Chebyshev, Monte-Carlo exceedance ≤ bound, and the planted-void probe. Green only if every assertion holds right now.
Trip the tamper in window 6 and this flips red on the next check.
Fixed-seed draws of m independent Bernoulli(1/2) variables (the maximal-variance case in [0,1], μ = 1/2). Deterministic PRNG (mulberry32), so the whole panel is reproducible bit-for-bit.
Distribution of the empirical mean X̄. Shaded tails are the region |X̄ − μ| ≥ t; the dashed line is the empirical exceedance mass, the solid marker is the Hoeffding bound 2·exp(−2mt²).
| t | emp. P(|X̄−μ|≥t) | Hoeffding | Chebyshev | ≤? |
|---|
Rows are m as set above; the final row is the extreme two-point witness (m=1, t=1/2) the tamper targets.
—
wall “Give me heavy tails and the exponential rate is a lie.”
True — and honest. The bound holds only for variables that stay inside a bounded range. Unbounded or fat-tailed data (Cauchy, unclipped rewards, a single outlier able to move the mean) breaks it: the MGF is infinite and Hoeffding’s lemma does not apply. The [0,1] hypothesis is load-bearing, not decorative.
amber The independence assumption is also assumed here; Hoeffding’s paper extends it to sampling without replacement and U-statistics, but arbitrary dependence is out of scope for this engine.
“The bound needs the variance, like Chebyshev.”
→ No. It needs only the range. That is why it beats Chebyshev’s 1/(4mt²) for bounded data — polynomial decay replaced by exponential.
“exp(−m·t²) is fine — the extra 2 in the exponent is cosmetic.”
→ The factor 2 (from the 1/8 sub-Gaussian variance proxy of a unit interval) is exactly what makes it a valid upper bound. Drop it and you claim a bound tighter than the truth — see window 6.
“Two-sided and one-sided are the same.”
→ One-sided is exp(−2mt²); the two-sided constant is 2, from the union of the upper and lower tails.
The disclosed planted void. Pressing tamper drops the 2 in the exponent — the engine then claims exp(−m·t²), tighter than the true bound. At the extreme two-point witness the empirical exceedance (=1) now exceeds the claimed bound (≈0.779), so the exceedance—≤—bound check breaks and the witness in 7 catches it.
state: honest — exp uses the factor 2.