Moments of Rademacher sums via generating functions
ProvedDetANN.rademacher_momentsapproximate-nearest-neighbordata-structuresderandomizationexpander-graphs
Write (definition DetANN_SignChoice).
- Let be uniform, and . For every ,
- Let be a nonempty finite set, uniform in , and . For every ,
These two identities compute the conditional moments in the proof of Lemma 6.2: part 1 for each coordinate under a partial assignment, part 2 for the sum over the independent repetitions .
Formalization Note. Expectations are uniform averages over finite sets (avgOver), and is the coefficient of a formal power series.
Preamble
import Mathlib import Definitions.Def_DetANN_SignedBlocks import Definitions.Def_DetANN_SignChoice
Formal statement
namespace DetANN
/-- **Moments of Rademacher sums via generating functions** (proof of Lemma 6.2).
1. For uniform signs `σ ∈ {±1}^n` and `Y = c + ∑_r a_r σ_r`,
`E[Y^m] = m! [t^m] e^{ct} ∏_r cosh(a_r t)`.
2. If `X_1, …, X_L` depend on independent coordinates `ω_1, …, ω_L` of a uniform point of `Ω^L`,
then `E[(∑_ℓ X_ℓ)^p] = p! [t^p] ∏_ℓ M_ℓ(t)`, where `M_ℓ` is the exponential generating function
of the moments of `X_ℓ`. -/
theorem rademacher_moments :
(∀ (n : ℕ) (c : ℝ) (a : Fin n → ℝ) (m : ℕ),
avgOver (fun s : Fin n → Bool => (c + ∑ r, a r * signOf (s r)) ^ m) =
(m.factorial : ℝ) * PowerSeries.coeff m (expSeries c * ∏ r, coshSeries (a r))) ∧
∀ (Ω : Type) [Fintype Ω] [Nonempty Ω] (L : ℕ) (X : Fin L → Ω → ℝ) (p : ℕ),
avgOver (fun ω : Fin L → Ω => (∑ ℓ, X ℓ (ω ℓ)) ^ p) =
(p.factorial : ℝ) * PowerSeries.coeff p (∏ ℓ, egf fun k => avgOver fun s => X ℓ s ^ k) := by
sorry
end DetANN
Source
Feng, Indyk, Deterministic Approximate Nearest Neighbors in High Dimensions, STOC 2027 submission (manuscript sha256 96f0ad57b9d12ba3ac6f9e61c88ddfd6b621e077d7e2a9821906e5b4ff0d0e82), proof of Lemma 6.2, p.16