§2.2, proof of Lemma 4 — dyadic decomposition
ProvedQuantumMC.MeanEst.lemma_4_decompositionmean-estimationmonte-carlop2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-algorithms
For an integrable nonnegative output and a natural number , the mean splits into the base interval, half-open dyadic bands, and the upper tail:
This identity fixes the band boundaries and the scaling used by Algorithm 2.
Preamble
import Mathlib import Definitions.Def_QuantumMC_MeanEst_Setting
Formal statement
namespace QuantumMC.MeanEst
open MeasureTheory ProbabilityTheory
/-- §2.2, proof of Lemma 4, p. 10: the dyadic decomposition of the mean. -/
theorem lemma_4_decomposition {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω)
[IsProbabilityMeasure P] (X : Ω → ℝ) (hX : Integrable X P)
(hpos : ∀ ω, 0 ≤ X ω) (k : ℕ) :
(∫ ω, X ω ∂P) = (∫ ω, truncIco 0 1 X ω ∂P) +
(∑ ℓ ∈ Finset.Icc 1 k, (2 : ℝ) ^ ℓ * (∫ ω, band X ℓ ω ∂P)) +
(∫ ω, truncGe ((2 : ℝ) ^ k) X ω ∂P) := by sorry
end QuantumMC.MeanEst
Source
Montanaro, Quantum speedup of Monte Carlo methods, arXiv:1504.06987v3, §2.2, proof of Lemma 4, p. 10
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.