Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1 — greedy worst-case distribution

Proved
ChenWasserstein.Reform.theorem_1

by Shuze Chen · Oct 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

chance-constraintsoptimal-transportoptimizationp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let EEE be a finite-dimensional real normed space with its Borel sigma algebra, let N≥1N\ge1N≥1, and let ξ1,…,ξN∈E\xi_1,\ldots,\xi_N\in Eξ1​,…,ξN​∈E be arbitrary samples, with repetitions permitted. Let S⊆ES\subseteq ES⊆E be open with nonempty complement C=E∖SC=E\setminus SC=E∖S. Write di=inf⁡y∈C∥ξi−y∥d_i=\inf_{y\in C}\|\xi_i-y\|di​=infy∈C​∥ξi​−y∥, P^=N−1∑iδξi\widehat P=N^{-1}\sum_i\delta_{\xi_i}P=N−1∑i​δξi​​, and F(θ)={P a Borel probability law:W1(P^,P)≤θ}\mathcal F(\theta)=\{P\text{ a Borel probability law}:W_1(\widehat P,P)\le\theta\}F(θ)={P a Borel probability law:W1​(P,P)≤θ}, where W1W_1W1​ is the infimum of the expected norm cost over all couplings. Assume θ>0\theta>0θ>0.

Assume the samples are ordered so that d1≤⋯≤dNd_1\le\cdots\le d_Nd1​≤⋯≤dN​. Choose any ηi∈C\eta_i\in Cηi​∈C satisfying ∥ξi−ηi∥=di\|\xi_i-\eta_i\|=d_i∥ξi​−ηi​∥=di​. Let III be the number of zero distances, D(j)=∑i=1jdiD(j)=\sum_{i=1}^j d_iD(j)=∑i=1j​di​, and j∗=max⁡{j∈{0,…,N}:D(j)≤θN}j^*=\max\{j\in\{0,\ldots,N\}:D(j)\le\theta N\}j∗=max{j∈{0,…,N}:D(j)≤θN}. When j∗<Nj^*<Nj∗<N, let p∗=(θN−D(j∗))/dj∗+1p^*=(\theta N-D(j^*))/d_{j^*+1}p∗=(θN−D(j∗))/dj∗+1​. Define P∗P^*P∗ by the corresponding atomic law below. Then P∗P^*P∗ is a probability law in F(θ)\mathcal F(\theta)F(θ) and attains the worst unsafe probability:

sup⁡P∈F(θ)P(C)=P∗(C).\sup_{P\in\mathcal F(\theta)}P(C)=P^*(C).P∈F(θ)sup​P(C)=P∗(C).

If j∗=Nj^*=Nj∗=N, then

P∗=1N∑i=1Iδξi+1N∑i=I+1Nδηi,P∗(C)=1.P^*=\frac1N\sum_{i=1}^{I}\delta_{\xi_i}+\frac1N\sum_{i=I+1}^{N}\delta_{\eta_i},\qquad P^*(C)=1.P∗=N1​i=1∑I​δξi​​+N1​i=I+1∑N​δηi​​,P∗(C)=1.

If j∗<Nj^*<Nj∗<N, then

P∗=1N∑i=1Iδξi+1N∑i=I+1j∗δηi+p∗Nδηj∗+1+1−p∗Nδξj∗+1+1N∑i=j∗+2Nδξi,P∗(C)=j∗+p∗N.P^*=\frac1N\sum_{i=1}^{I}\delta_{\xi_i}+\frac1N\sum_{i=I+1}^{j^*}\delta_{\eta_i}+\frac{p^*}{N}\delta_{\eta_{j^*+1}}+\frac{1-p^*}{N}\delta_{\xi_{j^*+1}}+\frac1N\sum_{i=j^*+2}^{N}\delta_{\xi_i},\qquad P^*(C)=\frac{j^*+p^*}{N}.P∗=N1​i=1∑I​δξi​​+N1​i=I+1∑j∗​δηi​​+Np∗​δηj∗+1​​+N1−p∗​δξj∗+1​​+N1​i=j∗+2∑N​δξi​​,P∗(C)=Nj∗+p∗​.

The paper reproduces this previously established uncertainty-quantification result without proof. The assertion includes the full attaining law, not merely its value.

Formalization Note The nonempty unsafe set makes explicit the paper's implicit nearest-point convention (finding F1). Safety may be empty. Nearest-point selections are arbitrary and need not be unique; their existence follows from closedness, nonemptiness and finite dimension. All probability suprema and transport integrals are extended nonnegative values. No epsilon is needed in this uncertainty-quantification statement. The defined greedy law, rather than an assumed optimal law, occurs in the conclusion.

Preamble
import Mathlib
import Definitions.Def_ChenWasserstein_Reform_Data

