Documentation

Dynamics.Moments

Moments of sums of independent coordinates #

For S = ∑ i, f i (ω i) with independent uniform coordinates ω i (the setting of Dynamics.Concentration):

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 #

theorem Dynamics.avg_cauchy {γ : Type u_1} [Fintype γ] (f g : γ → ℝ) :
(avg fun (y : γ) => f y * g y) ^ 2 ≤ (avg fun (y : γ) => f y ^ 2) * avg fun (y : γ) => g y ^ 2

Cauchy-Schwarz for uniform averages: Mathlib's Finset.expect_mul_sq_le_sq_mul_sq through avg_eq_expect.

theorem Dynamics.avg_head_tail {n : ℕ} {γ : Type u_1} [Fintype γ] (F : γ → ℝ) (G : (Fin n → γ) → ℝ) :
(avg fun (ω : Fin (n + 1) → γ) => F (ω 0) * G (Fin.tail ω)) = avg F * avg G

Independence of the head and the tail: on Fin (n + 1) → γ, a product of a function of ω 0 and a function of Fin.tail ω averages to the product of averages.

theorem Dynamics.avg_tail {n : ℕ} {γ : Type u_1} [Fintype γ] [Nonempty γ] (G : (Fin n → γ) → ℝ) :
(avg fun (ω : Fin (n + 1) → γ) => G (Fin.tail ω)) = avg G

A function of the tail alone has the same average over the longer product.

theorem Dynamics.avg_sum_coords {n : ℕ} {γ : Type u_1} [Fintype γ] [Nonempty γ] (f : Fin n → γ → ℝ) :
(avg fun (ω : Fin n → γ) => ∑ i : Fin n, f i (ω i)) = ∑ i : Fin n, avg (f i)

The mean of a sum of independent coordinates.

Second and fourth moments, Paley-Zygmund #

theorem Dynamics.avg_sum_sq {n : ℕ} {γ : Type u_1} [Fintype γ] [Nonempty γ] (f : Fin n → γ → ℝ) (hf0 : ∀ (i : Fin n), avg (f i) = 0) :
(avg fun (ω : Fin n → γ) => (∑ i : Fin n, f i (ω i)) ^ 2) = ∑ i : Fin n, avg fun (y : γ) => f i y ^ 2

Second moment of a sum of independent centered coordinates.

theorem Dynamics.avg_sum_fourth_le {n : ℕ} {γ : Type u_1} [Fintype γ] [Nonempty γ] (f : Fin n → γ → ℝ) (hf0 : ∀ (i : Fin n), avg (f i) = 0) (hfb : ∀ (i : Fin n) (y : γ), |f i y| ≤ 1) :
(avg fun (ω : Fin n → γ) => (∑ i : Fin n, f i (ω i)) ^ 4) ≤ (∑ i : Fin n, avg fun (y : γ) => f i y ^ 2) + 3 * (∑ i : Fin n, avg fun (y : γ) => f i y ^ 2) ^ 2

Fourth moment of a sum of independent centered coordinates bounded by 1: 𝔼S⁴ ≤ σ² + 3σ⁴.

theorem Dynamics.avg_pz_one_sided {γ : Type u_1} [Fintype γ] [Nonempty γ] (X : γ → ℝ) (hX : 0 ≤ avg X) {θ : ℝ} (hθ0 : 0 ≤ θ) (hθ1 : θ ≤ 1) :
(1 - θ) ^ 2 * avg X ^ 2 ≤ (avg fun (y : γ) => X y ^ 2) * avg fun (y : γ) => if θ * avg X < X y then 1 else 0

Paley-Zygmund, one-sided. If 𝔼X ≥ 0 (e.g. X ≥ 0) and 0 ≤ θ ≤ 1, then (1 - θ)² (𝔼X)² ≤ 𝔼X² P(X > θ 𝔼X), i.e. P(X > θ 𝔼X) ≥ (1 - θ)² (𝔼X)² / 𝔼X².

theorem Dynamics.avg_pz {γ : Type u_1} [Fintype γ] [Nonempty γ] (Z : γ → ℝ) {s : ℝ} (hs : 0 < s) (h2 : (avg fun (y : γ) => Z y ^ 2) = s) (h4 : (avg fun (y : γ) => Z y ^ 4) ≤ 4 * s ^ 2) :
9 / 64 ≤ avg fun (y : γ) => if s ≤ 4 * Z y ^ 2 then 1 else 0

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).

theorem Dynamics.avg_pz_sum {n : ℕ} {γ : Type u_1} [Fintype γ] [Nonempty γ] (f : Fin n → γ → ℝ) (hf0 : ∀ (i : Fin n), avg (f i) = 0) (hfb : ∀ (i : Fin n) (y : γ), |f i y| ≤ 1) (hσ : 1 ≤ ∑ i : Fin n, avg fun (y : γ) => f i y ^ 2) :
9 / 64 ≤ avg fun (ω : Fin n → γ) => if (∑ i : Fin n, avg fun (y : γ) => f i y ^ 2) ≤ 4 * (∑ i : Fin n, f i (ω i)) ^ 2 then 1 else 0

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 #

theorem Dynamics.abs_sub_avg_le_one_of_zero_one {γ : Type u_1} [Fintype γ] {f : γ → ℝ} (hf : ∀ (y : γ), f y = 0 ∨ f y = 1) (y : γ) :
|f y - avg f| ≤ 1

A {0,1}-valued function deviates from its mean by at most 1.

theorem Dynamics.variance_of_zero_one {γ : Type u_1} [Fintype γ] [Nonempty γ] {f : γ → ℝ} (hf : ∀ (y : γ), f y = 0 ∨ f y = 1) :
variance f = avg f * (1 - avg f)

The variance of a {0,1}-valued function with mean p is p (1 - p).

theorem Dynamics.avg_pz_zero_one {n : ℕ} {γ : Type u_1} [Fintype γ] [Nonempty γ] (Y : Fin n → γ → ℝ) (hY : ∀ (i : Fin n) (y : γ), Y i y = 0 ∨ Y i y = 1) (hσ : 1 ≤ ∑ i : Fin n, variance (Y i)) :
9 / 64 ≤ avg fun (ω : Fin n → γ) => if ∑ i : Fin n, variance (Y i) ≤ 4 * (∑ i : Fin n, (Y i (ω i) - avg (Y i))) ^ 2 then 1 else 0

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.

theorem Dynamics.avg_exp_sum_le {n : ℕ} {γ : Type u_1} [Fintype γ] [Nonempty γ] (Y : Fin n → γ → ℝ) (hY : ∀ (i : Fin n) (y : γ), Y i y = 0 ∨ Y i y = 1) (t : ℝ) :
(avg fun (ω : Fin n → γ) => Real.exp (t * ∑ i : Fin n, Y i (ω i))) ≤ Real.exp (t * ∑ i : Fin n, avg (Y i) + ↑n * (t ^ 2 / 8))

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 #

theorem Dynamics.avg_sq_sum_le_of_pairwise {Ω : Type u_2} {ι : Type u_3} [Fintype Ω] (s : Finset ι) (X : ι → Ω → ℝ) (hX : ∀ (i : ι) (ω : Ω), X i ω = 0 ∨ X i ω = 1) (hind : ∀ i ∈ s, ∀ j ∈ s, i ≠ j → (avg fun (ω : Ω) => X i ω * X j ω) = avg (X i) * avg (X j)) :
(avg fun (ω : Ω) => (∑ i ∈ s, X i ω) ^ 2) ≤ ∑ i ∈ s, avg (X i) + (∑ i ∈ s, avg (X i)) ^ 2

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.