(6) — the choice of gives
ProvedGilesMLMC.Complexity.eq_6multilevel-monte-carlop2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1real-analysis
Let be an integer and . Choose the integer
and let . Then
The right inequality makes the bias at level at most ; the left one bounds , and hence the number of levels and the cost.
Formalization Note The statement holds for every value of the ceiling, including a negative one, so is an integer and uses an integer power. is implicit in the paper.
Preamble
import Mathlib import Definitions.Def_GilesMLMC_Complexity_Setup import Definitions.Def_GilesMLMC_Complexity_Choices
Formal statement
namespace GilesMLMC.Complexity
/-- Inequality (6) (Giles 2008, §3, proof of Theorem 3.1, p. 609, PDF 3, right column, top): with `L = ⌈log(√2 c₁ T^α ε⁻¹)/(α log M)⌉`, `(1/√2) M^{-α} ε < c₁ h_L^α ≤ (1/√2) ε`.
Formalization Note. Here `L` is the integer `Lchoice M T α c₁ ε` (`Int.ceil`), and `h_L = T M^{-L}` is `hz` (an integer power), so the statement holds for every value of the ceiling, including a negative one. Powers with real exponents are `Real.rpow`. `ε > 0` is implicit in the paper. -/
theorem eq_6
(M : ℕ) (hM : 2 ≤ M) (T : ℝ) (hT : 0 < T)
(α c₁ ε : ℝ) (hα : 0 < α) (hc₁ : 0 < c₁) (hε : 0 < ε) :
(M : ℝ) ^ (-α) * ε / Real.sqrt 2 < c₁ * hz M T (Lchoice M T α c₁ ε) ^ α ∧
c₁ * hz M T (Lchoice M T α c₁ ε) ^ α ≤ ε / Real.sqrt 2 := by sorry
end GilesMLMC.Complexity
Source
Giles, Multilevel Monte Carlo path simulation, Operations Research 56(3) (2008), §3, proof of Theorem 3.1, (6), p. 609
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.