ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Euler strong, weak, and autonomous MLMC rate contracts

Example

Set $T = 1$ , $M = 2$ , and write $ϵ = 2^{- k}$ for integers $k \to \infty$ . Normalize the bias-rate constant to $C_{b} = 1$ to display the level counts. Fix the state and Brownian dimensions, and count arithmetic operations, Brownian increment draws, coefficient evaluations, and payoff evaluations as unit work.

The finite- $L^{2}$ strong route and the separate autonomous all-moment route both have $α = \frac{1}{2}$ , $β = 1$ , and per-path-pair work exponent $γ = 1$ . The bias cutoff is met at $L = 2 k + O (1)$ , so $h_{L} = 2^{- L} = Θ (ϵ^{2})$ .
Under the additional bounded-payoff backward-regularity contract, the finite- $L^{2}$ weak route has $α = 1$ , with the same $β = γ = 1$ . The bias cutoff is met at $L = k + O (1)$ , so $h_{L} = Θ (ϵ)$ .

The two bias contracts therefore require different finest grids, but the same $β = γ$ case of the MLMC theorem gives $O (ϵ^{- 2} k^{2}) = O (ϵ^{- 2} (\log ϵ^{- 1})^{2})$ work in each branch. The weak-rate branch is conditional on its stated backward regularity; it is not supplied by a Lipschitz payoff alone.

Facts & Assumptions

Given: AC; the finite- $L^{2}$ SDE contract; the autonomous all-moment SDE contract; a globally Lipschitz payoff; fixed state and Brownian dimensions and the unit-cost work model above; and, for the weak branch only, the bounded-payoff backward regularity and moment hypotheses.

[F1]

Autonomous all-moment Euler MLMC logarithmic cost: the autonomous Higham–Mao–Stuart route keeps its exact all-moment premise and gives $(α, β) = (1 / 2, 1)$ and the logarithmic MLMC work bound under the stated work model.

[F2]

Finite-L2 strong and conditional weak Euler MLMC cost: the finite- $L^{2}$ strong branch gives $(α, β) = (1 / 2, 1)$ ; the additional backward-regularity branch gives $(α, β) = (1, 1)$ . Both branches give the logarithmic MLMC work bound under the stated work model.

[F3]

Geometric MLMC hierarchy and coupled corrections: the estimator uses geometrically refined meshes and independent level sample blocks.

[A1]

AC is assumed by the two Euler rate contracts used in this comparison. The Axiom of Choice

Verification

1.1A1F1F2F3givenalgebra

With $ϵ = 2^{- k}$ and $C_{b} = T = 1$ , the bias cutoff $h_{L}^{α} \leq ϵ / \sqrt{2}$ requires $L \geq α^{- 1} (k + \frac{1}{2})$ . Thus the strong routes with $α = \frac{1}{2}$ use $L = 2 k + O (1)$ , while the weak route with $α = 1$ uses $L = k + O (1)$ . The meshes and level-block independence are those of [F3].

2.1A1F1F2givenstep 1.1algebra∎

For $ℓ \geq 1$ , the fine and coarse paths take $2^{ℓ}$ and $2^{ℓ - 1}$ Euler steps. Summing pairs of fine Brownian increments forms the coarse increments in $O (2^{ℓ})$ operations. Under the stated fixed-dimension unit-cost model, the coupled sample therefore costs $O (2^{ℓ}) = O (h_{ℓ}^{- 1})$ ; level zero takes one Euler step and also satisfies this bound. Thus $γ = 1$ in every branch, while [F1]–[F2] give $β = 1$ and the logarithmic MLMC work bound $O (ϵ^{- 2} (\log ϵ^{- 1})^{2}) = O (2^{2 k} k^{2})$ . The change in $α$ changes the finest mesh count but not this complexity regime.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

11 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Michael B. Giles, Multilevel Monte Carlo Path Simulation, §§2–3 (standard reference, not scraped)