Forward shortfall
DefinitionLawLocalComp_Supplement_AdmitsShortfalllaw-compressionmonotone-normsp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilitystochastic-loads
Let , be finite nonnegative laws and . For a coupling of and , the forward shortfall is
The pair admits shortfall at most if some coupling of and has .
Zero forward shortfall means , the opposite of the conditional-mean contraction . Theorem 6.2's second lower bound applies to maps whose input/output pairs all admit shortfall at most .
Formalization Note , so the shortfall is written without division.
Definition code
import Mathlib
import Definitions.Def_LawLocalComp_mean
import Definitions.Def_LawLocalComp_Supplement_IsCoupling
open Classical
namespace LawLocalComp
namespace Supplement
/-- **The input/output pair admits forward shortfall at most `β E X`.**
Mahboub–Rahgoshay, *Optimal Law-Local Compression for Stochastic Loads*, STOC 2027
submission manuscript of Oct. 29, 2026 (sha256 5f71501c…aa873), §6.1, p.10: "For an input/output coupling π put s_π = E(X − E_π[Y | X])_+"; Theorem 6.2, p.10
("whose input/output pairs admit s_π ≤ βEX").
`AdmitsShortfall β X Y`: there is a coupling `π` of `X` and `Y` with
`s_π = ∑_x (x · P(X = x) − ∑_y y · π(x, y))_+ ≤ β · E X`.
**Formalization Note.** `P(X = x) · (x − E_π[Y | X = x])_+ = (x · P(X = x) − ∑_y y π(x, y))_+`,
so the shortfall is written without division. -/
def AdmitsShortfall (β : ℝ) (X Y : Law) : Prop :=
∃ π : ℝ × ℝ →₀ ℝ, IsCoupling π X Y ∧
∑ x ∈ X.w.support, max 0 (x * X.w x - ∑ z ∈ π.support with z.1 = x, z.2 * π z) ≤ β * mean X
end Supplement
end LawLocalComp
Source
Mahboub–Rahgoshay, Optimal Law-Local Compression for Stochastic Loads, STOC 2027 submission (manuscript of Oct. 29, 2026, sha256 5f71501c…aa873), §6.1, p.10 (definition of s_π); Theorem 6.2, p.10