§A.2 — the expectation bound
ProvedProdMomentConc.expect_Lk_leconcentration-inequalitieslimited-independencep2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1probabilityread-k-families
Let be the read sets of the dependency graph, its average right degree, , and a uniformly random -subset of . Then
where is the number of underlying variables read by the outputs in .
The bound holds because and each output lies in with probability . It turns the tail estimates of around into the condition of Lemma A.2 (ii) and Theorem 3.5.
Formalization Note is Lk P I with kSubsetLaw n k, and is dR P.
Differences from the source:
- generalization: k a positive integer in the setting of Theorem 3.5 → any k ≤ n and any read sets; reason: the source's case is an instance
Preamble
import Mathlib import Definitions.Def_ProdMomentConc_edgeCount import Definitions.Def_ProdMomentConc_kSubsetLaw import Definitions.Def_ProdMomentConc_Lk open MeasureTheory ProbabilityTheory
Formal statement
namespace ProdMomentConc
/-- **Expectation bound `E L_k ≤ d_R k`** (§A.2).
Saks, Srinivasan, Valieva, *Concentration from Product Moments via an Additional Element of
Randomness*, arXiv:2608.04125 (held version, sha256 5218e9d0…), §A.2, p.36: "E Lk ≤ E_S[∑_{i∈I} deg(i)] = ∑ᵢ deg(i) Pr[i ∈ I] = (k/n) ∑ᵢ deg(i) = dR k".
For `I` a uniformly random `k`-subset of `[n]` (`k ≤ n`), the expected number of underlying
variables read by the outputs in `I` is at most `d_R k`, where `d_R` is the average right degree.
**Formalization Note.** `L_k = Lk P I`, `I ∼ kSubsetLaw n k`, `d_R = dR P = (∑ᵢ |Pᵢ|)/n`. -/
theorem expect_Lk_le {m n : ℕ} (P : Fin n → Finset (Fin m)) (k : ℕ) (hkn : k ≤ n) :
∫ S, (Lk P S : ℝ) ∂(kSubsetLaw n k) ≤ dR P * (k : ℝ) := by sorry
end ProdMomentConc
Source
Saks, Srinivasan, Valieva, Concentration from Product Moments via an Additional Element of Randomness, arXiv:2608.04125 (held version, sha256 5218e9d0405f975413d3e2dd2c4c9d6b43c772029e645965afee1cd619ae38aa), §A.2, p.36 (PDF p.36)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.