§2.3, proof of Theorem 5 — Chebyshev bound
ProvedQuantumMC.MeanEst.theorem_5_chebyshevmean-estimationmonte-carlop2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-algorithms
Let have variance at most , with , and let . Then
This bounds the chance that Algorithm 3's one preliminary sample is far from the rescaled mean. Formalization Note Finite variance is expressed with as well as the variance inequality.
Preamble
import Mathlib import Definitions.Def_QuantumMC_MeanEst_Setting
Formal statement
namespace QuantumMC.MeanEst
open MeasureTheory ProbabilityTheory
/-- §2.3, proof of Theorem 5, p. 12: Chebyshev at three standard deviations. -/
theorem theorem_5_chebyshev {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω)
[IsProbabilityMeasure P] (X : Ω → ℝ) (hXm : Measurable X)
(hX : MemLp X 2 P) (σ : ℝ) (hvar : variance X P ≤ σ ^ 2)
(hσ : 0 < σ) :
P {ω | 3 ≤ |X ω / σ - ∫ x, X x / σ ∂P|} ≤ (1 / 9 : ENNReal) := by sorry
end QuantumMC.MeanEst
Source
Montanaro, Quantum speedup of Monte Carlo methods, arXiv:1504.06987v3, §2.3, proof of Theorem 5, p. 12
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.