Moments of sums of independent coordinates #
For S = ∑ i, f i (ω i) with independent uniform coordinates ω i (the setting of
Dynamics.Concentration):
avg_cauchy: Cauchy-Schwarz for uniform averages (Mathlib'sFinset.expect_mul_sq_le_sq_mul_sqthroughavg_eq_expect);- Paley-Zygmund: one-sided,
P(X > θ 𝔼X) ≥ (1 - θ)² (𝔼X)² / 𝔼X²for𝔼X ≥ 0and0 ≤ θ ≤ 1(avg_pz_one_sided, in multiplied form), and two-sided forZ²(avg_pz); - centered summands bounded by
1: the second moment is the sum of the variancesσ²(avg_sum_sq), the fourth moment is at mostσ² + 3σ⁴(avg_sum_fourth_le), and the two-sided Paley-Zygmund inequality turns them into the anti-concentration boundP(σ² ≤ 4 S²) ≥ 9/64wheneverσ² ≥ 1(avg_pz_sum, andavg_pz_zero_onefor centered{0,1}-valued coordinates); {0,1}-valued summands: mean in[0, 1], variancep (1 - p)(variance_of_zero_one), and Hoeffding's exponential-moment bound𝔼 e^{tS} ≤ e^{t 𝔼S + n t²/8}for every realt(avg_exp_sum_le);- pairwise independent
{0,1}-valued summands:𝔼S² ≤ μ + μ²withμ = 𝔼S, i.e. the variance of the sum is at most its mean (avg_sq_sum_le_of_pairwise).
The lemmas on independent coordinates were proved, identically, in median/ (symmetry breaking
of the binary median dynamics) and plurality/ (the √n jump of binary 3-Majority near balance,
and, in the library ThreeMajority, symmetry breaking of 3-Majority with many colours); the
pairwise bound is the second-moment step of the PULL analysis in epidemics/ (library
RumorSpread, RumorPush.pull_avg_new_sq_le), which then applies the one-sided Paley-Zygmund
bound (RumorPush.pull_prob_goodRound).
Averages on product spaces #
Second and fourth moments, Paley-Zygmund #
Paley-Zygmund, two-sided. If 𝔼Z² = s > 0 and 𝔼Z⁴ ≤ 4 s², then s ≤ 4 Z²
with probability at least 9/64 (avg_pz_one_sided for Z² at θ = 1/4).
Anti-concentration of a sum. If independent centered coordinates are bounded by 1 and
their variances add up to σ² ≥ 1, then the sum S satisfies σ² ≤ 4 S² with probability at
least 9/64 (Paley-Zygmund, with 𝔼S² = σ² and 𝔼S⁴ ≤ σ² + 3σ⁴ ≤ 4σ⁴).
{0,1}-valued coordinates #
Anti-concentration for {0,1}-valued coordinates. If the variances of independent
{0,1}-valued coordinates add up to σ² ≥ 1, then the centered sum S = ∑ᵢ (Yᵢ - 𝔼Yᵢ)
satisfies σ² ≤ 4 S² with probability at least 9/64.
Hoeffding's exponential-moment bound for independent {0,1}-valued coordinates: for
every real t, 𝔼 exp (t ∑ᵢ Yᵢ) ≤ exp (t ∑ᵢ 𝔼Yᵢ + n t²/8) (Hoeffding's lemma
one_sub_add_mul_exp_le for each coordinate).
Pairwise independent indicators #
Second moment of a sum of pairwise independent indicators: if the {0,1}-valued
X i (i ∈ s) are pairwise uncorrelated, then 𝔼(∑ᵢ Xᵢ)² ≤ μ + μ² with μ = ∑ᵢ 𝔼Xᵢ, i.e. the
variance of the sum is at most its mean.