Lemma 2.4.11 — comparing Gaussian tails
ProvedSmoothedSimplex.Shadow.comparing_gaussian_tailsgaussianp2o-batch-pfp1ap2o-gran-per-chapterp2o-plan-paperp2o-v1probabilitysmoothed-analysis
Let and let be the density of the centered normal distribution with variance . Then for and ,
Moving the threshold of a Gaussian tail by changes its mass by a relative factor of order , as long as the threshold is not far out in the tail; Lemma 4.2.3 applies this to halfspace probabilities.
Formalization Note The tail integrals are the masses of and under gaussianReal 0 σ²; the ratio is cross-multiplied (the denominator is positive).
Preamble
import Mathlib
Formal statement
namespace SmoothedSimplex.Shadow
open MeasureTheory ProbabilityTheory
open scoped RealInnerProductSpace
/-- **Lemma 2.4.11 (Comparing Gaussian tails)** (Spielman & Teng, arXiv:cs/0111050v7,
Lemma 2.4.11, printed p. 23, PDF p. 23). Let `σ ≤ 1` and let `µ(t) = (1/(√(2π)σ)) e^{−t²/2σ²}`.
Then, for `x ≤ 2` and `|x − y| ≤ ε`,
`∫_{t=y}^∞ µ(t) dt / ∫_{t=x}^∞ µ(t) dt ≥ 1 − 8ε/(3σ²)`.
**Formalization Note.** `σ > 0`. `µ` is the density of `gaussianReal 0 σ²`, so
`∫_{t=y}^∞ µ(t) dt = gaussianReal 0 σ² [y, ∞)`. The ratio is cross-multiplied (the denominator is
positive, so this is equivalent). -/
theorem comparing_gaussian_tails (σ : ℝ) (hσ : 0 < σ) (hσ1 : σ ≤ 1) (x y ε : ℝ)
(hx : x ≤ 2) (hxy : |x - y| ≤ ε) :
(1 - 8 * ε / (3 * σ ^ 2)) * (gaussianReal 0 (σ ^ 2).toNNReal (Set.Ici x)).toReal ≤
(gaussianReal 0 (σ ^ 2).toNNReal (Set.Ici y)).toReal := by sorry
end SmoothedSimplex.Shadow
Source
Spielman & Teng, Smoothed Analysis of Algorithms, arXiv:cs/0111050v7, Lemma 2.4.11, eq. (6), printed p. 23 (PDF p. 23)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.