Theorem 3.1 — the multilevel estimator reaches MSE at cost , or
ProvedGilesMLMC.Complexity.theorem_3_1Complexity theorem for multilevel Monte Carlo. Let be a probability space, an integrable random variable (in the paper, a functional of the solution of an SDE for a given Brownian path) and , , integrable random variables (its approximations with timestep , where is an integer and ). For every level and every sample size let be a square-integrable estimator based on Monte Carlo samples, with computational complexity . Suppose there are constants and such that, for every and every ,
- (i) ;
- (ii) if , and if ;
- (iii) ;
- (iv) ;
and that for every choice of sample sizes the estimators are independent. Then there is a constant such that for every there are a finest level and sample sizes for which the multilevel estimator has
with a computational complexity bounded by
Plain Monte Carlo with an Euler discretisation needs cost of order for the same accuracy; the theorem shows that the multilevel estimator reaches the cost of an unbiased estimator when , loses only a factor when (the Euler scheme with a Lipschitz payoff), and gives an explicit rate otherwise.
Formalization Note and 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 , because the theorem chooses the sample sizes. Hypothesis (i) carries an absolute value: the page prints the one-sided , under which the theorem is false (take for every ); the proof uses the two-sided bound. is the paper's standing "integer " (§1), is implicit. The complexity is the sum of the level complexities, each constrained only by (iv). Since is fixed by the hypotheses, one constant serves; it does not depend on , or .
import Mathlib import Definitions.Def_GilesMLMC_Complexity_Setup
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.