Theorem B.1 — Poisson comparison for all convex and concave tests
OpenSampleCRS.AlmostGreedy.Supplement.theorem_b_1contention-resolutionp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let , , and . For every discrete convex function ,
and for every discrete concave the inequality is reversed. No integer-mean or positive-mean assumption is made. The finite Poisson-binomial expectation is real; the Poisson expectation may be for a convex test or for a concave test. Both clauses allow arbitrary growth of .
The paper proves this comparison on pp.39–40 despite its attribution to Hoeffding.
Differences from the source:
- encoding: elements 1,…,n and independent Bernoulli trials → Fin n and finite product-weight expectations; reason: the label shift is a bijection and the weights are exactly the independent Bernoulli law
- encoding: expectations of arbitrary discrete convex or concave tests → signed extended expectations in EReal and a finite real Poisson-binomial expectation; reason: finite-mean convex tests have an affine lower bound and concave tests an affine upper bound; this preserves infinite expectations without a default-zero integral
Preamble
import Mathlib import Definitions.Def_SampleCRS_AlmostGreedy_Supplement_onlineKernel import Definitions.Def_SampleCRS_AlmostGreedy_Supplement_discreteOrder import Definitions.Def_StaticProphetSec_pbE
Formal statement
namespace SampleCRS.AlmostGreedy.Supplement
/-- Theorem B.1, p.37. Poisson comparison for all convex and concave tests. -/
theorem theorem_b_1 {n : ℕ} (p : Fin n → ℝ) (hp : ValidProb p) (f : ℕ → ℝ) :
(DiscreteConvex f →
(StaticProphetSec.pbE f p : EReal) ≤
extendedE (ProbabilityTheory.poissonMeasure (Real.toNNReal (∑ i, p i))) f) ∧
(DiscreteConcave f →
extendedE (ProbabilityTheory.poissonMeasure (Real.toNNReal (∑ i, p i))) f ≤
(StaticProphetSec.pbE f p : EReal)) := by sorry
end SampleCRS.AlmostGreedy.Supplement
Source
Shaddin Dughmi, Vasilis Livanos, Pranav Nuti, STOC 2027 submission #686 (October 2026), Theorem B.1, p. 37