Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 5.1 — uniform acceptance-tail and moving-prefix limits

Open
SampleCRS.AlmostGreedy.Supplement.lemma_5_1

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

contention-resolutionp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1probability

Fix k≥2k\ge2k≥2 and the optimal known-probability adversarial balance γ=γadv(k)\gamma=\gamma_{\rm adv}(k)γ=γadv​(k). Consider any sequence of instances, with possibly varying sizes and policies, satisfying pi(r)>0p_i^{(r)}>0pi(r)​>0, ∑ipi(r)=k\sum_i p_i^{(r)}=k∑i​pi(r)​=k and δr=max⁡ipi(r)→0\delta_r=\max_i p_i^{(r)}\to0δr​=maxi​pi(r)​→0. Each policy is γ\gammaγ-balanced on its instance and may have full distributional knowledge. Let Nj(r)N_j^{(r)}Nj(r)​ be its number of acceptances in the first jjj arrivals, and interpolate H2,j(r)=E[(Nj(r)−1)+]H_{2,j}^{(r)}=E[(N_j^{(r)}-1)^+]H2,j(r)​=E[(Nj(r)​−1)+] linearly at the prefix masses sj(r)s_j^{(r)}sj(r)​.

With h2h_2h2​ defined by (11),

H2(δr)⟶h2uniformly on [0,k].H_2^{(\delta_r)}\longrightarrow h_2\quad\text{uniformly on }[0,k].H2(δr​)​⟶h2​uniformly on [0,k].

Moreover, for every sequence jr≤nrj_r\le n_rjr​≤nr​ and every real ttt with sjr(r)→ts_{j_r}^{(r)}\to tsjr​(r)​→t,

E[(Njr(r)−1)+]⟶h2(t).E[(N_{j_r}^{(r)}-1)^+]\longrightarrow h_2(t).E[(Njr​(r)​−1)+]⟶h2​(t).

This includes every moving-prefix limit, not just the two-block constructions used later. The balance assumption need only hold at each indicated instance, as in the proof in Appendix A.5.

Differences from the source:

  • encoding: arbitrary randomized nonanticipating policies, even with fixed order known in advance → real behavioral kernels on complete activation/action histories in arrival-position labels; reason: perfect recall on the finite observation tree represents arbitrary independent private randomness; relabelling a known order preserves all information
  • encoding: positive-bias instances, interpolation and h₂ in (11) → dependent finite sizes, half-open affine segments, the actual terminal node and explicit hSecond; reason: strictly positive p gives distinct interpolation nodes; hSecond is exactly formula (11) with the operational optimum
  • generalization: a sequence of γ-balanced OCRSs and instances → arbitrary kernels with γ balance at their indicated instances; reason: Appendix A.5 uses only the acceptance inequalities at each indicated instance; every globally γ-balanced scheme specializes to these kernels
Preamble
import Mathlib
import Definitions.Def_SampleCRS_AlmostGreedy_Supplement_prefixLimits
Formal statement
namespace SampleCRS.AlmostGreedy.Supplement

/-- Lemma 5.1, p.24. uniform acceptance-tail and moving-prefix limits. -/
theorem lemma_5_1 (k : ℕ) (hk : 2 ≤ k) (n : ℕ → ℕ)
    (p : (r : ℕ) → Fin (n r) → ℝ) (π : (r : ℕ) → OnlineKernel (n r))
    (hp : ∀ r, ValidProb (p r)) (hpos : ∀ r i, 0 < p r i)
    (hmass : ∀ r, (∑ i, p r i) = (k : ℝ))
    (hbal : ∀ r, BalancedInstance k (gammaAdv k) (π r) (p r))
    (hsmall : Filter.Tendsto (fun r => maxBias (p r)) Filter.atTop (nhds 0)) :
    TendstoUniformlyOn (fun r t => interpolateTail k (π r) (p r) 2 t)
      (hSecond k) Filter.atTop (Set.Icc 0 (k : ℝ)) ∧
    ∀ j : ℕ → ℕ, (∀ r, j r ≤ n r) → ∀ t : ℝ,
      Filter.Tendsto (fun r => prefixMass (p r) (j r)) Filter.atTop (nhds t) →
      Filter.Tendsto (fun r => tailExpectation k (π r) (p r) 2 (j r))
        Filter.atTop (nhds (hSecond k t)) := by sorry

end SampleCRS.AlmostGreedy.Supplement
Source
Shaddin Dughmi, Vasilis Livanos, Pranav Nuti, STOC 2027 submission #686 (October 2026), Lemma 5.1, p. 24

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me