Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.1 — the multilevel estimator reaches MSE <ε2<\varepsilon^2<ε2 at cost c4ε−2c_4\varepsilon^{-2}c4​ε−2, c4ε−2(log⁡ε)2c_4\varepsilon^{-2}(\log\varepsilon)^2c4​ε−2(logε)2 or c4ε−2−(1−β)/αc_4\varepsilon^{-2-(1-\beta)/\alpha}c4​ε−2−(1−β)/α

Proved
GilesMLMC.Complexity.theorem_3_1

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

complexitymultilevel-monte-carlop2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1simulation

Complexity theorem for multilevel Monte Carlo. Let (Ω,F,μ)(\Omega,\mathcal F,\mu)(Ω,F,μ) be a probability space, PPP an integrable random variable (in the paper, a functional of the solution of an SDE for a given Brownian path) and P^l\widehat P_lPl​, l≥0l\ge0l≥0, integrable random variables (its approximations with timestep hl=M−lTh_l=M^{-l}Thl​=M−lT, where M≥2M\ge2M≥2 is an integer and T>0T>0T>0). For every level lll and every sample size n≥1n\ge1n≥1 let Y^l(n)\widehat Y_l^{(n)}Yl(n)​ be a square-integrable estimator based on nnn Monte Carlo samples, with computational complexity Cl(n)C_l^{(n)}Cl(n)​. Suppose there are constants α≥12\alpha\ge\frac12α≥21​ and β,c1,c2,c3>0\beta,c_1,c_2,c_3>0β,c1​,c2​,c3​>0 such that, for every lll and every n≥1n\ge1n≥1,

  1. (i) ∣E[P^l−P]∣≤c1hlα\big|E[\widehat P_l-P]\big|\le c_1h_l^\alpha​E[Pl​−P]​≤c1​hlα​;
  2. (ii) E[Y^l(n)]=E[P^0]E[\widehat Y_l^{(n)}]=E[\widehat P_0]E[Yl(n)​]=E[P0​] if l=0l=0l=0, and E[Y^l(n)]=E[P^l−P^l−1]E[\widehat Y_l^{(n)}]=E[\widehat P_l-\widehat P_{l-1}]E[Yl(n)​]=E[Pl​−Pl−1​] if l>0l>0l>0;
  3. (iii) V[Y^l(n)]≤c2 n−1hlβV[\widehat Y_l^{(n)}]\le c_2\,n^{-1}h_l^\betaV[Yl(n)​]≤c2​n−1hlβ​;
  4. (iv) Cl(n)≤c3 n hl−1C_l^{(n)}\le c_3\,n\,h_l^{-1}Cl(n)​≤c3​nhl−1​;

and that for every choice of sample sizes N0,N1,⋯≥1N_0,N_1,\dots\ge1N0​,N1​,⋯≥1 the estimators Y^l(Nl)\widehat Y_l^{(N_l)}Yl(Nl​)​ are independent. Then there is a constant c4>0c_4>0c4​>0 such that for every 0<ε<e−10<\varepsilon<e^{-1}0<ε<e−1 there are a finest level LLL and sample sizes Nl≥1N_l\ge1Nl​≥1 for which the multilevel estimator Y^=∑l=0LY^l(Nl)\widehat Y=\sum_{l=0}^L\widehat Y_l^{(N_l)}Y=∑l=0L​Yl(Nl​)​ has

MSE≡E[(Y^−E[P])2]<ε2,\mathrm{MSE}\equiv E\big[(\widehat Y-E[P])^2\big]<\varepsilon^2,MSE≡E[(Y−E[P])2]<ε2,

with a computational complexity C=∑l=0LCl(Nl)C=\sum_{l=0}^LC_l^{(N_l)}C=∑l=0L​Cl(Nl​)​ bounded by

