Alphabeta Math
TheoremStatement: Literature-sourcedProof: 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.

MLMC cost complexity under bias, variance, and work rates

Statement

Let M≥2 be an integer, T>0, and hℓ=TM−ℓ. Let P be an integrable real target. Suppose we are given an infinite compatible hierarchy: for every ℓ≥0 a square-integrable level approximation Pℓ, and for every ℓ≥1 a fixed coupling of the laws of Pℓ and Pℓ−1. Define Δ0=P0 and, under each coupling, Δℓ=Pℓf−Pℓ−1c. For each finite L, use the first L+1 levels and their couplings, with independent sample blocks across levels, as in Geometric MLMC hierarchy and coupled corrections. Suppose there are constants Cb,Cv,Cc>0 and exponents α≥12 and β>0 such that, for every ℓ≥0, ∣EPℓ−EP∣≤Cbhℓα,Var⁡(Δℓ)≤Cvhℓβ, and the work for one level-ℓ correction sample is at most Cchℓ−1. For every sufficiently small ϵ>0, there are a finite level L and positive integer sample counts N0,…,NL for which the estimator of Geometric MLMC hierarchy and coupled corrections satisfies E[(μ^L,N−EP)2]≤ϵ2 and its total work has the following upper bounds, with constants independent of ϵ: {O(ϵ−2),β>1,O ⁣(ϵ−2(log⁡ϵ−1)2),β=1,O ⁣(ϵ−2−(1−β)/α),0<β<1. This is an upper bound under the three rate assumptions; it does not assert a matching lower bound or that the rates hold for a particular discretization.

Facts & Assumptions

Given: The infinite compatible hierarchy and target above, α≥12, β>0, positive constants Cb,Cv,Cc, the bias and correction-variance bounds, and the per-sample work bound. Every finite prefix, with independent level sample blocks, satisfies the definition cited in the Statement.

[F1]

Geometric MLMC hierarchy and coupled corrections: the geometric mesh widths are hℓ=TM−ℓ.

[F2]

Geometric MLMC hierarchy and coupled corrections: the estimator is the sum of level sample means, with independent sample blocks at distinct levels.

[F3]

Expectation, variance, and MSE of a finite MLMC estimator: its mean is EPL, its variance is ∑ℓ=0LVℓ/Nℓ, and its MSE is that variance plus squared bias.

Proof

Given: The rate hypotheses in the Statement.

1.1givenF1choosealgebra

For sufficiently small ϵ, choose L=⌈log⁡(2 CbTα/ϵ)αlog⁡M⌉. Then CbhLα≤ϵ/2. The ceiling also gives hL−1=O(ϵ−1/α) and L+1=O(log⁡ϵ−1).

2.1F2F3step 1.1constructalgebra

Put vℓ=Cvhℓβ, cℓ=Cchℓ−1, and SL=∑ℓ=0Lvℓcℓ. Choose Nℓ=⌈2ϵ−2SLvℓcℓ⌉,0≤ℓ≤L. Each Nℓ is a positive integer. Since Vℓ≤vℓ and Nℓ≥2ϵ−2SLvℓ/cℓ, [F3] gives Var⁡(μ^L,N)≤∑ℓ=0LvℓNℓ≤ϵ22SL∑ℓ=0Lvℓcℓ=ϵ22. The bias bound from step 1.1 and the MSE identity [F3] imply the required MSE bound.

2.2F1givenstep 1.1algebra

The ceiling inequality ⌈x⌉≤x+1 and the per-sample work bound imply Work⁡≤∑ℓ=0LNℓcℓ≤2ϵ−2SL2+∑ℓ=0Lcℓ. Because hℓ=hLML−ℓ, the geometric-series formula gives ∑ℓ=0Lcℓ=Cc∑ℓ=0Lhℓ−1≤Cc1−M−1hL−1=O(ϵ−1/α).

3.1givenstep 2.2algebra

If β>1, put q=(β−1)/2>0. Then SL=CvCc∑ℓ=0Lhℓq≤CvCc Tq1−M−q=O(1). The first term in step 2.2 is O(ϵ−2). Its rounding term is also O(ϵ−2), since 1/α≤2.

3.2givenstep 1.1step 2.2algebra

If β=1, then SL=CvCc(L+1)=O(log⁡ϵ−1) by step 1.1. The first term in step 2.2 is therefore O(ϵ−2(log⁡ϵ−1)2), and its rounding term is no larger for sufficiently small ϵ, again because 1/α≤2.

3.3givenstep 1.1step 2.2algebra

If 0<β<1, put q=(1−β)/2>0. Then SL=CvCc∑ℓ=0Lhℓ−q≤CvCc1−M−qhL−q. The lower geometric bound from step 1.1 gives hL−1=O(ϵ−1/α), so SL2=O(ϵ−(1−β)/α). The first term in step 2.2 is O(ϵ−2−(1−β)/α). The rounding term O(ϵ−1/α) is smaller because 1/α≤2<2+(1−β)/α.

4.1step 2.1step 3.1step 3.2step 3.3∎

The estimates in steps 3.1–3.3 cover respectively β>1, β=1, and 0<β<1. Each case gives the stated total-work upper bound while step 2.1 gives the same MSE bound.

Depends on

Used by

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