Case (a) —
ProvedGilesMLMC.Complexity.L_succ_le_c5multilevel-monte-carlop2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1real-analysis
Let be an integer, and . For the integer level of (6),
The number of levels thus grows only logarithmically in , with a constant independent of ; in case (a) this is the source of the factor .
Formalization Note is the integer ceiling, cast to the reals; the bound holds whatever its sign. is implicit in "".
Preamble
import Mathlib import Definitions.Def_GilesMLMC_Complexity_Setup import Definitions.Def_GilesMLMC_Complexity_Choices
Formal statement
namespace GilesMLMC.Complexity
/-- Case (a) of the proof of Theorem 3.1, bound on `L` (Giles 2008, §3, p. 609, PDF 3, right column, bottom): for `ε < e⁻¹`, `L + 1 ≤ c₅ log ε⁻¹` with `c₅ = 1/(α log M) + max(0, log(√2 c₁ T^α)/(α log M)) + 2`.
Formalization Note. `L` is the integer ceiling `Lchoice M T α c₁ ε` of (6), cast to ℝ; the bound holds whatever its sign. `ε > 0` is implicit in "ε < e⁻¹". -/
theorem L_succ_le_c5
(M : ℕ) (hM : 2 ≤ M) (T : ℝ) (hT : 0 < T)
(α c₁ ε : ℝ) (hα : 0 < α) (hc₁ : 0 < c₁) (hε : 0 < ε) (hε1 : ε < Real.exp (-1)) :
((Lchoice M T α c₁ ε : ℤ) : ℝ) + 1 ≤ c₅ M T α c₁ * Real.log ε⁻¹ := by sorry
end GilesMLMC.Complexity
Source
Giles, Multilevel Monte Carlo path simulation, Operations Research 56(3) (2008), §3, proof of Theorem 3.1, case (a), bound on L, p. 609
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.