C≤{c4ε−2,β>1,c4ε−2(log⁡ε)2,β=1,c4ε−2−(1−β)/α,0<β<1.C\le\begin{cases}c_4\varepsilon^{-2},&\beta>1,\\ c_4\varepsilon^{-2}(\log\varepsilon)^2,&\beta=1,\\ c_4\varepsilon^{-2-(1-\beta)/\alpha},&0<\beta<1.\end{cases}C≤⎩⎨⎧​c4​ε−2,c4​ε−2(logε)2,c4​ε−2−(1−β)/α,​β>1,β=1,0<β<1.​

Plain Monte Carlo with an Euler discretisation needs cost of order ε−3\varepsilon^{-3}ε−3 for the same accuracy; the theorem shows that the multilevel estimator reaches the cost ε−2\varepsilon^{-2}ε−2 of an unbiased estimator when β>1\beta>1β>1, loses only a factor (log⁡ε)2(\log\varepsilon)^2(logε)2 when β=1\beta=1β=1 (the Euler scheme with a Lipschitz payoff), and gives an explicit rate otherwise.

Formalization Note PPP and P^l\widehat P_lPl​ are arbitrary random variables; in the paper they come from an SDE and its discretisation, which the theorem uses only through (i)–(iv). This makes the statement more general, not weaker. Hypotheses (ii)–(iv), square integrability and independence are assumed for every sample size n≥1n\ge1n≥1, because the theorem chooses the sample sizes. Hypothesis (i) carries an absolute value: the page prints the one-sided E[P^l−P]≤c1hlαE[\widehat P_l-P]\le c_1h_l^\alphaE[Pl​−P]≤c1​hlα​, under which the theorem is false (take E[P^l−P]=−1E[\widehat P_l-P]=-1E[Pl​−P]=−1 for every lll); the proof uses the two-sided bound. M≥2M\ge2M≥2 is the paper's standing "integer M⩾2M\geqslant2M⩾2" (§1), ε>0\varepsilon>0ε>0 is implicit. The complexity CCC is the sum of the level complexities, each constrained only by (iv). Since β\betaβ is fixed by the hypotheses, one constant c4c_4c4​ serves; it does not depend on ε\varepsilonε, LLL or NlN_lNl​.

Preamble
import Mathlib
import Definitions.Def_GilesMLMC_Complexity_Setup
Formal statement
namespace GilesMLMC.Complexity

/-- **Theorem 3.1** (Giles 2008, Multilevel Monte Carlo path simulation, Operations Research
56(3), §3, p. 609, PDF 3, left column).

Formalization Note. `P` and `Phat l` (= P̂_l) are arbitrary real random variables on a
probability space; in the paper they come from an SDE and its discretisation with timestep
`h_l = M^{-l} T`, which the theorem uses only through (i)–(iv), so the statement is more
general, not weaker. `Y l n` is the level-`l` estimator Ŷ_l built from `n` samples and
`cost l n` its computational complexity C_l; since the theorem chooses the sample sizes,
(ii)–(iv), square integrability and independence are assumed for every sample size `n ≥ 1`.
Hypothesis (i) carries an absolute value: the page prints `E[P̂_l − P] ≤ c₁ h_l^α`, which
would make the theorem false (take `E[P̂_l − P] = −1`); the proof uses the two-sided bound.
`P`, `P̂_l` are integrable and every `Ŷ_l` is in L² (otherwise `∫` and `variance` take
junk value 0). `M ≥ 2` is the paper's standing "integer M ⩾ 2" (§1, p. 607); `T > 0`; `ε > 0`
is implicit in "ε < e⁻¹". The computational complexity `C` of Ŷ is `Σ_{l=0}^L C_l`. Since `β` is
fixed by the hypotheses, one `c₄` serves; the three implications are the three cases of the
paper's display. Real powers are `Real.rpow`. -/
theorem theorem_3_1
    {Ω : Type*} [MeasurableSpace Ω] (μ : MeasureTheory.Measure Ω)
    [MeasureTheory.IsProbabilityMeasure μ]
    (M : ℕ) (hM : 2 ≤ M) (T : ℝ) (hT : 0 < T)
    (α β c₁ c₂ c₃ : ℝ) (hα : 1 / 2 ≤ α) (hβ : 0 < β)
    (hc₁ : 0 < c₁) (hc₂ : 0 < c₂) (hc₃ : 0 < c₃)
    (P : Ω → ℝ) (Phat : ℕ → Ω → ℝ) (Y : ℕ → ℕ → Ω → ℝ) (cost : ℕ → ℕ → ℝ)
    (hP : MeasureTheory.Integrable P μ)
    (hPhat : ∀ l, MeasureTheory.Integrable (Phat l) μ)
    (hY : ∀ l N, 1 ≤ N → MeasureTheory.MemLp (Y l N) 2 μ)
    (h_i : ∀ l, |∫ ω, (Phat l ω - P ω) ∂μ| ≤ c₁ * h M T l ^ α)
    (h_ii : ∀ l N, 1 ≤ N → ∫ ω, Y l N ω ∂μ =
      if l = 0 then ∫ ω, Phat 0 ω ∂μ else ∫ ω, (Phat l ω - Phat (l - 1) ω) ∂μ)
    (h_iii : ∀ l N, 1 ≤ N →
      ProbabilityTheory.variance (Y l N) μ ≤ c₂ * (N : ℝ)⁻¹ * h M T l ^ β)
    (h_iv : ∀ l N, 1 ≤ N → cost l N ≤ c₃ * N * (h M T l)⁻¹)
    (h_indep : ∀ N : ℕ → ℕ, (∀ l, 1 ≤ N l) →
      ProbabilityTheory.iIndepFun (fun l => Y l (N l)) μ) :
    ∃ c₄ : ℝ, 0 < c₄ ∧ ∀ ε : ℝ, 0 < ε → ε < Real.exp (-1) →
      ∃ (L : ℕ) (N : ℕ → ℕ), (∀ l, 1 ≤ N l) ∧
        mse μ (estimator Y N L) P < ε ^ 2 ∧
        (1 < β → totalCost cost N L ≤ c₄ * ε ^ (-2 : ℝ)) ∧
        (β = 1 → totalCost cost N L ≤ c₄ * ε ^ (-2 : ℝ) * Real.log ε ^ 2) ∧
        (β < 1 → totalCost cost N L ≤ c₄ * ε ^ (-2 - (1 - β) / α)) := by sorry

end GilesMLMC.Complexity
Source
Giles, Multilevel Monte Carlo path simulation, Operations Research 56(3) (2008), Theorem 3.1, §3, p. 609
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

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