Appendix A, equation A2: squared-Gaussian tail bounds
OpenQAlgorithms.Papers.Independent.Intakenext100.P54.squared_gaussian_tailsLet , , and let be independent measurable variables. Write . For every ,
For one also has
For the strict lower-tail event has probability zero. This records both displayed consequences of Lemma 23 while giving the lower logarithm its correct domain.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P54
noncomputable section
open scoped BigOperators Matrix ComplexConjugate ComplexOrder NNReal ENNReal
open MeasureTheory ProbabilityTheory
namespace QAlgorithms.Papers.Independent.Intakenext100.P54
open QAlgorithms.Papers.Independent.Information100.P03 (PureEnsemble)
open QAlgorithms.Papers.Independent.Information100.P53 (fidelity)
open QAlgorithms.Papers.Independent.Dependency50.P07 (wordProb)
open QAlgorithms.Papers.Independent.Claimed50.P08 (classicalEntropy)
open QAlgorithms.Papers.Independent.Claimed50.P38 (tensorSuperop)
/-- Equation A2, PDF p.14: both squared-Gaussian tails. The lower displayed logarithmic
bound has domain eps < 1; for eps ≥ 1 the strict lower-tail event is empty.
The paper's exp is base two. -/
theorem squared_gaussian_tails {Omega : Type*} [MeasurableSpace Omega]
(mu : Measure Omega) [IsProbabilityMeasure mu] (N : ℕ) (hN : 0 < N)
(s2 : ℝ≥0) (hs : 0 < s2) (Y : Fin N → Omega → ℝ)
(hMeas : ∀ i, Measurable (Y i)) (hInd : iIndepFun Y mu)
(hLaw : ∀ i, Measure.map (Y i) mu = gaussianReal 0 s2)
(eps : ℝ) (heps : 0 ≤ eps) :
mu {w | (∑ i, Y i w ^ 2) / (N : ℝ) > (1 + eps) * s2} ≤
ENNReal.ofReal ((2 : ℝ) ^ (-(N : ℝ) * (eps - Real.log (1 + eps)) / (2 * Real.log 2))) ∧
(eps < 1 → mu {w | (∑ i, Y i w ^ 2) / (N : ℝ) < (1 - eps) * s2} ≤
ENNReal.ofReal ((2 : ℝ) ^ (-(N : ℝ) * (-eps - Real.log (1 - eps)) / (2 * Real.log 2)))) ∧
(1 ≤ eps → mu {w | (∑ i, Y i w ^ 2) / (N : ℝ) < (1 - eps) * s2} = 0) := by sorry
end QAlgorithms.Papers.Independent.Intakenext100.P54
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Let be any measurable space with probability measure , let be a positive natural number, let , and let for be measurable, jointly independent functions, each with Gaussian law of mean and variance . For every real , writing , all of the following hold:
The finite real bounds on the right are interpreted as extended nonnegative real numbers. Both tail events use strict inequalities, including at ; for , the lower-tail threshold is nonpositive.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.