Theorem 3.4 — general degrees:
OpenProdMomentConc.Supplement.theorem_3_4Let be -wise independent random variables (every at most of them are mutually independent). For each output let and with , and suppose for all . The dependency graph is bipartite, with the bits as left vertices, the outputs as right vertices, and an edge iff . Underlying variables that appear in no output are discarded, and . is the binary relative entropy.
Suppose the dependency graph has maximum left degree at most (each bit is read by at most outputs) and maximum right degree at most (each output reads at most bits), and assume . Then for every ,
This is the worst-case-degree baseline; the mission's goal (Theorem 3.5) improves the factor to at the cost of the constant , so it does not imply this bound.
Formalization Note are degree bounds, not exact maxima. The setup is the same as in the published goal ProdMomentConc.theorem_3_5.
Differences from the source:
- encoding: X₁, …, Xₘ ∈ {0,1} r-wise independent random variables → Bool-valued measurable bits; r-wise independence is the published LaconicBarrier.KWiseIndep (iIndepFun on every set of at most r variables) of the bits read as reals in {0,1}; reason: a {0,1}-valued variable and its Bool version generate the same σ-algebra, so the instances are the same
- encoding: each Yᵢ a function of a subset of the Xⱼ, Yᵢ ∈ [0,1] → Yᵢ = f i (X restricted to P i) with P : Fin n → Finset (Fin m) and f i : (P i → Bool) → ℝ valued in [0,1]; E[Yᵢ] = p as a Bochner integral; reason: Definition 2.4's read-Δ model; every f i is bounded and takes finitely many values, so the integral is never junk
- encoding: We discard underlying variables that appear in no output → hypothesis hused : ∀ j, ∃ i, j ∈ P i; reason: discarding unused variables is the same as assuming there are none
- encoding: ⌊r/Δ_R⌋ → natural-number division r / Δ_R, cast to ℝ; reason: the same value
import Mathlib import Definitions.Def_LimitedPriceChanges_LowerBound_KL import Definitions.Def_LaconicBarrier_KWiseIndep open MeasureTheory ProbabilityTheory
namespace ProdMomentConc.Supplement
/-- **Theorem 3.4 (general degrees, baseline).** Saks, Srinivasan, Valieva, *Concentration from
Product Moments via an Additional Element of Randomness*, arXiv:2608.04125 (held version, sha256
5218e9d0…), Theorem 3.4, p.15.
Let `X₁, …, Xₘ ∈ {0,1}` be `r`-wise independent and `Y₁, …, Yₙ ∈ [0,1]` with `E[Yᵢ] = p` for all
`i`, each `Yᵢ` a function of a subset of the `Xⱼ`, with dependency graph of maximum left degree at
most `Δ_L` and maximum right degree at most `Δ_R`. Discard underlying variables appearing in no
output and assume `1 ≤ r ≤ m` and `r ≥ Δ_R`. Then for every `0 < p < α < 1`,
`Pr[∑ Yᵢ ≥ αn] ≤ exp(−(⌊r/Δ_R⌋/Δ_L) D(α‖p))`.
**Formalization Note.**
* The bits are `Bool`-valued; output `i` is `f i` applied to the restriction of the bit vector to
`P i`, and `f i` takes values in `[0, 1]` (Definition 2.4, p.9).
* r-wise independence is the published `LaconicBarrier.KWiseIndep` (`iIndepFun` on every set of
at most `r` variables) applied to the bits read as reals in `{0, 1}`, exactly as in the published
`ProdMomentConc.theorem_3_5`.
* `D(α‖p)` is the published `LimitedPriceChanges.LowerBound.klBer α p`
`= α ln(α/p) + (1 − α) ln((1 − α)/(1 − p))` (p.4).
* "We discard underlying variables that appear in no output" is the hypothesis `hused`.
* `ΔL`, `ΔR` are degree bounds ("maximum left degree at most ∆L"), not the exact maxima.
* `⌊r/Δ_R⌋` is natural-number division `r / ΔR`, cast to `ℝ`. -/
theorem theorem_3_4 {Ω : Type*} [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ]
{m n : ℕ} (X : Fin m → Ω → Bool) (hXm : ∀ j, Measurable (X j))
(r : ℕ)
(hX : LaconicBarrier.KWiseIndep μ (fun j ω => if X j ω then (1 : ℝ) else 0) r)
(P : Fin n → Finset (Fin m)) (f : (i : Fin n) → (P i → Bool) → ℝ)
(hf : ∀ i b, 0 ≤ f i b ∧ f i b ≤ 1) (p : ℝ)
(hmean : ∀ i, ∫ ω, f i (fun j => X j ω) ∂μ = p)
(ΔL ΔR : ℕ) (hΔL : ∀ j, (Finset.univ.filter (fun i => j ∈ P i)).card ≤ ΔL)
(hΔR : ∀ i, (P i).card ≤ ΔR) (hused : ∀ j, ∃ i, j ∈ P i)
(hr1 : 1 ≤ r) (hrm : r ≤ m) (hrΔR : ΔR ≤ r)
(α : ℝ) (hp : 0 < p) (hpα : p < α) (hα1 : α < 1) :
μ.real {ω | α * (n : ℝ) ≤ ∑ i, f i (fun j => X j ω)} ≤
Real.exp (-(((r / ΔR : ℕ) : ℝ) / (ΔL : ℝ)) *
LimitedPriceChanges.LowerBound.klBer α p) := by sorry
end ProdMomentConc.Supplement