open MeasureTheory
open scoped ENNReal BigOperators
Formal statement
/- Imported declaration bodies, quoted verbatim for standalone blind auditing.
These are comments, not redeclarations or additional assumptions.

noncomputable def distUnsafe {E : Type*} [NormedAddCommGroup E] (S : Set E) (u : E) : ℝ :=
  Metric.infDist u Sᶜ

noncomputable def kthSmallest {N : ℕ} (v : Fin N → ℝ) (j : ℕ) : ℝ :=
  ((Finset.univ.val.map v).sort (· ≤ ·)).getD j 0

def IsCoupling {S : Type*} [MeasurableSpace S] (μ₁ μ₂ : Measure S) (π : Measure (S × S)) : Prop :=
  IsProbabilityMeasure π ∧ π.map Prod.fst = μ₁ ∧ π.map Prod.snd = μ₂

noncomputable def transportCost {S : Type*} [MeasurableSpace S] (c : S → S → ℝ)
    (μ₁ μ₂ : Measure S) : ℝ≥0∞ :=
  ⨅ (π : Measure (S × S)) (_ : IsCoupling μ₁ μ₂ π), ∫⁻ p, ENNReal.ofReal (c p.1 p.2) ∂π

noncomputable def worstProb {S : Type*} [MeasurableSpace S] (c : S → S → ℝ) (μ : Measure S)
    (δ : ℝ) (A : Set S) : ℝ≥0∞ :=
  ⨆ (P : Measure S) (_ : IsProbabilityMeasure P ∧ transportCost c μ P ≤ ENNReal.ofReal δ), P A

noncomputable def empiricalDistribution {E : Type*} [MeasurableSpace E] {N : ℕ}
    (ξhat : Fin N → E) : Measure E :=
  (N : ENNReal)⁻¹ • ∑ i, Measure.dirac (ξhat i)

noncomputable def prefixSum {N : ℕ} (d : Fin N → ℝ) (j : ℕ) : ℝ :=
  ∑ i : Fin N, if i.val < j then d i else 0

noncomputable def zeroCount {N : ℕ} (d : Fin N → ℝ) : ℕ :=
  (Finset.univ.filter (fun i => d i = 0)).card

noncomputable def jStar {N : ℕ} (d : Fin N → ℝ) (θ : ℝ) : ℕ :=
  ((Finset.range (N + 1)).filter (fun j => prefixSum d j ≤ θ * (N : ℝ))).sup id

noncomputable def pStar {N : ℕ} (d : Fin N → ℝ) (θ : ℝ) : ℝ :=
  if h : jStar d θ < N then
    (θ * (N : ℝ) - prefixSum d (jStar d θ)) / d ⟨jStar d θ, h⟩
  else 0

noncomputable def fullLaw {E : Type*} [MeasurableSpace E] {N : ℕ}
    (ξ η : Fin N → E) (d : Fin N → ℝ) : Measure E :=
  (N : ℝ≥0∞)⁻¹ • ∑ i : Fin N,
    if i.val < zeroCount d then Measure.dirac (ξ i) else Measure.dirac (η i)

noncomputable def partialLaw {E : Type*} [MeasurableSpace E] {N : ℕ}
    (ξ η : Fin N → E) (d : Fin N → ℝ) (θ : ℝ) : Measure E :=
  (N : ℝ≥0∞)⁻¹ • ∑ i : Fin N,
    if i.val < zeroCount d then Measure.dirac (ξ i)
    else if i.val < jStar d θ then Measure.dirac (η i)
    else if i.val = jStar d θ then
      ENNReal.ofReal (pStar d θ) • Measure.dirac (η i) +
        ENNReal.ofReal (1 - pStar d θ) • Measure.dirac (ξ i)
    else Measure.dirac (ξ i)

noncomputable def greedyLaw {E : Type*} [MeasurableSpace E] {N : ℕ}
    (ξ η : Fin N → E) (d : Fin N → ℝ) (θ : ℝ) : Measure E :=
  if jStar d θ = N then fullLaw ξ η d else partialLaw ξ η d θ
-/

namespace ChenWasserstein.Reform

