CounterexampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedjudge pass (gpt-6-luna)

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.

Nondecaying correction variance can force cubic cost

Statement refuted

Bias order one and per-sample work $O (h_{ℓ}^{- 1})$ alone guarantee the logarithmic MLMC work bound $O (ϵ^{- 2} (\log ϵ^{- 1})^{2})$ .

Facts & Assumptions

Given: The finite MLMC hierarchy, the claimed universal complexity bound above, and the counterexample construction below.

[F1]

Geometric MLMC hierarchy and coupled corrections: adjacent-level couplings need only have the correct marginal laws, and level sample blocks are independent.

[F2]

Expectation, variance, and MSE of a finite MLMC estimator: the MLMC MSE is squared finest-level bias plus the sum of each correction variance divided by its sample count.

Counterexample

Let $T = 1$ , $M = 2$ , $h_{ℓ} = 2^{- ℓ}$ , target $P = 0$ , and $P_{ℓ} = h_{ℓ} + Z_{ℓ},$ where each $Z_{ℓ}$ is Rademacher. At level $ℓ \geq 1$ , couple the fine and coarse marginals independently: use independent Rademacher variables $Z_{ℓ}^{f}$ and $Z_{ℓ - 1}^{c}$ and set $Δ_{ℓ} = (h_{ℓ} + Z_{ℓ}^{f}) - (h_{ℓ - 1} + Z_{ℓ - 1}^{c}) .$ At level $0$ , use $Δ_{0} = 1 + Z_{0}$ . Take the level sample blocks independent and charge $h_{ℓ}^{- 1}$ work per draw.

Given: Any finite level $L$ and positive integer sample counts for which the estimator has MSE at most $ϵ^{2}$ .

1.1F1givenalgebra

Since $E P_{ℓ} = h_{ℓ}$ , the finest-level bias is $h_{L}$ , so this hierarchy has bias order $α = 1$ . For $ℓ \geq 1$ , the independent centered Rademacher terms have variance $1 + 1 = 2$ , hence $Var (Δ_{ℓ}) = 2$ and no bound $O (h_{ℓ}^{β})$ holds for any $β > 0$ . The sample cost is exactly $h_{ℓ}^{- 1}$ .

2.1F2step 1.1givenalgebra∎

By [F2], the MSE is $h_{L}^{2} + \frac{1}{N_{0}} + 2 \sum_{ℓ = 1}^{L} \frac{1}{N_{ℓ}} .$ Thus MSE at most $ϵ^{2}$ requires $h_{L} \leq ϵ$ and $N_{L} \geq 2 ϵ^{- 2}$ . The finest-level work alone is therefore $N_{L} h_{L}^{- 1} \geq 2 ϵ^{- 3}$ . This grows faster than $ϵ^{- 2} (\log ϵ^{- 1})^{2}$ , so the claimed logarithmic bound fails without a positive correction-variance decay rate.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

5 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, §3 (standard reference, not scraped)