§10.7, p. 39 — W_N² − U_N² = ((1/N)ΣF₀(ξ^(i)) − 1/2)² ≤ max{…} in terms of D′_N(F₀)
ProvedRobustSAA.Univariate.watson_boundcramer-von-misesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1watson
Let , let have order statistics , let be a probability distribution on , and let . With the Cramér–von Mises and the Watson statistic (8),
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 ), and the order statistics are the sorted sample s ∘ Tuple.sort s. The statement assumes , 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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.