Lemma 3.6 — inverse binomial moments: and for any coupling
OpenQMomentMatch.FirstBound.Supplement.lemma_3_6binomial-distributionp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let be an integer, let , and let be random variables (on a common probability space, not necessarily independent) with marginal laws and . Then
and for all real with ,
In the proof of Lemma 4.1 this averages the inverse block-count factors of Lemma 4.9 over the random multiplicities, where the counts of different values are dependent.
Formalization Note The pair is given by its joint law on , an arbitrary probability vector whose two marginals are the binomial laws; every coupling of and has such a joint law, and the expectations depend only on it.
Differences from the source:
- encoding: random variables Y, Z with marginals Bin(m−1, a), Bin(m−1, b), not necessarily independent → an arbitrary probability vector μ on Fin m × Fin m whose marginals are binomPmf (m−1) a and binomPmf (m−1) b; reason: both expectations depend only on the joint law, which is supported on {0,…,m−1}²
Preamble
import Mathlib import Definitions.Def_QMomentMatch_FirstBound_Basic import Definitions.Def_QMomentMatch_FirstBound_Supplement_NewtonCoeff
Formal statement
namespace QMomentMatch.FirstBound.Supplement
open QMomentMatch.FirstBound
/-- Lemma 3.6 (Inverse binomial moments), pp. 17–18. The pair `(Y, Z)` is given by its joint
law `μ` on `{0, …, m−1}²` (any coupling), whose marginals are `Bin(m − 1, a)` and
`Bin(m − 1, b)`. -/
theorem lemma_3_6 (m : ℕ) (hm : 1 ≤ m) (a b : ℝ) (ha : 0 < a) (ha1 : a ≤ 1)
(hb : 0 < b) (hb1 : b ≤ 1) (μ : Fin m × Fin m → ℝ) (hμ : IsProbVec μ)
(hY : ∀ y : Fin m, ∑ z : Fin m, μ (y, z) = binomPmf (m - 1) a y)
(hZ : ∀ z : Fin m, ∑ y : Fin m, μ (y, z) = binomPmf (m - 1) b z) :
∑ p : Fin m × Fin m, μ p * (1 + ((p.1 : ℕ) : ℝ))⁻¹ = (1 - (1 - a) ^ m) / ((m : ℝ) * a) ∧
(1 - (1 - a) ^ m) / ((m : ℝ) * a) ≤ 1 / ((m : ℝ) * a) ∧
∀ β γ : ℝ, 0 ≤ β → 0 ≤ γ → β + γ ≤ 1 →
∑ p : Fin m × Fin m, μ p * ((1 + ((p.1 : ℕ) : ℝ)) ^ (-β) * (1 + ((p.2 : ℕ) : ℝ)) ^ (-γ)) ≤
((m : ℝ) * a) ^ (-β) * ((m : ℝ) * b) ^ (-γ) := by sorry
end QMomentMatch.FirstBound.Supplement
Source
Chandrima Kayal, Frédéric Magniez, Sayantan Sen, Dániel Szabó, STOC 2027 submission #564 (October 2026), Lemma 3.6, pp. 17–18