Hoeffding and Bernstein bounds on finite product spaces #
Concentration for a sum ∑ i, Y i (ω i) of independent coordinates, where
ω : Fin n → γ is drawn uniformly (so the coordinates ω i are independent
uniform draws from the finite type γ). As everywhere in this library the
probability of an event is the average of its indicator, and independence is
avg_prod_pi; no measure theory is used.
one_sub_add_mul_exp_le: Hoeffding's lemma for a Bernoulli variable,1 - p + p eᵗ ≤ exp(p t + t²/8), proved by two monotonicity arguments.avg_hoeffding: Hoeffding's inequality for{0,1}-valued coordinates,P(X ≥ 𝔼X + λ) ≤ exp(-2λ²/n).exp_le_bernstein: the scalar inequality behind Bernstein's bound,e^y ≤ 1 + y + y² / (2(1 - u/3))fory ≤ u < 3, from the monotonicity of(1 + y + y²/(2(1 - y/3))) e^{-y}on either side of0.avg_bernstein: Bernstein's inequality,P(X ≥ 𝔼X + λ) ≤ exp(-λ² / (2σ²(1 + bλ/(3σ²))))whenever every coordinate satisfiesYᵢ - 𝔼Yᵢ ≤ bandσ²bounds the variance ofX.avg_hoeffding_lower: Hoeffding's lower tail, andvariance_le_avg_of_zero_one: the variance of a{0,1}coordinate is at most its mean.avg_bernstein_lower: Bernstein's lower tail;avg_bernstein_of_zero_oneandavg_bernstein_lower_of_zero_one: for{0,1}coordinates with meanμ, each tail beyond√(3ℓ(μ + 2ℓ))has probability at moste^{-ℓ}.
The multiplicative Chernoff bounds are in Dynamics.Chernoff.
Scalar inequalities #
Tail bounds for sums of independent coordinates #
The variance of a coordinate, 𝔼[(Y - 𝔼Y)²].
Equations
- Dynamics.variance f = Dynamics.avg fun (y : γ) => (f y - Dynamics.avg f) ^ 2
Instances For
Bernstein's inequality (Dubhashi–Panconesi): if every coordinate
satisfies Yᵢ - 𝔼Yᵢ ≤ b and σ² is at least the variance of
X = ∑ᵢ Yᵢ, then P(X ≥ 𝔼X + λ) ≤ exp(-λ² / (2σ²(1 + bλ/(3σ²)))).
Lower tails and the variance of a {0,1} coordinate #
Markov's inequality applied to exp (t (X - k)) with t ≤ 0: the lower-tail companion
of avg_tail_le_of_mgf.
Hoeffding's inequality, lower tail, for independent {0,1}-valued coordinates:
P(X ≤ 𝔼X - λ) ≤ exp(-2λ²/n). Replaces Median.avg_hoeffding_lower.
Bernstein's lower tail and the two-sided bound for {0,1} coordinates #
Bernstein's inequality, lower tail: if every coordinate satisfies 𝔼Yᵢ - Yᵢ ≤ b and
σ² is at least the variance of X = ∑ᵢ Yᵢ, then
P(X ≤ 𝔼X - λ) ≤ exp(-λ² / (2σ²(1 + bλ/(3σ²)))) (avg_bernstein applied to -Y).
Bernstein's inequality for {0,1} coordinates, upper tail: with mean μ = 𝔼X and
ℓ > 0, P(X ≥ μ + √(3ℓ(μ + 2ℓ))) ≤ e^{-ℓ} (avg_bernstein with b = 1 and variance bound
μ + 2ℓ). The deviation is ≈ √(3ℓμ) for large means.
Bernstein's inequality for {0,1} coordinates, lower tail: with mean μ = 𝔼X and
ℓ > 0, P(X ≤ μ - √(3ℓ(μ + 2ℓ))) ≤ e^{-ℓ}.