Lemma 3.4, p.8 — and
ProvedDetANN.lemma_3_4approximate-nearest-neighbordata-structuresderandomizationexpander-graphsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be a square-integrable random vector and an independent copy of . Then
These are the variance identities behind the bias–variance arguments of §5 and §7.
Formalization Note is a function on a probability space in ; the pair is realized on .
Differences from the source:
- generalization: random vectors in ℝ^d → random vectors in any complete real inner product space; reason: ℝ^d is a complete real inner product space
- encoding: square-integrable X and an independent copy X′ → MemLp X 2 μ on a probability space, and (X ω, X ω′) under the product measure μ ⊗ μ; reason: the product measure realizes two independent copies with the law of X
Preamble
import Mathlib
Formal statement
namespace DetANN
open MeasureTheory
/-- **Lemma 3.4** (Y. Feng, P. Indyk, *Deterministic Approximate Nearest Neighbors in High Dimensions*, STOC 2027
submission (manuscript sha256 96f0ad57…), (10), p.8).
For a square-integrable random vector `X` and an independent copy `X'`:
`E‖X − EX‖² = ½ E‖X − X'‖²` and, for every vector `v`, `E‖v − X‖² = ‖v − EX‖² + E‖X − EX‖²`.
**Formalization Note.** `X` is defined on a probability space `(Ω, μ)` with values in a complete real
inner product space `F` (the paper uses `F = ℝ^d`), and is square-integrable (`MemLp X 2 μ`), so
every integral is of an integrable function. The pair `(X, X')` of independent copies is realized as
`(X ω, X ω')` under the product measure `μ ⊗ μ`. -/
theorem lemma_3_4 {Ω F : Type*} [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ]
[NormedAddCommGroup F] [InnerProductSpace ℝ F] [CompleteSpace F]
(X : Ω → F) (hX : MemLp X 2 μ) :
∫ ω, ‖X ω - ∫ ω', X ω' ∂μ‖ ^ 2 ∂μ = (1 / 2) * ∫ p, ‖X p.1 - X p.2‖ ^ 2 ∂(μ.prod μ) ∧
∀ v : F, ∫ ω, ‖v - X ω‖ ^ 2 ∂μ =
‖v - ∫ ω, X ω ∂μ‖ ^ 2 + ∫ ω, ‖X ω - ∫ ω', X ω' ∂μ‖ ^ 2 ∂μ := by sorry
end DetANN
Source
Feng, Indyk, Deterministic Approximate Nearest Neighbors in High Dimensions, STOC 2027 submission (manuscript sha256 96f0ad57b9d12ba3ac6f9e61c88ddfd6b621e077d7e2a9821906e5b4ff0d0e82), Lemma 3.4, (10), p.8 (PDF p.8)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.