Mixed moments of balanced predicates on independent coordinates
Lax253009.ProductMoments · concepts/Lax253009/ProductMoments.lean · lax-253009
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Choose independently and uniformly a label from a nonempty finite set for every coordinate . If two real predicates have mean zero, then is zero for , and is for .
This is the independence and cancellation argument from equation (6) to equation (7) in the proof of Lemma 4.5. For the application, labels are -bit words and the predicates are balanced sign-valued functions.
For a finite family of balanced predicates, the second moment of a weighted sum over supports therefore contains only equal-support terms, weighted by the squares of their coefficients. This yields the exact expression in equation (7) before the correlation estimates are applied. For supports of size at least and coefficients of total squared mass at most one, this second moment is bounded by the sum of the absolute correlations to the power .
Concept map
Evidence
Lean source view on GitHub
| 1 | import Mathlib.Data.Real.Basic |
| 2 | import Mathlib.Data.Fintype.Pi |
| 3 | import Mathlib.Algebra.BigOperators.Expect |
| 4 | import Mathlib.Algebra.BigOperators.Ring.Finset |
| 5 | |
| 6 | /-! |
| 7 | --- |
| 8 | title: Mixed moments of balanced predicates on independent coordinates |
| 9 | type: theorem |
| 10 | --- |
| 11 | Choose independently and uniformly a label from a nonempty finite |
| 12 | set for every coordinate . If two real predicates have mean zero, |
| 13 | then |
| 14 | |
| 15 | is zero for , and is |
| 16 | for . |
| 17 | |
| 18 | This is the independence and cancellation argument from equation (6) to |
| 19 | equation (7) in the proof of Lemma 4.5. For the application, labels are |
| 20 | -bit words and the predicates are balanced sign-valued functions. |
| 21 | |
| 22 | For a finite family of balanced predicates, the second moment of a weighted |
| 23 | sum over supports therefore contains only equal-support terms, weighted |
| 24 | by the squares of their coefficients. This yields the exact expression |
| 25 | in equation (7) before the correlation estimates are applied. |
| 26 | For supports of size at least and coefficients of total squared mass |
| 27 | at most one, this second moment is bounded by the sum of the absolute |
| 28 | correlations to the power . |
| 29 | -/ |
| 30 | |
| 31 | namespace Lax253009.ProductMoments |
| 32 | |
| 33 | open scoped BigOperators |
| 34 | |
| 35 | noncomputable def weightedSum {ι κ : Type} (supports : Finset (Finset ι)) |
| 36 | (c : Finset ι → ℝ) (predicates : Finset (κ → ℝ)) (f : ι → κ) : ℝ := |
| 37 | ∑ S ∈ supports, c S * ∑ B ∈ predicates, ∏ i ∈ S, B (f i) |
| 38 | |
| 39 | axiom mixed_moment {ι κ : Type} [Fintype ι] [DecidableEq ι] |
| 40 | [Fintype κ] [Nonempty κ] (B C : κ → ℝ) |
| 41 | (hB : (𝔼 z, B z) = 0) (hC : (𝔼 z, C z) = 0) (S T : Finset ι) : |
| 42 | (𝔼 f : ι → κ, (∏ i ∈ S, B (f i)) * (∏ i ∈ T, C (f i))) = |
| 43 | if S = T then (𝔼 z, B z * C z) ^ S.card else 0 |
| 44 | |
| 45 | axiom second_moment {ι κ : Type} [Fintype ι] [DecidableEq ι] |
| 46 | [Fintype κ] [Nonempty κ] (supports : Finset (Finset ι)) |
| 47 | (c : Finset ι → ℝ) (predicates : Finset (κ → ℝ)) |
| 48 | (hbalanced : ∀ B ∈ predicates, (𝔼 z, B z) = 0) : |
| 49 | (𝔼 f : ι → κ, weightedSum supports c predicates f ^ 2) = |
| 50 | ∑ S ∈ supports, c S ^ 2 * |
| 51 | ∑ B ∈ predicates, ∑ C ∈ predicates, (𝔼 z, B z * C z) ^ S.card |
| 52 | |
| 53 | axiom high_degree_bound {ι κ : Type} [Fintype ι] [DecidableEq ι] |
| 54 | [Fintype κ] [Nonempty κ] (supports : Finset (Finset ι)) |
| 55 | (c : Finset ι → ℝ) (predicates : Finset (κ → ℝ)) (l : ℕ) |
| 56 | (hbalanced : ∀ B ∈ predicates, (𝔼 z, B z) = 0) |
| 57 | (hbounded : ∀ B ∈ predicates, ∀ z, |B z| ≤ 1) |
| 58 | (hdegree : ∀ S ∈ supports, l ≤ S.card) |
| 59 | (henergy : ∑ S ∈ supports, c S ^ 2 ≤ 1) : |
| 60 | (𝔼 f : ι → κ, weightedSum supports c predicates f ^ 2) ≤ |
| 61 | ∑ B ∈ predicates, ∑ C ∈ predicates, |𝔼 z, B z * C z| ^ l |
| 62 | |
| 63 | end Lax253009.ProductMoments |
| 64 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments