Lemma A.3 — Hypergeometric moments and KL comparison
OpenBirthdayEntropy.Soundness.Supplement.lemma_A_3graph-theoryinformation-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let , , , , the uniform law on all -views, and any probability law on them, allowing zero atoms. Put . For every real ,
If , also
The binary divergence uses the continuous convention at . The moment bound includes and negative tilts; only the KL conclusion restricts . This compares arbitrary view bias with its information cost. The shared moment clause has the existing Open proof dependency RandOrderSort.lemma_4_5; that partial result does not supply the arbitrary-law KL clause.
Differences from the source:
- encoding: arbitrary view law and KL against uniform all-view law → published finite Law and real relativeEntropy, with published Bernoulli divergence; reason: uniform reference masses are positive; zero numerator terms vanish and endpoints have the continuous values
Preamble
import Mathlib import Definitions.Def_BirthdayEntropy_Soundness_Supplement_Agreement import Definitions.Def_bernoulliRelativeEntropy
Formal statement
namespace BirthdayEntropy.Soundness.Supplement
open OAI.ThorpCompatibility
/-- Lemma A.3, (24)–(25), PDF pp19–20 / printed pp18–19. Arbitrary L
and arbitrary view law; every real tilt, including negative ones and endpoint incidences. -/
theorem lemma_A_3 (n ℓ : ℕ) (hn : 1 ≤ n) (hℓ : 1 ≤ ℓ) (hℓn : ℓ ≤ n)
(L : Finset (Fin n)) (μ : Law (View n ℓ)) :
let lam := (L.card : ℝ) / n
let x := lowIncidence μ L
let u := allViewLaw n ℓ hℓn
(∀ t : ℝ, u.mean (fun S => Real.exp (t * ((S.val ∩ L).card : ℝ))) ≤
(1 - lam + lam * Real.exp t)^ℓ) ∧
(0 < lam → lam < 1 →
(ℓ : ℝ) * BanditAlgorithm.bernoulliRelativeEntropy x lam ≤ μ.relativeEntropy u) := by sorry
end BirthdayEntropy.Soundness.Supplement
Source
Alexandru Popa, STOC 2027 submission #907 (October 2026), https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/907.pdf, Lemma A.3, PDF p19-20 / printed p18-19