Lemma B.1 — actual competing candidate-count comparison
OpenSampleCRS.AlmostGreedy.Supplement.lemma_b_1contention-resolutionp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let and have total mass . With Appendix B's parameters , let the independent candidate bits have biases and let . Then for every element, including those with ,
The competitor distribution uses the candidate biases rather than the original activation probabilities. Its mean need not be . This is the comparison used for Algorithm 6.
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: G_i is a sum of independent candidate bits with biases ρ_j, j≠i → the published activation law at candidateBias followed by otherCount; reason: the omitted coordinate is counted nowhere; the unused independent coordinate averages out, giving exactly the same count law
Preamble
import Mathlib import Definitions.Def_SampleCRS_AlmostGreedy_Supplement_scaling
Formal statement
namespace SampleCRS.AlmostGreedy.Supplement
/-- Lemma B.1, p.41. actual competing candidate-count comparison. -/
theorem lemma_b_1 {n : ℕ} (k : ℕ) (hk : 1 ≤ k) (p : Fin n → ℝ)
(hp : ValidProb p) (hmass : (∑ i, p i) = (k : ℝ)) :
∀ i : Fin n, StaticProphetSec.poisE (StaticProphetSec.AR k)
(Real.toNNReal ((k : ℝ) - p i)) ≤ competingAR k p i := by sorry
end SampleCRS.AlmostGreedy.Supplement
Source
Shaddin Dughmi, Vasilis Livanos, Pranav Nuti, STOC 2027 submission #686 (October 2026), Lemma B.1, p. 41