Lemma A.4 — Rare-coordinate bias versus answer entropy
ProvedBirthdayEntropy.Soundness.Supplement.lemma_A_4graph-theoryinformation-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
For real numbers and , let be binary relative entropy with . Then both inequalities hold:
The result separates rare-coordinate bias from the surviving answer-entropy budget, with the exact intermediate constant and the strict final inequality.
Differences from the source:
- encoding: continuous endpoint binary divergence → published bernoulliRelativeEntropy at x=0 allowed; reason: lambda is strictly between zero and one, so the total real formula agrees with both endpoint limits
Preamble
import Mathlib import Definitions.Def_bernoulliRelativeEntropy
Formal statement
namespace BirthdayEntropy.Soundness.Supplement
/-- Lemma A.4, (26), PDF p20 / printed p19. Both the precise gap and its
strict numerical lower bound; x=0 is included. -/
theorem lemma_A_4 (lam x : ℝ) (hlam0 : 0 < lam) (hlam1 : lam < 1)
(hx0 : 0 ≤ x) (hxlam : x ≤ lam / 4) :
lam * (3/4 - Real.log 8 / 4) ≤
BanditAlgorithm.bernoulliRelativeEntropy x lam - x * Real.log 2 ∧
2 * lam / 9 < lam * (3/4 - Real.log 8 / 4) := 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.4, PDF p20 / printed p19