Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§10.7, p. 39 — W_N² − U_N² = ((1/N)ΣF₀(ξ^(i)) − 1/2)² ≤ max{…} in terms of D′_N(F₀)

Proved
RobustSAA.Univariate.watson_bound

by mikedeng1 · Oct 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

cramer-von-misesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1watson

Let N≥1N\ge1N≥1, let ξ1,…,ξN∈R\xi^1,\dots,\xi^N\in\mathbb Rξ1,…,ξN∈R have order statistics ξ(1)≤⋯≤ξ(N)\xi^{(1)}\le\dots\le\xi^{(N)}ξ(1)≤⋯≤ξ(N), let F0F_0F0​ be a probability distribution on R\mathbb RR, and let DN′(F0)=max⁡i∣F0(ξ(i))−2i−12N∣D'_N(F_0)=\max_i|F_0(\xi^{(i)})-\tfrac{2i-1}{2N}|DN′​(F0​)=maxi​∣F0​(ξ(i))−2N2i−1​∣. With WNW_NWN​ the Cramér–von Mises and UNU_NUN​ the Watson statistic (8),

WN2−UN2=(1N∑i=1NF0(ξ(i))−12)2≤max⁡{(1N∑i=1Nmin⁡{1,2i−12N+DN′(F0)}−12)2, (1N∑i=1Nmax⁡{0,2i−12N−DN′(F0)}−12)2}.\begin{aligned} W_N^2-U_N^2&=\Big(\frac1N\sum_{i=1}^NF_0(\xi^{(i)})-\frac12\Big)^2\\ &\le\max\Big\{\Big(\frac1N\sum_{i=1}^N\min\Big\{1,\frac{2i-1}{2N}+D'_N(F_0)\Big\}-\frac12\Big)^2,\ \Big(\frac1N\sum_{i=1}^N\max\Big\{0,\frac{2i-1}{2N}-D'_N(F_0)\Big\}-\frac12\Big)^2\Big\}. \end{aligned}WN2​−UN2​​=(N1​i=1∑N​F0​(ξ(i))−21​)2≤max{(N1​i=1∑N​min{1,2N2i−1​+DN′​(F0​)}−21​)2, (N1​i=1∑N​max{0,2N2i−1​−DN′​(F0​)}−21​)2}.​

This controls the centring term by which the Watson statistic differs from the CvM statistic.

Formalization Note Lean indices are 0-based (Lean's i is the paper's i+1i+1i+1), and the order statistics are the sorted sample s ∘ Tuple.sort s. The statement assumes N≥1N\ge1N≥1, which the paper's statistics presuppose.

Preamble
import Mathlib
import Definitions.Def_RobustSAA_Univariate_Setting
Formal statement
namespace RobustSAA.Univariate

open Filter MeasureTheory

/-- §10.7, p. 39: `W_N² − U_N² = ((1/N) Σ F₀(ξ^(i)) − 1/2)²`, which is at most the larger of the
two squared extremes obtained from `|F₀(ξ^(i)) − (2i−1)/(2N)| ≤ D′_N(F₀)` and `0 ≤ F₀ ≤ 1`. -/
theorem watson_bound {N : ℕ} (hN : 0 < N) (F₀ : ProbabilityMeasure ℝ) (s : Fin N → ℝ) :
    cvmStat F₀ s ^ 2 - watsonStat F₀ s ^ 2 = meanDev F₀ s ^ 2 ∧
    meanDev F₀ s ^ 2 ≤
      max ((1 / (N : ℝ) * ∑ i : Fin N,
              min 1 ((2 * ((i : ℕ) + 1 : ℝ) - 1) / (2 * N) + Dprime F₀ s) - 1 / 2) ^ 2)
          ((1 / (N : ℝ) * ∑ i : Fin N,
              max 0 ((2 * ((i : ℕ) + 1 : ℝ) - 1) / (2 * N) - Dprime F₀ s) - 1 / 2) ^ 2) := by sorry

end RobustSAA.Univariate
Source
Bertsimas, Gupta, Kallus, Robust Sample Average Approximation, arXiv:1408.4445v3, §10.7, proof of Theorem 5, p. 39, display before "Letting M"
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 8, 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