§2.2, proof of Lemma 4 — band second-moment bound
ProvedQuantumMC.MeanEst.lemma_4_band_boundmean-estimationmonte-carlop2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-algorithms
Let be nonnegative with a finite second moment and . On the band ,
This bounds each band mean by its second moment.
Preamble
import Mathlib import Definitions.Def_QuantumMC_MeanEst_Setting
Formal statement
namespace QuantumMC.MeanEst
open MeasureTheory ProbabilityTheory
/-- §2.2, proof of Lemma 4, p. 11: one dyadic band's first moment is bounded by its second. -/
theorem lemma_4_band_bound {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω)
[IsProbabilityMeasure P] (X : Ω → ℝ) (hX : MemLp X 2 P)
(hpos : ∀ ω, 0 ≤ X ω) (ℓ : ℕ) (hℓ : 1 ≤ ℓ) :
(∫ ω, truncIco ((2 : ℝ) ^ (ℓ - 1)) ((2 : ℝ) ^ ℓ) X ω ∂P) ≤
l2norm P (truncIco ((2 : ℝ) ^ (ℓ - 1)) ((2 : ℝ) ^ ℓ) X) ^ 2 /
(2 : ℝ) ^ (ℓ - 1) := by sorry
end QuantumMC.MeanEst
Source
Montanaro, Quantum speedup of Monte Carlo methods, arXiv:1504.06987v3, §2.2, proof of Lemma 4, p. 11
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.