Lemma 3.3 — prefix threshold-product bound
OpenSampleCRS.AlmostGreedy.Supplement.lemma_3_3contention-resolutionp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let and fix an arrival whose prefix mass satisfies . For the product when , with otherwise,
There is no restriction on suffix mass and no total-mass-one assumption. This is the product inequality supporting the threshold-loss bound.
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.3, p.13. prefix threshold-product bound. -/
theorem lemma_3_3 {n : ℕ} (p : Fin n → ℝ) (hp : ValidProb p) (ell : Fin n)
(hprefix : (∑ i ∈ Finset.univ.filter (fun i : Fin n => i ≤ ell), p i) ≤ 1) :
(∑ i ∈ Finset.univ.filter (fun i : Fin n => i < ell),
p i * (1 - p i) * (g p ell (some i) - g p ell none)) ≤ (3 / 8 : ℝ) := by sorry
end SampleCRS.AlmostGreedy.Supplement
Source
Shaddin Dughmi, Vasilis Livanos, Pranav Nuti, STOC 2027 submission #686 (October 2026), Lemma 3.3, p. 13