/-- Chen, Kuhn and Wiesemann (2024), Theorem 1, printed p. 413 / PDF p. 4.
The samples are ordered by distance. η is any selection of closest unsafe points.
The nonempty complement states the source's implicit nearest-point domain. -/
theorem theorem_1
    {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E]
    [MeasurableSpace E] [BorelSpace E] {N : ℕ}
    (ξ η : Fin N → E) (S : Set E) (θ : ℝ)
    (hN : 0 < N) (hθ : 0 < θ) (hS : IsOpen S) (hC : Sᶜ.Nonempty)
    (horder : Monotone (fun i => WassDRCCP.Improved.distUnsafe S (ξ i)))
    (hη : ∀ i, η i ∈ Sᶜ ∧ ‖ξ i - η i‖ = WassDRCCP.Improved.distUnsafe S (ξ i)) :
    let d := fun i => WassDRCCP.Improved.distUnsafe S (ξ i)
    let P := greedyLaw ξ η d θ
    IsProbabilityMeasure P ∧
    ModelRiskOT.WorstProb.transportCost (fun u v : E => ‖u - v‖)
      (WassersteinDRO.Duality.empiricalDistribution ξ) P ≤ ENNReal.ofReal θ ∧
    ModelRiskOT.WorstProb.worstProb (fun u v : E => ‖u - v‖)
      (WassersteinDRO.Duality.empiricalDistribution ξ) θ Sᶜ = P Sᶜ ∧
    (jStar d θ = N → P = fullLaw ξ η d ∧ P Sᶜ = 1) ∧
    (jStar d θ < N → P = partialLaw ξ η d θ ∧
      P Sᶜ = ENNReal.ofReal (((jStar d θ : ℕ) : ℝ) + pStar d θ) / (N : ℝ≥0∞)) := by sorry

end ChenWasserstein.Reform
Source
Chen, Kuhn and Wiesemann, Technical Note—Data-Driven Chance Constrained Programs over Wasserstein Balls, Operations Research 72(1) (2024), 410–424, https://doi.org/10.1287/opre.2022.2330, Theorem 1, printed p. 413, PDF p. 4
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Setting.

  • EEE is a finite-dimensional real normed vector space with its Borel σ-algebra, and NNN is a natural number.
  • ξ=(ξ0,…,ξN−1)\xi=(\xi_0,\dots,\xi_{N-1})ξ=(ξ0​,…,ξN−1​) and η=(η0,…,ηN−1)\eta=(\eta_0,\dots,\eta_{N-1})η=(η0​,…,ηN−1​) are points of EEE, S⊆ES\subseteq ES⊆E is a set, and θ\thetaθ is a real number.

Hypotheses.

  • N>0N>0N>0 and θ>0\theta>0θ>0.
  • SSS is open, and its complement ScS^cSc is nonempty. Since SSS is open, ScS^cSc is closed.
  • Set di=dist⁡(ξi,Sc)=inf⁡u∈Sc∥ξi−u∥d_i=\operatorname{dist}(\xi_i,S^c)=\inf_{u\in S^c}\|\xi_i-u\|di​=dist(ξi​,Sc)=infu∈Sc​∥ξi​−u∥. The sequence d0≤d1≤⋯≤dN−1d_0\le d_1\le\dots\le d_{N-1}d0​≤d1​≤⋯≤dN−1​ is nondecreasing in the index.
  • For every iii, ηi∈Sc\eta_i\in S^cηi​∈Sc and ∥ξi−ηi∥=di\|\xi_i-\eta_i\|=d_i∥ξi​−ηi​∥=di​. So each ηi\eta_iηi​ is a nearest point of ScS^cSc to ξi\xi_iξi​.

Notation used in the conclusion.

  • P^N=1N∑iδξi\hat P_N=\frac1N\sum_i\delta_{\xi_i}P^N​=N1​∑i​δξi​​ is the empirical measure.
  • PPP is the greedy law of (ξ,η,d,θ)(\xi,\eta,d,\theta)(ξ,η,d,θ), with all ingredients expanded:
    • I=#{i:di=0}I=\#\{i: d_i=0\}I=#{i:di​=0}.
    • j⋆=max⁡{ j∈{0,…,N}:∑i<jdi≤θN }j^\star=\max\{\, j\in\{0,\dots,N\}: \sum_{i<j} d_i\le\theta N\,\}j⋆=max{j∈{0,…,N}:∑i<j​di​≤θN}, or 000 if that set is empty.
    • If j⋆<Nj^\star<Nj⋆<N, then p⋆=(θN−∑i<j⋆di)/dj⋆p^\star=(\theta N-\sum_{i<j^\star}d_i)/d_{j^\star}p⋆=(θN−∑i<j⋆​di​)/dj⋆​, which is 000 if dj⋆=0d_{j^\star}=0dj⋆​=0. If j⋆=Nj^\star=Nj⋆=N, then p⋆=0p^\star=0p⋆=0.
    • If j⋆=Nj^\star=Nj⋆=N:
