Eq. (18), p. 23 — Chernoff–Hoeffding bound for the sample mean
ProvedVdNSim.Sparse.eq_18chernoff-hoeffdingconcentrationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sampling
Let be a probability law on a finite set , and let be real valued. Draw independent samples from . For every ,
This is the concentration estimate invoked for the bounded summands of the simulation estimator.
Formalization Note The independent variables are realized as evaluations of one function on independent draws from a finite probability mass function. The assumption rules out a negative tolerance, for which the displayed event is empty.
Preamble
import Mathlib import Definitions.Def_VdNSim_Sparse_Model noncomputable section
Formal statement
namespace VdNSim.Sparse
/-- Appendix A, Eq. (18), in the finite sampling model used by the paper. -/
theorem eq_18 {X : Type*} [Fintype X] [DecidableEq X]
(p : X → ℝ) (hp0 : ∀ x, 0 ≤ p x) (hp1 : ∑ x, p x = 1)
(f : X → ℝ) (hf : ∀ x, f x ∈ Set.Icc (-1) 1)
{K : ℕ} (hK : 0 < K) {ε : ℝ} (hε : 0 < ε) :
1 - 2 * Real.exp (-((K : ℝ) * ε ^ 2) / 4) ≤
sampleProb p K (fun xs =>
|(K : ℝ)⁻¹ * ∑ k, f (xs k) - ∑ x, p x * f x| ≤ ε) := by sorry
end VdNSim.Sparse
Source
Van den Nest, Simulating quantum computers with probabilistic methods, arXiv:0911.1624v3, p. 23, Eq. (18)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.