Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Finite-mean natural-number laws, discrete convexity and extended expectations

Definition
SampleCRS_AlmostGreedy_Supplement_discreteOrder

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

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

For f:N→Rf:\mathbb N\to\mathbb Rf:N→R, define Δf(j)=f(j+1)−f(j)\Delta f(j)=f(j+1)-f(j)Δf(j)=f(j+1)−f(j) and Δ2f(j)=Δf(j+1)−Δf(j)\Delta^2f(j)=\Delta f(j+1)-\Delta f(j)Δ2f(j)=Δf(j+1)−Δf(j). Discrete convexity means all second differences are nonnegative; discrete concavity means they are nonpositive. A natural-number law is an arbitrary probability measure on N\mathbb NN with finite first moment. Its stop loss at j+1j+1j+1 is E[(X−j−1)+]E[(X-j-1)^+]E[(X−j−1)+], with subtraction in the reals.

For two such laws P,QP,QP,Q, define Dj=EP[(X−j−1)+]−EQ[(Y−j−1)+]D_j=E_P[(X-j-1)^+]-E_Q[(Y-j-1)^+]Dj​=EP​[(X−j−1)+]−EQ​[(Y−j−1)+]. The order P≥cxQP\ge_{cx}QP≥cx​Q tests every discrete convex real function integrable under both laws. Signed extended expectations use

EP∗[f]=∫f+ dP−∫f− dPin R‾.E_P^*[f]=\int f^+\,dP-\int f^-\,dP\quad\text{in }\overline{\mathbb R}.EP∗​[f]=∫f+dP−∫f−dPin R.

On convex tests the negative part is finite under finite-mean laws; on concave tests the positive part is finite. Thus B.1 can retain infinite expectations. The summability predicate for B.2 is exactly the convergence of the nonnegative series ∑j(EP[(X−j−1)+]+EQ[(Y−j−1)+])∣Δ2f(j)∣\sum_j(E_P[(X-j-1)^+]+E_Q[(Y-j-1)^+])|\Delta^2 f(j)|∑j​(EP​[(X−j−1)+]+EQ​[(Y−j−1)+])∣Δ2f(j)∣. There is no restriction to finite support, equal means or a common underlying probability space.

Definition code
import Mathlib

open MeasureTheory

namespace SampleCRS.AlmostGreedy.Supplement

def delta (f : ℕ → ℝ) (j : ℕ) : ℝ := f (j + 1) - f j

def delta2 (f : ℕ → ℝ) (j : ℕ) : ℝ := delta f (j + 1) - delta f j

def DiscreteConvex (f : ℕ → ℝ) : Prop := ∀ j, 0 ≤ delta2 f j

def DiscreteConcave (f : ℕ → ℝ) : Prop := ∀ j, delta2 f j ≤ 0

/-- Arbitrary N-supported laws, using their pushforward distributions. There is
no common-space, independence, finite-support or higher-moment assumption. -/
structure NatLaw where
  law : Measure ℕ
  probability : IsProbabilityMeasure law
  finiteMean : Integrable (fun j : ℕ => (j : ℝ)) law

attribute [instance] NatLaw.probability

noncomputable def mean (P : NatLaw) : ℝ := ∫ j, (j : ℝ) ∂P.law

/-- Real subtraction after casting counts, followed by the positive part. -/
noncomputable def stopLoss (P : NatLaw) (j : ℕ) : ℝ :=
  ∫ x, max ((x : ℝ) - (j : ℝ) - 1) 0 ∂P.law

noncomputable def stopDifference (P Q : NatLaw) (j : ℕ) : ℝ := stopLoss P j - stopLoss Q j

def ConvexDominates (P Q : NatLaw) : Prop :=
  ∀ f : ℕ → ℝ, DiscreteConvex f → Integrable f P.law → Integrable f Q.law →
    (∫ j, f j ∂Q.law) ≤ ∫ j, f j ∂P.law

/-- Signed extended expectation. Convex tests under finite-mean laws have a
finite negative part, and concave tests have a finite positive part. Thus on
the domains used in B.1 there is no infinity-minus-infinity ambiguity. -/
noncomputable def extendedE (P : Measure ℕ) (f : ℕ → ℝ) : EReal :=
  (∫⁻ j, ENNReal.ofReal (f j) ∂P).toEReal - (∫⁻ j, ENNReal.ofReal (-f j) ∂P).toEReal

def SecondDifferenceSummable (P Q : NatLaw) (f : ℕ → ℝ) : Prop :=
  Summable (fun j => (stopLoss P j + stopLoss Q j) * |delta2 f j|)

end SampleCRS.AlmostGreedy.Supplement
Source
Shaddin Dughmi, Vasilis Livanos, Pranav Nuti, STOC 2027 submission #686 (October 2026), Definitions B.2–B.3 and Theorem B.2 setup, pp.37–38

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