sum_scaled_iid_gaussian_map
theoremverifiedimported Lean
Weighted sum of independent Gaussians is Gaussian. Let $(\Omega,\mu)$ be a probability space, and let $(Y_j)_{j}$ be a family of independent, measurable real-valued random variables, each distributed as a centred Gaussian with mean $0$ and variance $\sigma_0 \ge 0$. Then for any real coefficients $(x_j)_j$ and any finite index set $s$, the random variable $\sum_{j \in s} x_j\, Y_j$ has distribution $N\!\Bigl(0,\; \bigl(\sum_{j \in s} x_j^2\bigr)\,\sigma_0\Bigr)$; that is, its law is the centred Gaussian on $\bbr$ with variance $\sigma_0 \sum_{j \in s} x_j^2$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open MeasureTheory ProbabilityTheory Real NNReal Matrix Finset in variable {d k : ℕ} in lemma sum_scaled_iid_gaussian_map {Ω ι : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {Y : ι → Ω → ℝ} {σ₀ : NNReal} (hY_meas : ∀ j, Measurable (Y j)) (hY_law : ∀ j, Measure.map (Y j) μ = gaussianReal 0 σ₀) (hY_indep : iIndepFun Y μ) (x : ι → ℝ) (s : Finset ι) : Measure.map (fun ω => ∑ j ∈ s, x j * Y j ω) μ = gaussianReal 0 (⟨∑ j ∈ s, (x j) ^ 2, Finset.sum_nonneg (fun _ _ => sq_nonneg _)⟩ * σ₀)
- Source
- TCSlib, `sum_scaled_iid_gaussian_map`
- Lean proof
- By Ganesh Sankar, from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Copyright (c) 2026 Ganesh Sankar. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.sum_scaled_iid_gaussian_map← sum_scaled_iid_gaussian_map (TCSlib/LearningTheory/JohnsonLindenstrauss/RowDistribution.lean:127): adapted
What was changed in
sum_scaled_iid_gaussian_map--- TCSlib/LearningTheory/JohnsonLindenstrauss/RowDistribution.lean:127 (sum_scaled_iid_gaussian_map) +++ as compiled here @@ -1,19 +1,5 @@ -/-- **Row-projection is Gaussian.** - -If `Y j` are mutually independent measurable real random variables each with law -`N(0, σ₀)` and `x j : ℝ` are fixed coefficients, then for every finite set `s` of indices -the weighted sum `∑ j ∈ s, x j · Y j` has law `N(0, (∑ j ∈ s, (x j)²) · σ₀)` under -`μ`. This is the observation of [DG03, §2] that the projection of iid Gaussians is Gaussian with -variance `‖x‖²/k` (DG03 work with a random orthogonal projection; the iid-Gaussian-matrix -form used here is the standard variant, cf. [Ver18, §5.3]). - -**Proof sketch.** Step 1: the scaled family `Z j = x j · Y j` is measurable, each `Z j` -has law `N(0, (x j)²·σ₀)` by `map_const_mul_gaussian`, and the `Z j` are mutually -independent as images of the `Y j`. Step 2: induct on the finite set `s`. In the empty -case the sum is identically `0`, whose law is the Dirac mass at `0`, i.e. `N(0, 0)`. -Step 3 (insert case): split the sum as `Z j₀` plus the sum over the remaining indices; the -two are independent (Mathlib's `iIndepFun.indepFun_finset_sum_of_notMem`), the partial -sum is Gaussian by the induction hypothesis, and the sum of two independent centered -Gaussians is centered Gaussian with added variances -(`gaussianReal_add_gaussianReal_of_indepFun`); finally match the variance expression. -/ +set_option relaxedAutoImplicit false in +set_option autoImplicit false in +open MeasureTheory ProbabilityTheory Real NNReal Matrix Finset in +variable {d k : ℕ} in lemma sum_scaled_iid_gaussian_map @@ -48,4 +34,4 @@ apply NNReal.eq - push_cast - simp + show (0 : ℝ) = 0 * (σ₀ : ℝ) + ring | insert j₀ s' hj₀ ih => @@ -74,3 +60,3 @@ apply NNReal.eq - push_cast + show x j₀ ^ 2 * (σ₀ : ℝ) + (∑ j ∈ s', x j ^ 2) * σ₀ = (∑ j ∈ insert j₀ s', x j ^ 2) * σ₀ rw [Finset.sum_insert hj₀] - Verified
- 16 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- map_const_mul_gaussianScaling a centered real Gaussian. Let $X\colon \Omega \to \bbr$ be a measurable random variable on a measure space $(\Omega, \mu)$ whose…
- Used by 1
- jl_concentration_single_via_chi_squaredJohnson–Lindenstrauss concentration for a single vector. Let $k \ge 1$, and let $A$ be a random $k \times d$ real matrix on a probability…
Lean source view module on GitHub
set_option relaxedAutoImplicit false in set_option autoImplicit false in open MeasureTheory ProbabilityTheory Real NNReal Matrix Finset in variable {d k : ℕ} in /-- **Row-projection is Gaussian.** If `Y j` are mutually independent measurable real random variables each with law `N(0, σ₀)` and `x j : ℝ` are fixed coefficients, then for every finite set `s` of indices the weighted sum `∑ j ∈ s, x j · Y j` has law `N(0, (∑ j ∈ s, (x j)²) · σ₀)` under `μ`. This is the observation of [DG03, §2] that the projection of iid Gaussians is Gaussian with variance `‖x‖²/k` (DG03 work with a random orthogonal projection; the iid-Gaussian-matrix form used here is the standard variant, cf. [Ver18, §5.3]). **Proof sketch.** Step 1: the scaled family `Z j = x j · Y j` is measurable, each `Z j` has law `N(0, (x j)²·σ₀)` by `map_const_mul_gaussian`, and the `Z j` are mutually independent as images of the `Y j`. Step 2: induct on the finite set `s`. In the empty case the sum is identically `0`, whose law is the Dirac mass at `0`, i.e. `N(0, 0)`. Step 3 (insert case): split the sum as `Z j₀` plus the sum over the remaining indices; the two are independent (Mathlib's `iIndepFun.indepFun_finset_sum_of_notMem`), the partial sum is Gaussian by the induction hypothesis, and the sum of two independent centered Gaussians is centered Gaussian with added variances (`gaussianReal_add_gaussianReal_of_indepFun`); finally match the variance expression. -/ lemma sum_scaled_iid_gaussian_map {Ω ι : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {Y : ι → Ω → ℝ} {σ₀ : NNReal} (hY_meas : ∀ j, Measurable (Y j)) (hY_law : ∀ j, Measure.map (Y j) μ = gaussianReal 0 σ₀) (hY_indep : iIndepFun Y μ) (x : ι → ℝ) (s : Finset ι) : Measure.map (fun ω => ∑ j ∈ s, x j * Y j ω) μ = gaussianReal 0 (⟨∑ j ∈ s, (x j) ^ 2, Finset.sum_nonneg (fun _ _ => sq_nonneg _)⟩ * σ₀) := by classical -- Step 1: the family `Z j := x j * Y j` is independent Gaussian by `iIndepFun.comp`. set Z : ι → Ω → ℝ := fun j ω => x j * Y j ω with hZ_def have hZ_meas : ∀ j, Measurable (Z j) := fun j => (hY_meas j).const_mul (x j) have hZ_law : ∀ j, Measure.map (Z j) μ = gaussianReal 0 (⟨(x j) ^ 2, sq_nonneg _⟩ * σ₀) := fun j => map_const_mul_gaussian (hY_meas j) (hY_law j) (x j) have hZ_indep : iIndepFun Z μ := hY_indep.comp (fun j r => x j * r) (fun j => measurable_const.mul measurable_id) -- Step 2: induction on `s`. induction s using Finset.induction_on with | empty => -- The sum is constantly 0, so its law is `Dirac 0 = gaussianReal 0 0`. have hLHS : (fun ω => ∑ j ∈ (∅ : Finset ι), x j * Y j ω) = (fun _ => (0 : ℝ)) := by funext ω; simp rw [hLHS, Measure.map_const, measure_univ, one_smul, ← gaussianReal_zero_var (0 : ℝ), gaussianReal_ext_iff] refine ⟨rfl, ?_⟩ apply NNReal.eq show (0 : ℝ) = 0 * (σ₀ : ℝ) ring | insert j₀ s' hj₀ ih => -- Step 3: split the sum and use independence + Gaussian add. have hsplit : (fun ω => ∑ j ∈ insert j₀ s', x j * Y j ω) = (Z j₀ + ∑ j ∈ s', Z j) := by funext ω change ∑ j ∈ insert j₀ s', x j * Y j ω = Z j₀ ω + (∑ j ∈ s', Z j) ω rw [Finset.sum_insert hj₀, Finset.sum_apply] rw [hsplit] -- Independence between `Z j₀` and the partial sum over `s'`. have hindep : IndepFun (Z j₀) (∑ j ∈ s', Z j) μ := (hZ_indep.indepFun_finset_sum_of_notMem hZ_meas hj₀).symm -- Law of the partial sum: massage the IH from the `fun ω => ...` form to the -- Pi-sum form `∑ j ∈ s', Z j`. have hpartial_eq : (fun ω => ∑ j ∈ s', x j * Y j ω) = ∑ j ∈ s', Z j := by funext ω change _ = (∑ j ∈ s', Z j) ω rw [Finset.sum_apply] rw [hpartial_eq] at ih -- Combine using `gaussianReal_add_gaussianReal_of_indepFun`. rw [gaussianReal_add_gaussianReal_of_indepFun hindep (hZ_law j₀) ih] -- Match the variance form. Use `gaussianReal_ext_iff` to split into mean + variance. rw [gaussianReal_ext_iff] refine ⟨by ring, ?_⟩ apply NNReal.eq show x j₀ ^ 2 * (σ₀ : ℝ) + (∑ j ∈ s', x j ^ 2) * σ₀ = (∑ j ∈ insert j₀ s', x j ^ 2) * σ₀ rw [Finset.sum_insert hj₀] ring