Lemma 3.2 — one-sample threshold error
OpenSampleCRS.AlmostGreedy.Supplement.lemma_3_2contention-resolutionp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let have total mass one, let be Algorithm 3's actual sample-based threshold, and put . Then for every element, including zero-bias elements,
The coefficient is the one stated in Lemma 3.2. This controls the threshold distribution error used in Theorem 3.4.
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: threshold 0 before all arrivals and thresholds 1,…,n → none and some i : Option (Fin n); reason: a separate sentinel preserves strict-after-threshold eligibility at the first arrival
Preamble
import Mathlib import Definitions.Def_SampleCRS_AlmostGreedy_Supplement_threshold
Formal statement
namespace SampleCRS.AlmostGreedy.Supplement
/-- Lemma 3.2, p.13. one-sample threshold error. -/
theorem lemma_3_2 {n : ℕ} (p : Fin n → ℝ) (hp : ValidProb p) (hmass : (∑ i, p i) = 1) :
∀ i : Fin n, thresholdError p i ≤ ((1 - 1 / Real.exp 1) / 12) * p i * (1 - p i) := by sorry
end SampleCRS.AlmostGreedy.Supplement
Source
Shaddin Dughmi, Vasilis Livanos, Pranav Nuti, STOC 2027 submission #686 (October 2026), Lemma 3.2, p. 13