P=fullLaw=1N(∑i<Iδξi+∑i≥Iδηi).P=\mathrm{fullLaw}=\frac1N\Big(\sum_{i<I}\delta_{\xi_i}+\sum_{i\ge I}\delta_{\eta_i}\Big).P=fullLaw=N1​(i<I∑​δξi​​+i≥I∑​δηi​​).
  • Otherwise P=partialLaw=1N∑iμiP=\mathrm{partialLaw}=\frac1N\sum_i\mu_iP=partialLaw=N1​∑i​μi​. Here μi=δξi\mu_i=\delta_{\xi_i}μi​=δξi​​ for i<Ii<Ii<I. Otherwise μi=δηi\mu_i=\delta_{\eta_i}μi​=δηi​​ for i<j⋆i<j^\stari<j⋆. Otherwise μi=[p⋆]+δηi+[1−p⋆]+δξi\mu_i=[p^\star]_+\delta_{\eta_i}+[1-p^\star]_+\delta_{\xi_i}μi​=[p⋆]+​δηi​​+[1−p⋆]+​δξi​​ for i=j⋆i=j^\stari=j⋆. Otherwise μi=δξi\mu_i=\delta_{\xi_i}μi​=δξi​​.
  • The transport cost between two measures μ,ν\mu,\nuμ,ν on EEE is
W(μ,ν)=inf⁡π∫∥u−v∥ dπ(u,v),W(\mu,\nu)=\inf_\pi\int\|u-v\|\,d\pi(u,v),W(μ,ν)=πinf​∫∥u−v∥dπ(u,v),

a value in [0,∞][0,\infty][0,∞]. The infimum is over couplings π\piπ: probability measures on E×EE\times EE×E whose first marginal is μ\muμ and second marginal is ν\nuν. An infimum over no couplings is +∞+\infty+∞.

  • The worst-case probability of a set AAA is
WP(A)=sup⁡{ Q(A):Q a Borel probability measure on E, W(P^N,Q)≤θ }.\mathrm{WP}(A)=\sup\{\,Q(A): Q \text{ a Borel probability measure on } E,\ W(\hat P_N,Q)\le\theta\,\}.WP(A)=sup{Q(A):Q a Borel probability measure on E, W(P^N​,Q)≤θ}.

Conclusion. All five of the following hold:

  1. PPP is a probability measure.
  2. W(P^N,P)≤θW(\hat P_N,P)\le\thetaW(P^N​,P)≤θ.
  3. WP(Sc)=P(Sc)\mathrm{WP}(S^c)=P(S^c)WP(Sc)=P(Sc), so the supremum is attained at PPP. This is an equality in [0,∞][0,\infty][0,∞].
  4. If j⋆=Nj^\star=Nj⋆=N, then P=fullLaw(ξ,η,d)P=\mathrm{fullLaw}(\xi,\eta,d)P=fullLaw(ξ,η,d) and P(Sc)=1P(S^c)=1P(Sc)=1.
  5. If j⋆<Nj^\star<Nj⋆<N, then P=partialLaw(ξ,η,d,θ)P=\mathrm{partialLaw}(\xi,\eta,d,\theta)P=partialLaw(ξ,η,d,θ) and
P(Sc)=[ j⋆+p⋆ ]+N.P(S^c)=\frac{[\,j^\star+p^\star\,]_+}{N}.P(Sc)=N[j⋆+p⋆]+​​.

Since j⋆≤Nj^\star\le Nj⋆≤N always, exactly one of items 4 and 5 applies.

Degenerate cases:

  • N=0N=0N=0 and θ≤0\theta\le0θ≤0. Both are excluded by the hypotheses.
  • N=1N=1N=1. There is a single sample. Then j⋆∈{0,1}j^\star\in\{0,1\}j⋆∈{0,1}, and j⋆=1j^\star=1j⋆=1 exactly when d0≤θd_0\le\thetad0​≤θ.
  • Zero-dimensional EEE. If E={0}E=\{0\}E={0}, the only open set with nonempty complement is S=∅S=\emptysetS=∅. Then Sc=ES^c=ESc=E, every di=0d_i=0di​=0, I=NI=NI=N, and ηi=ξi\eta_i=\xi_iηi​=ξi​.
  • Index order. The statement uses ∑i<jdi\sum_{i<j}d_i∑i<j​di​ in index order and the position test i<Ii<Ii<I. Under the monotonicity hypothesis, these index positions coincide with sorted positions.
  • Division by zero. If j⋆<Nj^\star<Nj⋆<N and dj⋆=0d_{j^\star}=0dj⋆​=0, then p⋆p^\starp⋆ is defined to be 000.
  • Automatic consequences. The statement does not separately assume 0≤p⋆≤10\le p^\star\le10≤p⋆≤1. Item 1 nevertheless asserts that PPP has total mass exactly 111, and that includes the mass [p⋆]++[1−p⋆]+[p^\star]_++[1-p^\star]_+[p⋆]+​+[1−p⋆]+​ carried by index j⋆j^\starj⋆ when j⋆≥Ij^\star\ge Ij⋆≥I. The hypothesis on η\etaη can be satisfied, because ScS^cSc is closed and nonempty in a finite-dimensional space, so nearest points exist.
Human review
  • Endorsed by Community (Bot) · Oct 29, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Oct 29, 2026

    Confirmed by the mission captain (proposal self-audit).

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