Appendix A, p. 23 — complex sample-mean concentration
ProvedVdNSim.Sparse.complex_hoeffdingcomplex-analysisconcentrationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sampling
Let be a probability law on a finite set , and let satisfy for every . For independent draws from and ,
This form controls the complex functions and appearing in Theorem 3.
Formalization Note The paper states that a similar complex bound follows by splitting real and imaginary parts but does not print a constant. The displayed constant is the consequence of its Eq. (18). The positive tolerance and sample count specify the valid domain.
Preamble
import Mathlib import Definitions.Def_VdNSim_Sparse_Model noncomputable section
Formal statement
namespace VdNSim.Sparse
/-- Appendix A, p. 23, the complex-valued consequence of Eq. (18). -/
theorem complex_hoeffding {X : Type*} [Fintype X] [DecidableEq X]
(p : X → ℝ) (hp0 : ∀ x, 0 ≤ p x) (hp1 : ∑ x, p x = 1)
(f : X → ℂ) (hf : ∀ x, ‖f x‖ ≤ 1)
{K : ℕ} (hK : 0 < K) {ε : ℝ} (hε : 0 < ε) :
sampleProb p K (fun xs =>
ε < ‖(K : ℂ)⁻¹ * ∑ k, f (xs k) - expect p f‖) ≤
4 * Real.exp (-((K : ℝ) * ε ^ 2) / 8) := by sorry
end VdNSim.Sparse
Source
Van den Nest, Simulating quantum computers with probabilistic methods, arXiv:0911.1624v3, p. 23, paragraph following Eq. (18)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.