bernoulli_powerset_expectation_double
ProvedDouble linearity of the Bernoulli powerset expectation. The expectation of a double coordinate sum of functions of two inclusion indicators pushes through both sums term-by-term:
This is the form used to expand the second moment (variance) of a statistic linear in the inclusion indicators into a double sum of pair-coordinate expectations.
Preamble
import Definitions.Def_matrix_completion_neumann open MatrixCompletion open scoped BigOperators
Formal statement
theorem bernoulli_powerset_expectation_double {n₁ n₂ : ℕ} (p : ℝ)
(G : (Fin n₁ × Fin n₂) → (Fin n₁ × Fin n₂) → ℝ → ℝ → ℝ) :
bernoulliExpectation p
(fun Omega => ∑ w : Fin n₁ × Fin n₂, ∑ w' : Fin n₁ × Fin n₂,
G w w' (if w ∈ Omega then 1 else 0) (if w' ∈ Omega then 1 else 0)) =
∑ w : Fin n₁ × Fin n₂, ∑ w' : Fin n₁ × Fin n₂,
bernoulliExpectation p
(fun Omega => G w w' (if w ∈ Omega then 1 else 0) (if w' ∈ Omega then 1 else 0)) := by sorrySource
Boucheron–Lugosi–Massart, Concentration Inequalities (OUP 2013), Ch. 15; Candès–Recht 2009, arXiv:0805.4471, §6 (centered sampling operator p⁻¹(P_Ω − p)).