Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 2.3, (2.8), p. 5 — √N(v̂_N − v*) ⇒ min_{x∈𝒮*} Y(x), Y a centered Gaussian vector with the autocovariance of G(x, W)

Proved
KleywegtSAA.ValueCLT.proposition_2_3

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

central-limit-theoremp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sample-average-approximationstochastic-programming

Consider the stochastic program min⁡x∈S{g(x)=E G(x,W)}\min_{x \in \mathcal S} \{ g(x) = \mathbb E\, G(x, W) \}minx∈S​{g(x)=EG(x,W)} of (1.1) over a nonempty finite set S\mathcal SS, where for every x∈Sx \in \mathcal Sx∈S the function G(x,⋅)G(x, \cdot)G(x,⋅) is measurable and E ∣G(x,W)∣<∞\mathbb E\,|G(x, W)| < \inftyE∣G(x,W)∣<∞. Let W1,W2,…W^1, W^2, \dotsW1,W2,… be an i.i.d. sample of WWW, let

g^N(x)=1N∑n=1NG(x,Wn),v^N=min⁡x∈Sg^N(x),v∗=min⁡x∈Sg(x),\hat g_N(x) = \frac1N \sum_{n=1}^N G(x, W^n), \qquad \hat v_N = \min_{x \in \mathcal S} \hat g_N(x), \qquad v^* = \min_{x \in \mathcal S} g(x),g^​N​(x)=N1​n=1∑N​G(x,Wn),v^N​=x∈Smin​g^​N​(x),v∗=x∈Smin​g(x),

and let S∗\mathcal S^*S∗ be the set of optimal solutions of (1.1).

Proposition 2.3. Suppose that the variances σ2(x)=Var⁡{G(x,W)}\sigma^2(x) = \operatorname{Var}\{G(x, W)\}σ2(x)=Var{G(x,W)} exist for every x∈S∗x \in \mathcal S^*x∈S∗. Then

N (v^N−v∗)  ⇒  min⁡x∈S∗Y(x),(2.8)\sqrt N\,(\hat v_N - v^*) \;\Rightarrow\; \min_{x \in \mathcal S^*} Y(x), \tag{2.8}N​(v^N​−v∗)⇒x∈S∗min​Y(x),(2.8)

where ⇒\Rightarrow⇒ denotes convergence in distribution and (Y(x))x∈S∗(Y(x))_{x \in \mathcal S^*}(Y(x))x∈S∗​ is a Gaussian random vector with zero mean and the autocovariance function of G(x,W)G(x, W)G(x,W): Cov⁡(Y(x),Y(x′))=Cov⁡(G(x,W),G(x′,W))\operatorname{Cov}(Y(x), Y(x')) = \operatorname{Cov}(G(x, W), G(x', W))Cov(Y(x),Y(x′))=Cov(G(x,W),G(x′,W)) for x,x′∈S∗x, x' \in \mathcal S^*x,x′∈S∗.

The result gives the first-order asymptotic distribution of the SAA estimator of the optimal value of a discrete stochastic program. When the true problem has several optimal solutions, the limit is the minimum of a correlated Gaussian vector, which has negative mean; so v^N\hat v_Nv^N​ is biased downward at the order N−1/2N^{-1/2}N−1/2.

Formalization Note The limit is any random vector YYY, on any probability space, whose law is the multivariate Gaussian measure on RS∗\mathbb R^{\mathcal S^*}RS∗ with mean 000 and covariance matrix (Cov⁡(G(x,W),G(x′,W)))x,x′∈S∗\big(\operatorname{Cov}(G(x, W), G(x', W))\big)_{x, x' \in \mathcal S^*}(Cov(G(x,W),G(x′,W)))x,x′∈S∗​; this matrix is positive semidefinite under the variance hypothesis, so the Gaussian law is the genuine one. The vector is indexed by S∗\mathcal S^*S∗, not by S\mathcal SS. "The variance exists" is square integrability of G(x,W)G(x, W)G(x,W), assumed only on S∗\mathcal S^*S∗ as in the Proposition; off S∗\mathcal S^*S∗ only the integrability of (1.1) is assumed. "G(x,⋅)G(x, \cdot)G(x,⋅) is PPP-measurable" is read as Borel measurability. The sample is a 000-indexed sequence of independent random elements, each with the law of the first one.

Preamble
import Mathlib
import Definitions.Def_KleywegtSAA_ValueCLT_Setting
Formal statement
namespace KleywegtSAA.ValueCLT

open MeasureTheory ProbabilityTheory Filter Topology

open Classical in
/-- Kleywegt–Shapiro, Proposition 2.3, (2.8), p. 5: if the variances `σ²(x) = Var G(x, W)` exist
for every `x ∈ S*`, then `√N (v̂_N − v*) ⇒ min_{x ∈ S*} Y(x)`, where `(Y(x))_{x ∈ S*}` is a
centered Gaussian vector with the autocovariance function of `G(x, W)`. -/
theorem proposition_2_3
    {X : Type*} (S : Finset X) (hS : S.Nonempty)
    {𝒲 : Type*} [MeasurableSpace 𝒲] (G : X → 𝒲 → ℝ) (hG : ∀ x ∈ S, Measurable (G x))
    {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
    (W : ℕ → Ω → 𝒲) (hWm : ∀ n, Measurable (W n)) (hind : iIndepFun W P)
    (hid : ∀ n, IdentDistrib (W n) (W 0) P P)
    (hint : ∀ x ∈ S, Integrable (fun ω => G x (W 0 ω)) P)
    (hvar : ∀ x ∈ optSet S hS (KleywegtSAA.ExpRate.trueObj G P W), MemLp (fun ω => G x (W 0 ω)) 2 P) :
    ∀ {Ω' : Type*} [MeasurableSpace Ω'] (Q : Measure Ω') [IsProbabilityMeasure Q]
      (Y : Ω' → EuclideanSpace ℝ (optSet S hS (KleywegtSAA.ExpRate.trueObj G P W))),
      HasLaw Y (multivariateGaussian 0 (covMat G P W (optSet S hS (KleywegtSAA.ExpRate.trueObj G P W)))) Q →
      TendstoInDistribution
        (fun (N : ℕ) ω => Real.sqrt N * (S.inf' hS (KleywegtSAA.ExpRate.sampleObj G W N ω) - S.inf' hS (KleywegtSAA.ExpRate.trueObj G P W)))
        atTop
        (fun ω' => Finset.univ.inf'
          (Finset.univ_nonempty_iff.2 (optSet_nonempty S hS (KleywegtSAA.ExpRate.trueObj G P W)).to_subtype)
          (fun x => Y ω' x))
        (fun _ => P) Q := by sorry

end KleywegtSAA.ValueCLT
Source
Kleywegt & Shapiro, The sample average approximation method for stochastic discrete optimization, preprint (two-author version, sha256 56657748…), p. 5, Proposition 2.3, (2.8); standing assumptions p. 1 (1.1) and p. 2 (2.1)
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

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