Lemma B.2 — reciprocal Poisson acceptance is convex
OpenSampleCRS.AlmostGreedy.Supplement.lemma_b_2contention-resolutionp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
For every integer , define . Then
Equivalently, is convex on . The parameter is real, not restricted to integer means, and both endpoints are included. This supplies the interpolation inequality used for Conservative Scaling.
Differences from the source:
- encoding: Poisson parameter λ∈[k−1,k] → Real.toNNReal λ in the published bounded-test Poisson expectation; reason: λ≥0 on the entire claimed interval, so this conversion does not change any parameter or expectation
Preamble
import Mathlib import Definitions.Def_SampleCRS_AlmostGreedy_Supplement_scaling
Formal statement
namespace SampleCRS.AlmostGreedy.Supplement
/-- Lemma B.2, p.42. reciprocal Poisson acceptance is convex. -/
theorem lemma_b_2 (k : ℕ) (hk : 2 ≤ k) :
ConvexOn ℝ (Set.Icc ((k : ℝ) - 1) (k : ℝ)) (reciprocalAR k) := by sorry
end SampleCRS.AlmostGreedy.Supplement
Source
Shaddin Dughmi, Vasilis Livanos, Pranav Nuti, STOC 2027 submission #686 (October 2026), Lemma B.2, p. 42