§2.2, proof of Lemma 4 — tail second-moment bound
ProvedQuantumMC.MeanEst.lemma_4_tail_boundmean-estimationmonte-carlop2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-algorithms
Let be nonnegative with a finite second moment. For any natural number ,
This controls the output omitted by the finite dyadic sum. Formalization Note The paper writes a sum over its discrete output law; the integral has the same value for that law.
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 tail is bounded by its second moment. -/
theorem lemma_4_tail_bound {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω)
[IsProbabilityMeasure P] (X : Ω → ℝ) (hX : MemLp X 2 P)
(hpos : ∀ ω, 0 ≤ X ω) (k : ℕ) :
(∫ ω, truncGe ((2 : ℝ) ^ k) X ω ∂P) ≤
l2norm P X ^ 2 / (2 : ℝ) ^ k := 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.