Gaussian tail bounds x/(1+x²) ϕ(x) ≤ Pr[g ≥ x] ≤ ϕ(x)/x for x > 0 (§4, proof of Theorem 4.2)
ProvedMemoSDPI.Main.gaussian_tail_boundsgaussianp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilitytail-bound
Let be a standard Gaussian random variable with density . For every ,
The proof of Theorem 4.2 uses the lower bound at and the upper bound at (cited from Polyanskiy–Wu, Exercise V.25, eq. (V.8)).
Formalization Note is Mathlib's gaussianPDFReal 0 1 and is the real value of the standard Gaussian measure gaussianReal 0 1 on .
Differences from the source: none.
Preamble
import Mathlib set_option autoImplicit false open MeasureTheory ProbabilityTheory
Formal statement
namespace MemoSDPI.Main
/-- Feldman, Lyu, Talwar, *Lower Bounds for Memorization, Privacy and Replicability from Not-So-Strong Data Processing Inequalities*, STOC 2027 submission (manuscript sha256 dbb300da…), p. 16, proof of Theorem 4.2 (cited from [PW24, Exercise V.25, eq. (V.8)]): for a
standard Gaussian `g` and `x > 0`, `x/(1 + x²) · ϕ(x) ≤ Pr[g ≥ x] ≤ ϕ(x)/x`. -/
theorem gaussian_tail_bounds (x : ℝ) (hx : 0 < x) :
x / (1 + x ^ 2) * gaussianPDFReal 0 1 x ≤ (gaussianReal 0 1).real (Set.Ici x) ∧
(gaussianReal 0 1).real (Set.Ici x) ≤ gaussianPDFReal 0 1 x / x := by sorry
end MemoSDPI.Main
Source
Feldman, Lyu, Talwar, Lower Bounds for Memorization, Privacy and Replicability from Not-So-Strong Data Processing Inequalities, STOC 2027 submission (manuscript sha256 dbb300da…), p. 16, §4, proof of Theorem 4.2, Gaussian tail bounds
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.