Theorem 4.2 — Count Test feasibility and explicit balance
OpenSampleCRS.AlmostGreedy.Supplement.theorem_4_2contention-resolutionp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
For every capacity , integer and unknown with , run Count Test (Algorithm 5) in fixed adversarial order. Its output is an active subset of size at most for every realization of the samples, activations, allowance and valid selected candidate-slot subset. For each with ,
All integer choices of are retained. The experiment uses the exact equivalent uniform-slot implementation on p.19.
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: the sequential fraction (min(k,N)-A)/(N-C) in Algorithm 5 → a uniform min(k,N)-subset of N candidate slots chosen in advance; reason: p.19 explicitly proves the two online laws equivalent; unobserved terminal slots are unused and the empty choice at N=0 is unique
Preamble
import Mathlib import Definitions.Def_SampleCRS_AlmostGreedy_Supplement_countTest
Formal statement
namespace SampleCRS.AlmostGreedy.Supplement
/-- Theorem 4.2, p.18. Count Test feasibility and explicit balance. -/
theorem theorem_4_2 {n : ℕ} (k r : ℕ) (hk : 1 ≤ k) (hr : 1 ≤ r)
(p : Fin n → ℝ) (hp : ValidProb p) (hmass : (∑ i, p i) ≤ (k : ℝ)) :
CountFeasible n k r ∧ ∀ i, 0 < p i →
1 - 1 / ((r : ℝ) + 1) - (r : ℝ) / (2 * (k : ℝ)) -
1 / (2 * Real.sqrt (k : ℝ)) ≤ countC k r p i := by sorry
end SampleCRS.AlmostGreedy.Supplement
Source
Shaddin Dughmi, Vasilis Livanos, Pranav Nuti, STOC 2027 submission #686 (October 2026), Theorem 4.2, p. 18