Theorem B.2 — the full second-difference expectation expansion
OpenSampleCRS.AlmostGreedy.Supplement.theorem_b_2contention-resolutionp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let have arbitrary laws on with finite means. Define and . For any satisfying
the expectations of are finite, the signed expansion is summable, and
The means need not be equal. Neither independence nor common underlying probability space, bounded support, extra moments or convexity is assumed. The integrability and convergence conclusions make the displayed equality an equality of genuine finite expectations and convergent series.
Differences from the source:
- encoding: arbitrary N-supported random variables with finite means → their probability laws NatLaw on N with integrable first moment; reason: every such random variable has this pushforward law, and every such law is realized by the identity variable
- encoding: the printed absolute summability hypothesis and expectation-series equality → Summable of the nonnegative weighted absolute differences, with integrability and signed summability asserted in the conclusion; reason: these are exactly the well-definedness consequences implicit in the source equality; they prevent totalized real integrals or tsum from assigning a spurious zero
Preamble
import Mathlib import Definitions.Def_SampleCRS_AlmostGreedy_Supplement_discreteOrder
Formal statement
namespace SampleCRS.AlmostGreedy.Supplement
/-- Theorem B.2, p.38. the full second-difference expectation expansion. -/
theorem theorem_b_2 (P Q : NatLaw) (f : ℕ → ℝ) (hs : SecondDifferenceSummable P Q f) :
MeasureTheory.Integrable f P.law ∧ MeasureTheory.Integrable f Q.law ∧
Summable (fun j => stopDifference P Q j * delta2 f j) ∧
(∫ j, f j ∂P.law) - (∫ j, f j ∂Q.law) =
(mean P - mean Q) * delta f 0 + ∑' j, stopDifference P Q j * delta2 f j := by sorry
end SampleCRS.AlmostGreedy.Supplement
Source
Shaddin Dughmi, Vasilis Livanos, Pranav Nuti, STOC 2027 submission #686 (October 2026), Theorem B.2, p. 38