Probability
The catalogue's first page explains what each entry shows.
Chapter 1 · Preliminaries on random variables all chapters
Definitions, theorems and lemmas
Corollary 1.2.5
Chebyshev's inequality for a real random variable with finite centered second moment.
Lean statement
theorem hdp_01_hcor_h1_d2_d5 {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} {X : Ω → ℝ} (hX : Measurable X) (hInt : Integrable X μ) (hSqInt : Integrable (fun ω => (X ω - NumStability.HDP.Scalar.Preliminaries.expectation μ X) ^ 2) μ) {t : ℝ} (ht : 0 < t) : μ.real {ω | |X ω - NumStability.HDP.Scalar.Preliminaries.expectation μ X| ≥ t} ≤ NumStability.HDP.Scalar.Preliminaries.variance μ X / t ^ 2Theorem 1.3.1
Lean statement
theorem hdp_01_hthm_h1_d3_d1 {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} {X : ℕ → Ω → ℝ} (hInt : Integrable (X 0) μ) (hIndep : Pairwise ((· ⟂ᵢ[μ] ·) on X)) (hIdent : ∀ i, IdentDistrib (X i) (X 0) μ μ) : ∀ᵐ ω ∂μ, Tendsto (fun n : ℕ => (∑ i ∈ Finset.range n, X i ω) / n) atTop (nhds (∫ ω, X 0 ω ∂μ))Theorem 1.3.2
The closed-tail formulation printed immediately after Theorem 1.3.2, including the displayed standard-normal density integral.
Lean statement
theorem hdp_01_hthm_h1_d3_d2_tail {Ω : Type*} [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ] (X : ℕ → Ω → ℝ) (m σ : ℝ) (hσ : 0 < σ) (hX : ∀ i, MemLp (X i) 2 μ) (hIndep : iIndepFun X μ) (hIdent : ∀ i, IdentDistrib (X i) (X 0) μ μ) (hMean : ∫ ω, X 0 ω ∂μ = m) (hVariance : Var[X 0; μ] = σ ^ 2) (t : ℝ) : Tendsto (fun N : ℕ => ((NumStability.HDP.Scalar.LimitTheorems.probabilityLaw (hdp_01_hdef_hzn X m σ (N + 1)) (hdp_01_hdef_hzn_aemeasurable μ X m σ (N + 1) (fun i => (hX i).aemeasurable)) : ProbabilityMeasure ℝ) : Measure ℝ) (Set.Ici t)) atTop (𝓝 (ENNReal.ofReal (∫ x in Set.Ici t, (Real.sqrt (2 * Real.pi))⁻¹ * Real.exp (-(x ^ 2) / 2))))hdp_
01_ · 4 more declarations under this itemhthm_ h1_ d3_ d2_ tail Theorem 1.3.4
Theorem 1.3.4 (Poisson Limit Theorem): if the largest Bernoulli parameter in a row tends to zero and the row sums of parameters tend to
rate, then the laws of the independent Bernoulli row sums converge toPoisson(rate).Lean statement
theorem hdp_01_hthm_h1_d3_d4 (p : (N : ℕ) → Fin (N + 1) → ℝ≥0) (hp : ∀ N i, p N i ≤ 1) (rate : ℝ≥0) (hmax : Tendsto (fun N => (NumStability.HDP.Scalar.LimitTheorems.poissonRowMax p N : ℝ)) atTop (𝓝 0)) (hsum : Tendsto (NumStability.HDP.Scalar.LimitTheorems.poissonRowSum p) atTop (𝓝 (rate : ℝ))) : Tendsto (NumStability.HDP.Scalar.LimitTheorems.poissonBernoulliRowProbabilityMeasure p hp) atTop (𝓝 (NumStability.HDP.Scalar.LimitTheorems.poissonRealProbabilityMeasure rate))
Equations and other results
Result
The book's displayed formula
M_X(t) = E exp(tX), represented by the nonnegative Lebesgue integral so that no unstated finiteness convention is required.Lean statement
theorem hdp_01_hdef_hmgf_spec {Ω : Type*} [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ] (X : Ω → ℝ) (_hX : Measurable X) (t : ℝ) : NumStability.HDP.Scalar.Preliminaries.mgf μ X t = ∫⁻ ω, ENNReal.ofReal (Real.exp (t * X ω)) ∂μResult
The two displayed
L^pnorm clauses, packaged for a single source audit.Lean statement
theorem hdp_01_hdef_hlp_hnorm_spec {Ω : Type*} [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ] (X : Ω → ℝ) : (∀ p : ENNReal, p ≠ 0 → p ≠ ⊤ → eLpNorm X p μ = (∫⁻ ω, ‖X ω‖ₑ ^ p.toReal ∂μ) ^ (1 / p.toReal)) ∧ eLpNorm X (⊤ : ENNReal) μ = eLpNormEssSup X μResult
The two displayed formulas for
Z_Nagree when the partial sum has meanN m, varianceN σ², andN, σare positive.Lean statement
theorem hdp_01_hdef_hzn_eq_source_normalization {Ω : Type*} [MeasurableSpace Ω] (μ : Measure Ω) (X : ℕ → Ω → ℝ) (m σ : ℝ) (N : ℕ) (hN : 0 < N) (hσ : 0 < σ) (hMean : NumStability.HDP.Scalar.Preliminaries.expectation μ (fun ω => ∑ i ∈ Finset.range N, X i ω) = (N : ℝ) * m) (hVar : NumStability.HDP.Scalar.Preliminaries.variance μ (fun ω => ∑ i ∈ Finset.range N, X i ω) = (N : ℝ) * σ ^ 2) : (fun ω => ((∑ i ∈ Finset.range N, X i ω) - NumStability.HDP.Scalar.Preliminaries.expectation μ (fun ω => ∑ i ∈ Finset.range N, X i ω)) / Real.sqrt (NumStability.HDP.Scalar.Preliminaries.variance μ (fun ω => ∑ i ∈ Finset.range N, X i ω))) = hdp_01_hdef_hzn X m σ NResult
For every exponent
p ∈ [1,∞], theL^pquotient has its normed additive group structure and is complete.Lean statement
theorem hdp_01_hthm_hlp_hbanach_spec {Ω : Type*} [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ] (p : ENNReal) [Fact (1 ≤ p)] : Nonempty (NormedAddCommGroup (MeasureTheory.Lp ℝ p μ)) ∧ Nonempty (NormedSpace ℝ (MeasureTheory.Lp ℝ p μ)) ∧ (∀ f : MeasureTheory.Lp ℝ p μ, ‖f‖ = ENNReal.toReal (eLpNorm f p μ)) ∧ IsComplete (Set.univ : Set (MeasureTheory.Lp ℝ p μ))Result
For a measurable representative and a positive exponent, membership in
L^pis exactly finiteness of the extendedL^pnorm.Lean statement
theorem hdp_01_hdef_hlp_hspace_spec {Ω : Type*} [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ] (p : ENNReal) (_hp : p ≠ 0) (X : Ω → ℝ) (hX : AEStronglyMeasurable X μ) : (NumStability.HDP.Scalar.Preliminaries.lpNormSpaceModel μ p).representativeMember X ↔ eLpNorm X p μ < ⊤Result
The book's Section 1.1 definitions of expectation and variance, read on the declared finite-Lebesgue-integral definability domain. The first conjunct is footnote 1: on the integrable domain
E Xis the Lebesgue integral ofX. The second conjunct is the printed formulaVar(X) = E(X - E X)^2, together with the fact that square-integrability makes its outer expectation an ordinary finite Lebesgue integral rather than a totalized value.Lean statement
theorem hdp_01_hdef_hexpectation_hvariance_spec {Ω : Type*} [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ] (X : Ω → ℝ) : (Integrable X μ → NumStability.HDP.Scalar.Preliminaries.expectation μ X = ∫ ω, X ω ∂μ) ∧ (MemLp X 2 μ → Integrable (fun ω => (X ω - NumStability.HDP.Scalar.Preliminaries.expectation μ X) ^ 2) μ ∧ NumStability.HDP.Scalar.Preliminaries.variance μ X = NumStability.HDP.Scalar.Preliminaries.expectation μ (fun ω => (X ω - NumStability.HDP.Scalar.Preliminaries.expectation μ X) ^ 2))Result
For every
0 < p < 1, two disjoint singleton indicators on the uniform two-point probability space violate theL^ptriangle inequality.Lean statement
theorem hdp_01_hclaim_hlp_hquasinorm_spec (p : ENNReal) (hp0 : 0 < p) (hp1 : p < 1) : ∃ (μ : Measure (Fin 2)) (f g : Fin 2 → ℝ), IsProbabilityMeasure μ ∧ ¬ eLpNorm (f + g) p μ ≤ eLpNorm f p μ + eLpNorm g p μResult
Lean statement
theorem hdp_01_hthm_hcauchy_hschwarz {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} {X Y : Ω → ℝ} (hX : MemLp X 2 μ) (hY : MemLp Y 2 μ) : ‖NumStability.HDP.Scalar.Preliminaries.expectation μ (fun ω => X ω * Y ω)‖ ≤ (eLpNorm X 2 μ).toReal * (eLpNorm Y 2 μ).toRealResult
Hölder's inequality on the book's probability-space
L^pclasses. The first conjunct covers finite conjugate exponents; the other two retain the(1, ∞)and(∞, 1)endpoints explicitly.Lean statement
theorem hdp_01_hthm_hholder_spec {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {X Y : Ω → ℝ} : (∀ {p q : ℝ}, p.HolderConjugate q → MemLp X (ENNReal.ofReal p) μ → MemLp Y (ENNReal.ofReal q) μ → ‖expectation μ (fun ω => X ω * Y ω)‖ ≤ (∫ ω, ‖X ω‖ ^ p ∂μ) ^ (1 / p) * (∫ ω, ‖Y ω‖ ^ q ∂μ) ^ (1 / q)) ∧ (MemLp X 1 μ → MemLp Y (⊤ : ENNReal) μ → ‖expectation μ (fun ω => X ω * Y ω)‖ ≤ (eLpNorm X 1 μ).toReal * (eLpNorm Y (⊤ : ENNReal) μ).toReal) ∧ (MemLp X (⊤ : ENNReal) μ → MemLp Y 1 μ → ‖expectation μ (fun ω => X ω * Y ω)‖ ≤ (eLpNorm X (⊤ : ENNReal) μ).toReal * (eLpNorm Y 1 μ).toReal)Result
Chapter 1 source-facing Jensen inequality, stated on the declared finite-integral definability domain.
Lean statement
theorem hdp_01_hthm_hjensen {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {X : Ω → ℝ} {φ : ℝ → ℝ} (hφ : ConvexOn ℝ Set.univ φ) (hX : Integrable X μ) (hφX : Integrable (fun ω => φ (X ω)) μ) : φ (expectation μ X) ≤ expectation μ (fun ω => φ (X ω))Result
The book's cumulative-distribution formula
F_X(t) = P{X ≤ t}at every real threshold.Lean statement
theorem hdp_01_hdef_hcdf_spec {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {X : Ω → ℝ} (hX : AEMeasurable X μ) : ∀ t : ℝ, NumStability.HDP.Scalar.Preliminaries.cdf μ X t = μ (X ⁻¹' Set.Iic t)Result
A real function is convex exactly when it satisfies the book's displayed two-point inequality for every interpolation parameter in
[0,1].Lean statement
theorem hdp_01_hdef_hconvex_hfunction_spec (φ : ℝ → ℝ) : convexFunctionInterface φ ↔ ∀ (t : ℝ), 0 ≤ t → t ≤ 1 → ∀ x y : ℝ, φ (t * x + (1 - t) * y) ≤ t * φ x + (1 - t) * φ yResult
The source's indicator
1_Eis one onEand zero offE.Lean statement
theorem hdp_01_hdef_hindicator {Ω : Type*} [MeasurableSpace Ω] (E : Set Ω) (ω : Ω) : (ω ∈ E → indicatorFunction E ω = 1) ∧ (ω ∉ E → indicatorFunction E ω = 0)Result
On a probability space, the strict upper tail is one minus the inclusive CDF at the same threshold.
Lean statement
theorem hdp_01_heq_htail_hcdf_spec {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {X : Ω → ℝ} (hX : AEMeasurable X μ) (t : ℝ) : upperTail μ X t = 1 - cdf μ X tResult
The Bernoulli component of the Chapter 1 model: support and point masses, together with the printed mean and variance identities.
Lean statement
theorem hdp_01_hdef_hbernoulli (p : ℝ≥0) (hp0 : 0 < p) (hp1 : p < 1) : NumStability.HDP.Scalar.LimitTheorems.bernoulliNatPMF p (le_of_lt hp1) 1 = p ∧ NumStability.HDP.Scalar.LimitTheorems.bernoulliNatPMF p (le_of_lt hp1) 0 = 1 - p ∧ (∀ k : ℕ, k ≠ 0 → k ≠ 1 → NumStability.HDP.Scalar.LimitTheorems.bernoulliNatPMF p (le_of_lt hp1) k = 0) ∧ (∫ x : ℝ, x ∂ (NumStability.HDP.Scalar.LimitTheorems.bernoulliRealPMF p (le_of_lt hp1)).toMeasure) = p.toReal ∧ (∫ x : ℝ, (x - p.toReal) ^ 2 ∂ (NumStability.HDP.Scalar.LimitTheorems.bernoulliRealPMF p (le_of_lt hp1)).toMeasure) = p.toReal * (1 - p.toReal)Result
The binomial component of the Chapter 1 model: the success count of the canonical vector of
NBernoulli trials has the binomial law.Lean statement
theorem hdp_01_hdef_hbinomial (p : ℝ≥0) (hp0 : 0 < p) (hp1 : p < 1) (N : ℕ) (hN : 0 < N) : (NumStability.HDP.Scalar.LimitTheorems.bernoulliTrialVectorPMF p (le_of_lt hp1) N).map (NumStability.HDP.Scalar.LimitTheorems.bernoulliSuccessCount N) = NumStability.HDP.Scalar.LimitTheorems.binomialNatPMF p (le_of_lt hp1) NResult
The variance of the mean of the first
N + 1iid samples tends to zero.Lean statement
theorem hdp_01_hclaim_hsample_hmean_hvariance_hlimit {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsFiniteMeasure μ] {X : ℕ → Ω → ℝ} (hX : ∀ i, MemLp (X i) 2 μ) (hIndep : ∀ ⦃i j : ℕ⦄, i ≠ j → IndepFun (X i) (X j) μ) (hIdent : ∀ i, IdentDistrib (X i) (X 0) μ μ) : Tendsto (fun N : ℕ => Var[fun ω => ((N + 1 : ℕ) : ℝ)⁻¹ * ∑ i : Fin (N + 1), X i ω; μ]) atTop (𝓝 0)Result
Lean statement
theorem hdp_01_hlem_hindependent_hvariance_hsum {ι Ω : Type*} [Fintype ι] [MeasurableSpace Ω] {μ : Measure Ω} [IsFiniteMeasure μ] {X : ι → Ω → ℝ} (hX : ∀ i, MemLp (X i) 2 μ) (hIndep : ∀ ⦃i j : ι⦄, i ≠ j → IndepFun (X i) (X j) μ) : Var[∑ i, X i; μ] = ∑ i, Var[X i; μ]Equation (1.1)
On square-integrable real random variables, the representative-level inner product is
E[XY], and its corresponding norm is the square root ofE|X|². Mathlib'sLpsupplies the a.e.-quotient space; this theorem isolates the two printed formulas.Lean statement
theorem hdp_01_heq_h1_d1_spec {Ω : Type*} [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ] (X Y : Ω → ℝ) (_hX : MemLp X 2 μ) (_hY : MemLp Y 2 μ) : NumStability.HDP.Scalar.Preliminaries.l2InnerProduct μ X Y = NumStability.HDP.Scalar.Preliminaries.expectation μ (fun ω => X ω * Y ω) ∧ NumStability.HDP.Scalar.Preliminaries.l2Norm μ X = Real.sqrt (NumStability.HDP.Scalar.Preliminaries.expectation μ (fun ω => |X ω| ^ 2))hdp_
01_ · 1 more declaration under this itemheq_ h1_ d1_ spec Equation (1.2)
Covariance is the expectation of the product of the centered representatives and hence their representative-level
L²inner product.Lean statement
theorem hdp_01_heq_h1_d2_spec {Ω : Type*} [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ] (X Y : Ω → ℝ) (_hX : MemLp X 2 μ) (_hY : MemLp Y 2 μ) : covariance μ X Y = expectation μ (fun ω => (X ω - expectation μ X) * (Y ω - expectation μ Y)) ∧ expectation μ (fun ω => (X ω - expectation μ X) * (Y ω - expectation μ Y)) = l2InnerProduct μ (fun ω => X ω - expectation μ X) (fun ω => Y ω - expectation μ Y)Equation (1.4)
On the book's probability-space
L^p, theL^psize satisfies the triangle inequality for every extended exponentp ≥ 1, includingp = ∞. TheMemLphypotheses record the source's premise thatXandYbelong toL^p; the reusable inequality itself is valid under the weaker measurability hypotheses extracted from them.Lean statement
theorem hdp_01_heq_h1_d4_spec {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {X Y : Ω → ℝ} {p : ENNReal} (hp : 1 ≤ p) (hX : MemLp X p μ) (hY : MemLp Y p μ) : eLpNorm (X + Y) p μ ≤ eLpNorm X p μ + eLpNorm Y p μEquation (1.5)
Lean statement
theorem hdp_01_heq_h1_d5 {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsFiniteMeasure μ] (N : ℕ) (hN : 0 < N) {X : Fin N → Ω → ℝ} (hX : ∀ i, MemLp (X i) 2 μ) (hIndep : ∀ ⦃i j : Fin N⦄, i ≠ j → IndepFun (X i) (X j) μ) (hIdent : ∀ i, IdentDistrib (X i) (X ⟨0, hN⟩) μ μ) : Var[fun ω => (N : ℝ)⁻¹ * ∑ i, X i ω; μ] = (N : ℝ)⁻¹ * Var[X ⟨0, hN⟩; μ]Equation (1.6)
The density of the standard normal law.
Lean statement
theorem hdp_01_heq_h1_d6 : hdp_01_hdef_hstandard_hnormal = volume.withDensity (ProbabilityTheory.gaussianPDF 0 1) ∧ ProbabilityTheory.gaussianPDFReal 0 1 = fun x : ℝ => (Real.sqrt (2 * Real.pi))⁻¹ * Real.exp (-(x ^ 2) / 2)Equation (1.8)
The point mass of the Poisson law with rate
rate.Lean statement
theorem hdp_01_heq_h1_d8 (rate : ℝ≥0) (k : ℕ) : hdp_01_hdef_hpoisson rate {k} = ENNReal.ofReal (Real.exp (-(rate : ℝ)) * (rate : ℝ) ^ k / Nat.factorial k)Result
The expectation of the strict superlevel indicator is its event probability.
Lean statement
theorem hdp_01_hlem_h1_d2_d1_hindicator_hexpectation_spec {Ω : Type*} [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ] {X : Ω → ℝ} (hX : Measurable X) (t : ℝ) : expectation μ (indicatorFunction {ω | t < X ω}) = μ.real {ω | t < X ω}Result
A real number splits across the complementary events
x ≥ tandx < t.Lean statement
theorem hdp_01_hprop_h1_d2_d4_hdecomposition_spec (x t : ℝ) : x = x * (if t ≤ x then 1 else 0) + x * (if x < t then 1 else 0)
Problems and exercises
Exercise 1.2.6
The Chebyshev bound obtained by applying Markov's inequality to the squared centered random variable.
Lean statement
theorem hdp_01_hex_h1_d2_d6 {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} {X : Ω → ℝ} (hX : Measurable X) (hInt : Integrable X μ) (hSqInt : Integrable (fun ω => (X ω - NumStability.HDP.Scalar.Preliminaries.expectation μ X) ^ 2) μ) {t : ℝ} (ht : 0 < t) : μ.real {ω | |X ω - NumStability.HDP.Scalar.Preliminaries.expectation μ X| ≥ t} ≤ NumStability.HDP.Scalar.Preliminaries.variance μ X / t ^ 2hdp_
01_ · 1 more declaration under this itemhex_ h1_ d2_ d6
Chapter 2 · Concentration of sums of independent random variables all chapters
Definitions, theorems and lemmas
Definition 2.5.6
Lean statement
theorem hdp_02_hdef_h2_d5_d6 {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {X : Ω → ℝ} (_hX : Measurable X) : (∀ i : NumStability.HDP.Scalar.SubGaussian.SubGaussianPropertyKind, i ≠ .linearMGF → (NumStability.HDP.Scalar.SubGaussian.IsSubGaussian μ X ↔ ∃ K : ℝ, 0 < K ∧ NumStability.HDP.Scalar.SubGaussian.SubGaussianProperty μ X i K)) ∧ (NumStability.HDP.Scalar.SubGaussian.IsSubGaussian μ X → NumStability.HDP.Scalar.SubGaussian.PsiTwoNorm μ X < ∞ ∧ NumStability.HDP.Scalar.SubGaussian.PsiTwoNorm μ X = sInf {t : ℝ≥0∞ | NumStability.HDP.Scalar.SubGaussian.PsiTwoAdmissible μ X t})hdp_
02_ · 1 more declaration under this itemhdef_ h2_ d5_ d6 Definition 2.7.5
Finiteness of the property-(c) gauge is equivalent to satisfying any one of Proposition 2.7.1(a)--(d), and that gauge is the infimum of the positive property-(c) scales. Display (2.21)'s distinct property-(d) infimum remains represented by
hdp_02_heq_h2_d21_exact.Lean statement
theorem hdp_02_hdef_h2_d7_d5_exact : ∀ {Omega : Type*} [MeasurableSpace Omega] {mu : Measure Omega} [IsProbabilityMeasure mu] {X : Omega -> Real}, (PsiOnePropertyThreeGauge mu X < (⊤ : ENNReal) ↔ ∃ i : SubExponentialPropertyKind, ∃ K : Real, 0 < K ∧ SubExponentialProperty mu X i K) ∧ PsiOnePropertyThreeGauge mu X = sInf {t : ENNReal | PsiOnePropertyThreeAdmissible mu X t}hdp_
02_ · 1 more declaration under this itemhdef_ h2_ d7_ d5_ exact Lemma 2.7.6
Squaring identifies sub-gaussian variables with sub-exponential variables and squares the corresponding Orlicz gauge.
Lean statement
theorem hdp_02_hlem_h2_d7_d6_exact : ∀ {Omega : Type*} [MeasurableSpace Omega] {mu : Measure Omega} [IsProbabilityMeasure mu] {X : Omega -> Real}, Measurable X -> (SubExponential.PsiOneGauge mu (fun omega => X omega ^ 2) < (⊤ : ENNReal) ↔ SubGaussian.PsiTwoGauge mu X < (⊤ : ENNReal)) ∧ SubExponential.PsiOneGauge mu (fun omega => X omega ^ 2) = SubGaussian.PsiTwoGauge mu X ^ 2hdp_
02_ · 3 more declarations under this itemhlem_ h2_ d7_ d6_ exact Proposition 2.1.2
Printed page 13: the two-sided Mills-ratio estimate for the upper tail of a standard-normal random variable.
Lean statement
theorem hdp_02_hprop_h2_d1_d2 (t : ℝ) (ht : 0 < t) : (Real.sqrt (2 * Real.pi))⁻¹ * ((1 / t - 1 / t ^ 3) * Real.exp (-(t ^ 2) / 2)) ≤ standardNormalLaw.real (Ici t) ∧ standardNormalLaw.real (Ici t) ≤ (Real.sqrt (2 * Real.pi))⁻¹ * ((1 / t) * Real.exp (-(t ^ 2) / 2))hdp_
02_ · 3 more declarations under this itemhprop_ h2_ d1_ d2 Proposition 2.4.1
Lean statement
theorem hdp_02_hprop_h2_d4_d1 (n : ℕ) (hn : 2 ≤ n) (p : Set.Icc (0 : ℝ) 1) (hd : 4000 * Real.log (n : ℝ) ≤ (n - 1) * (p : ℝ)) : (NumStability.HDP.Scalar.IndependentSums.Chernoff.erdosRenyiModel n p).graphLaw.real {G | ∀ v : Fin n, |((NumStability.HDP.Scalar.IndependentSums.Chernoff.erdosRenyiModel n p).degree v G : ℝ) - (n - 1) * (p : ℝ)| < ((n - 1) * (p : ℝ)) / 10} ≥ (9 : ℝ) / 10Theorem 2.2.2
Lean statement
theorem hdp_02_hthm_h2_d2_d2 {ι Ω : Type*} [Fintype ι] [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {X : ι → Ω → ℝ} {a : ι → ℝ} {t : ℝ} (hX : ∀ i, Measurable (X i)) (hIndep : iIndepFun X μ) (hLaw : ∀ i, Measure.map (X i) μ = NumStability.HDP.Scalar.IndependentSums.Hoeffding.rademacherPMF.toMeasure) (ht : 0 ≤ t) : μ.real {ω | ∑ i, a i * X i ω ≥ t} ≤ Real.exp (-t ^ 2 / (2 * ∑ i, (a i) ^ 2))Theorem 2.2.5
Theorem 2.2.5 with the symmetric Bernoulli law as its only distributional premise; sign symmetry and exponential integrability are consequences.
Lean statement
theorem hdp_02_hthm_h2_d2_d5_source {ι Ω : Type*} [Fintype ι] [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {X : ι → Ω → ℝ} {a : ι → ℝ} {t : ℝ} (hX : ∀ i, Measurable (X i)) (hIndep : iIndepFun X μ) (hLaw : ∀ i, Measure.map (X i) μ = NumStability.HDP.Scalar.IndependentSums.Hoeffding.rademacherPMF.toMeasure) (ht : 0 < t) : μ.real {ω | |∑ i, a i * X i ω| ≥ t} ≤ 2 * Real.exp (-t ^ 2 / (2 * ∑ i, (a i) ^ 2))Theorem 2.2.6
Theorem 2.2.6 without a spurious positive-total-width premise. When all interval widths vanish, the displayed right-hand side is one and the result is the universal probability bound.
Lean statement
theorem hdp_02_hthm_h2_d2_d6_source {ι Ω : Type*} [Fintype ι] [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {X : ι → Ω → ℝ} {m M : ι → ℝ} {t : ℝ} (hX : ∀ i, Measurable (X i)) (hIndep : iIndepFun X μ) (hbound : ∀ i, ∀ᵐ ω ∂μ, X i ω ∈ Set.Icc (m i) (M i)) (ht : 0 < t) : μ.real {ω | ∑ i, (X i ω - ∫ y, X i y ∂μ) ≥ t} ≤ Real.exp (-2 * t ^ 2 / (∑ i, ‖M i - m i‖ ^ 2))Theorem 2.3.1
Theorem 2.3.1 without proof-internal integrability assumptions and with the zero-mean Bernoulli family included.
Lean statement
theorem hdp_02_hthm_h2_d3_d1_source {ι Ω : Type*} [Fintype ι] [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {B : ι → Ω → Bool} {p : ι → ℝ≥0} (hp : ∀ i, p i ≤ 1) (hB : iIndepFun B μ) (hLaw : ∀ i, HasLaw (B i) (PMF.bernoulli (p i) (hp i)).toMeasure μ) (hMeas : ∀ i, Measurable (B i)) {t : ℝ} (ht : ∑ i, (p i : ℝ) < t) : μ.real {ω | t ≤ ∑ i, (if B i ω then 1 else 0)} ≤ Real.exp (-(∑ i, (p i : ℝ))) * ((Real.exp 1 * (∑ i, (p i : ℝ)) / t) ^ t)Theorem 2.9.1
Lean statement
theorem hdp_02_hthm_h2_d9_d1_exact : hdp_02_hthm_h2_d9_d1__contract_typehdp_
02_ · 2 more declarations under this itemhthm_ h2_ d9_ d1_ exact Theorem 2.9.2
Lean statement
theorem hdp_02_hthm_h2_d9_d2_exact : hdp_02_hthm_h2_d9_d2__contract_typehdp_
02_ · 1 more declaration under this itemhthm_ h2_ d9_ d2_ exact
Equations and other results
Result
Lean statement
theorem hdp_02_hbody_h2_d6_hconstant_hpsi2 : ∃ C : ℝ, 1 ≤ C ∧ ∀ {Omega : Type*} [MeasurableSpace Omega] {mu : Measure Omega} [IsProbabilityMeasure mu] (a : ℝ), NumStability.HDP.Scalar.SubGaussian.PsiTwoNorm mu (fun _ : Omega => a) ≤ ENNReal.ofReal (C * |a|)Result
Every fixed vertex has the stated binomial degree law and an absolute Chernoff exponent for a ten-percent deviation. The absolute constant remains existentially quantified as in the source.
Lean statement
theorem hdp_02_hbody_h2_d4_hdegree_hchernoff : (∀ (n : ℕ) (p : Set.Icc (0 : ℝ) 1) (v : Fin n), HasLaw ((NumStability.HDP.Scalar.IndependentSums.Chernoff.erdosRenyiModel n p).degree v) (NumStability.HDP.Scalar.IndependentSums.Chernoff.graphBinomialLaw n p) (NumStability.HDP.Scalar.IndependentSums.Chernoff.erdosRenyiModel n p).graphLaw) ∧ ∃ c : ℝ, 0 < c ∧ ∀ (n : ℕ) (p : Set.Icc (0 : ℝ) 1) (v : Fin n), (NumStability.HDP.Scalar.IndependentSums.Chernoff.erdosRenyiModel n p).graphLaw.real {G | (1 / 10 : ℝ) * ((n - 1) * (p : ℝ)) ≤ |((NumStability.HDP.Scalar.IndependentSums.Chernoff.erdosRenyiModel n p).degree v G : ℝ) - (n - 1) * (p : ℝ)|} ≤ 2 * Real.exp (-(c * ((n - 1) * (p : ℝ))))Result
The probability of at least one bad event is bounded by the sum of the individual bad-event probabilities.
Lean statement
theorem hdp_02_hbody_h2_d4_hunion_hbound {Ω ι : Type*} [MeasurableSpace Ω] [Fintype ι] (μ : Measure Ω) (Bad : ι → Set Ω) : μ.real (⋃ i, Bad i) ≤ ∑ i, μ.real (Bad i)Result
Section 2.1, printed page 12: if
S_Nis the number of heads inNindependent fair coin tosses, thenE S_N = N / 2andVar(S_N) = N / 4.Lean statement
theorem hdp_02_hbody_h2_d1_hsn_hmoments {ι Ω : Type*} [Fintype ι] [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {B : ι → Ω → Bool} (_hN : 0 < Fintype.card ι) (hB : ∀ i, Measurable (B i)) (hIndep : iIndepFun B μ) (hLaw : ∀ i, Measure.map (B i) μ = fairBernoulliPMF.toMeasure) : (∫ ω, ∑ i, bernoulliIndicator (B i ω) ∂μ) = (Fintype.card ι : ℝ) / 2 ∧ Var[fun ω ↦ ∑ i, bernoulliIndicator (B i ω); μ] = (Fintype.card ι : ℝ) / 4Result
Printed page 14: in
N = 2nfair tosses the central count has probability2⁻ᴺ * binom(N,N/2), the standardized count has the same mass at zero, and that mass is comparable to1 / sqrt N.Lean statement
theorem hdp_02_hbody_h2_d1_hbinom_hcentral : (∀ n : ℕ, PMF.binomial (1 / 2) (by norm_num) (2 * n) ⟨n, by omega⟩ = (2 : ℝ≥0∞)⁻¹ ^ (2 * n) * (Nat.choose (2 * n) n : ℝ≥0∞)) ∧ (∀ n : ℕ, 0 < n → standardizedFairBinomial n 0 = PMF.binomial (1 / 2) (by norm_num) (2 * n) ⟨n, by omega⟩) ∧ (fun n : ℕ => (2 : ℝ)⁻¹ ^ (2 * n) * (Nat.choose (2 * n) n : ℝ)) =Θ[Filter.atTop] (fun n : ℕ => 1 / Real.sqrt (2 * (n : ℝ)))Result
Printed page 14: continuity of the standard normal law gives
P {g = 0} = 0.Lean statement
theorem hdp_02_hbody_h2_d1_hgaussian_hatom : standardNormalLaw {0} = 0Result
Section 2.1, printed page 13: with
Z_N = (S_N - N/2) / sqrt (N/4), the eventsS_N ≥ 3N/4andZ_N ≥ sqrt (N/4)coincide.Lean statement
theorem hdp_02_hbody_h2_d1_hzn_hidentity {ι Ω : Type*} [Fintype ι] [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {B : ι → Ω → Bool} (hN : 0 < Fintype.card ι) (_hB : ∀ i, Measurable (B i)) (_hIndep : iIndepFun B μ) (_hLaw : ∀ i, Measure.map (B i) μ = fairBernoulliPMF.toMeasure) : {ω | ∑ i, bernoulliIndicator (B i ω) ≥ (3 / 4 : ℝ) * (Fintype.card ι : ℝ)} = {ω | (∑ i, bernoulliIndicator (B i ω) - (Fintype.card ι : ℝ) / 2) / Real.sqrt ((Fintype.card ι : ℝ) / 4) ≥ Real.sqrt ((Fintype.card ι : ℝ) / 4)}Result
Printed page 14, footnote 1: two-sided and one-sided comparison up to positive constant factors, either everywhere or eventually at infinity.
Lean statement
theorem hdp_02_hnotation_h2_d1_hasymptotic : ∀ f g : ℕ → ℝ, (IsComparableEverywhere f g ↔ ∃ c C : ℝ, 0 < c ∧ 0 < C ∧ ∀ n, c * f n ≤ g n ∧ g n ≤ C * f n) ∧ (IsComparableEventually f g ↔ ∃ c C : ℝ, 0 < c ∧ 0 < C ∧ ∀ᶠ n in Filter.atTop, c * f n ≤ g n ∧ g n ≤ C * f n) ∧ (IsLessSimEverywhere f g ↔ ∃ C : ℝ, 0 < C ∧ ∀ n, f n ≤ C * g n) ∧ (IsLessSimEventually f g ↔ ∃ C : ℝ, 0 < C ∧ ∀ᶠ n in Filter.atTop, f n ≤ C * g n) ∧ (IsGreaterSimEverywhere f g ↔ ∃ c : ℝ, 0 < c ∧ ∀ n, g n ≤ c * f n) ∧ (IsGreaterSimEventually f g ↔ ∃ c : ℝ, 0 < c ∧ ∀ᶠ n in Filter.atTop, g n ≤ c * f n)Result
Lean statement
theorem hdp_02_hbody_h2_d2_hcosh_hmgf {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {X : Ω → ℝ} (hX : Measurable X) (hLaw : Measure.map X μ = NumStability.HDP.Scalar.IndependentSums.Hoeffding.rademacherPMF.toMeasure) (lam a : ℝ) : (∫ ω, Real.exp (lam * (a * X ω)) ∂μ) = (Real.exp (lam * a) + Real.exp (-(lam * a))) / 2 ∧ (∫ ω, Real.exp (lam * (a * X ω)) ∂μ) = Real.cosh (lam * a)Result
Lean statement
theorem hdp_02_hbody_h2_d2_hcoin_hbound {ι Ω : Type*} [Fintype ι] [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {B : ι → Ω → Bool} (hB : ∀ i, Measurable (B i)) (hIndep : iIndepFun B μ) (hLaw : ∀ i, Measure.map (B i) μ = NumStability.HDP.Scalar.IndependentSums.Hoeffding.fairBernoulliPMF.toMeasure) (hN : 0 < Fintype.card ι) : μ.real {ω | ∑ i, NumStability.HDP.Scalar.IndependentSums.Hoeffding.bernoulliIndicator (B i ω) ≥ (3 / 4 : ℝ) * (Fintype.card ι : ℝ)} ≤ Real.exp (-(Fintype.card ι : ℝ) / 8)Result
Lean statement
theorem hdp_02_hbody_h2_d2_htwo_hsided_hsplit {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {S : Ω → ℝ} (hS : Measurable S) {t : ℝ} (ht : 0 < t) : μ.real {ω | |S ω| ≥ t} = μ.real {ω | S ω ≥ t} + μ.real {ω | -S ω ≥ t}Result
The affine Bernoulli coupling is Rademacher exactly at the fair parameter.
Lean statement
theorem affineBernoulliIsRademacherIff {p : ℝ≥0} (hp : p ≤ 1) : PMF.map rademacherValue (PMF.bernoulli p hp) = rademacherPMF ↔ p = (1 / 2 : ℝ≥0)Result
The elementary exponential inequality used in the Bernoulli MGF estimate.
Lean statement
theorem hdp_02_hbody_h2_d3_hone_hplus_hx (x : ℝ) : 1 + x ≤ Real.exp xResult
Lean statement
theorem hdp_02_hlem_hbernoulli_hmgf_hbound_scalar (p : ℝ≥0) (hp : p ≤ 1) (lam : ℝ) : ((∫ b : Bool, Real.exp (lam * (if b then 1 else 0)) ∂ (PMF.bernoulli p hp).toMeasure) = 1 + (Real.exp lam - 1) * (p : ℝ)) ∧ (1 + (Real.exp lam - 1) * (p : ℝ) ≤ Real.exp ((Real.exp lam - 1) * (p : ℝ)))Result
Every vertex in the Erdős--Rényi model
G(n,p)has expected degree(n - 1) p.Lean statement
theorem hdp_02_hbody_h2_d4_hexpected_hdegree (n : ℕ) (p : Set.Icc (0 : ℝ) 1) (v : Fin n) : ∫ G : SimpleGraph (Fin n), ((hdp_02_hdef_herdos_hrenyi n p).degree v G : ℝ) ∂(hdp_02_hdef_herdos_hrenyi n p).graphLaw = ((n - 1 : ℕ) : ℝ) * (p : ℝ)Result
Section 2.5's square-MGF display without a zero-gauge quotient.
Lean statement
theorem hdp_02_hbody_h2_d5_hpsi2_hsquare_hpoint_effectiveDomain {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {X : Ω → ℝ} (hX : Measurable X) (hFinite : PsiTwoGauge μ X < ∞) : PsiTwoSquareMomentEffectiveDomain μ XResult
Section 2.5's quantitative minimality assertion with every quotient kept on its positive-gauge effective domain.
Lean statement
theorem hdp_02_hbody_h2_d5_hpsi2_hminimality_effectiveDomain : ∃ C : ℝ, 1 ≤ C ∧ ∀ {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {X : Ω → ℝ}, Measurable X → PsiTwoGauge μ X < ∞ → PsiTwoDisplayedBoundsEffectiveDomain μ X ∧ (∀ i : SubGaussianPropertyKind, (i = .tail ∨ i = .moment ∨ i = .squarePoint) → ∀ {K : ℝ}, 0 < K → SubGaussianProperty μ X i K → PsiTwoGauge μ X ≤ ENNReal.ofReal (C * K)) ∧ ((Integrable X μ ∧ (∫ ω, X ω ∂μ) = 0) → ∀ {K : ℝ}, 0 < K → SubGaussianProperty μ X .linearMGF K → PsiTwoGauge μ X ≤ ENNReal.ofReal (C * K))Result
Lean statement
theorem hdp_02_hbody_h2_d7_hgaussian_hsquare_htail (t : ℝ) (ht : 0 < t) : standardNormalLaw.real {x : ℝ | x ^ 2 > t} = standardNormalLaw.real {x : ℝ | |x| > Real.sqrt t} ∧ 2 * (Real.sqrt (2 * Real.pi))⁻¹ * ((1 / Real.sqrt t - 1 / (Real.sqrt t) ^ 3) * Real.exp (-t / 2)) ≤ standardNormalLaw.real {x : ℝ | x ^ 2 > t} ∧ standardNormalLaw.real {x : ℝ | x ^ 2 > t} ≤ 2 * (Real.sqrt (2 * Real.pi))⁻¹ * ((1 / Real.sqrt t) * Real.exp (-t / 2))Result
Lean statement
theorem hdp_02_hbody_h2_d7_horlicz_hbanach_exact : hdp_02_hbody_h2_d7_horlicz_hbanach__contract_typeResult
Lean statement
theorem hdp_02_hbody_h2_d2_hwlog_hnorm {ι Ω : Type*} [Fintype ι] (X : ι → Ω → ℝ) (a : ι → ℝ) (t : ℝ) (_ht : 0 ≤ t) : ((∑ i, (a i) ^ 2 = 0) ∧ {ω | ∑ i, a i * X i ω ≥ t} = {_ω | (0 : ℝ) ≥ t}) ∨ ((0 < ∑ i, (a i) ^ 2) ∧ (∑ i, (a i / Real.sqrt (∑ j, (a j) ^ 2)) ^ 2 = 1) ∧ {ω | ∑ i, a i * X i ω ≥ t} = {ω | ∑ i, (a i / Real.sqrt (∑ j, (a j) ^ 2)) * X i ω ≥ t / Real.sqrt (∑ j, (a j) ^ 2)})Equation (2.1)
Printed page 12: Chebyshev's
4/Nbound for at least3N/4heads.Lean statement
theorem hdp_02_heq_h2_d1 {ι Ω : Type*} [Fintype ι] [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {B : ι → Ω → Bool} (hN : 0 < Fintype.card ι) (hB : ∀ i, Measurable (B i)) (hIndep : iIndepFun B μ) (hLaw : ∀ i, Measure.map (B i) μ = fairBernoulliPMF.toMeasure) : μ.real {ω | ∑ i, bernoulliIndicator (B i ω) ≥ (3 / 4 : ℝ) * (Fintype.card ι : ℝ)} ≤ μ.real {ω | |∑ i, bernoulliIndicator (B i ω) - (Fintype.card ι : ℝ) / 2| ≥ (Fintype.card ι : ℝ) / 4} ∧ μ.real {ω | |∑ i, bernoulliIndicator (B i ω) - (Fintype.card ι : ℝ) / 2| ≥ (Fintype.card ι : ℝ) / 4} ≤ 4 / (Fintype.card ι : ℝ)hdp_
02_ · 1 more declaration under this itemheq_ h2_ d1 Equation (2.3)
Printed page 13: for
t ≥ 1, the standard-normal upper tail is bounded by the standard-normal density att.Lean statement
theorem hdp_02_heq_h2_d3 (t : ℝ) (ht : 1 ≤ t) : standardNormalLaw.real (Ici t) ≤ (Real.sqrt (2 * Real.pi))⁻¹ * Real.exp (-(t ^ 2) / 2)hdp_
02_ · 1 more declaration under this itemheq_ h2_ d3 Equation (2.5)
The one-sided exponential Markov bound at a positive Laplace parameter.
Lean statement
theorem hdp_02_heq_h2_d5 {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {S : Ω → ℝ} (hS : Measurable S) {lam t : ℝ} (hlam : 0 < lam) (hExp : Integrable (fun ω => Real.exp (lam * S ω)) μ) : (μ.real (S ⁻¹' Set.Ici t) = μ.real ((fun ω => Real.exp (lam * S ω)) ⁻¹' Set.Ici (Real.exp (lam * t)))) ∧ (μ.real (S ⁻¹' Set.Ici t) ≤ Real.exp (-(lam * t)) * (∫ ω, Real.exp (lam * S ω) ∂μ))Equation (2.6)
Lean statement
theorem hdp_02_hlem_hmgf_hindependent_hsum {ι Ω : Type*} [Fintype ι] [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {X : ι → Ω → ℝ} (lam : ℝ) (a : ι → ℝ) (hX : iIndepFun X μ) (hExp : ∀ i, Integrable (fun ω => Real.exp (lam * (a i * X i ω))) μ) : ∫ ω, Real.exp (lam * ∑ i, a i * X i ω) ∂μ = ∏ i, ∫ ω, Real.exp (lam * (a i * X i ω)) ∂μEquation (2.7)
The exponential-Markov bound for a sum of independent Bernoulli indicators, with its MGF factored into the product of the coordinate MGFs as in (2.7).
Lean statement
theorem hdp_02_heq_h2_d7 {ι Ω : Type*} [Fintype ι] [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {B : ι → Ω → Bool} (hB : iIndepFun B μ) (hMeas : ∀ i, Measurable (B i)) {lam t : ℝ} (hlam : 0 < lam) : μ.real {ω | t ≤ ∑ i, (if B i ω then 1 else 0)} ≤ Real.exp (-(lam * t)) * ∏ i, ∫ ω, Real.exp (lam * (if B i ω then 1 else 0)) ∂μEquation (2.8)
Display (2.8), exposed separately at its printed locator.
Lean statement
theorem hdp_02_heq_h2_d8 (rate : ℝ≥0) {t : ℝ} (ht : (rate : ℝ) < t) : (poissonMeasure rate).real {n : ℕ | t ≤ (n : ℝ)} ≤ Real.exp (-(rate : ℝ)) * ((Real.exp 1 * (rate : ℝ) / t) ^ t)Equation (2.10)
For a standard normal variable and every nonnegative threshold,
P{|X| ≥ t} ≤ 2 exp(-t²/2).Lean statement
theorem hdp_02_heq_h2_d10 (t : ℝ) (ht : 0 ≤ t) : standardNormalLaw.real {x : ℝ | |x| ≥ t} ≤ 2 * Real.exp (-(t ^ 2) / 2)Equation (2.11)
Lean statement
theorem standardNormalLpNormGrowth : ∃ C : ℝ, 0 < C ∧ ∀ p : ℝ, 1 ≤ p → (∫ x : ℝ, |x| ^ p ∂(gaussianReal 0 1)) ^ (1 / p) ≤ C * Real.sqrt pEquation (2.12)
Lean statement
theorem hdp_02_heq_h2_d12 (lam : ℝ) : ∫ x, Real.exp (lam * x) ∂(gaussianReal 0 1) = Real.exp (lam ^ 2 / 2)Equation (2.13)
Lean statement
theorem psiTwoNorm_eq_sInf {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} {X : Ω → ℝ} (_hX : Measurable X) (_hSub : IsSubGaussian μ X) : PsiTwoNorm μ X = sInf {t : ℝ≥0∞ | PsiTwoAdmissible μ X t}Equation (2.14)
Lean statement
theorem psiTwoGaugeToTail {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {X : Ω → ℝ} (hX : Measurable X) (hFinite : PsiTwoGauge μ X < ∞) {t : ℝ} (ht : 0 ≤ t) : μ.real {ω | |X ω| ≥ t} ≤ 2 * Real.exp (-t ^ 2 / (2 * (PsiTwoGauge μ X).toReal) ^ 2)Equation (2.15)
Lean statement
theorem psiTwoGaugeToLpMomentGrowth {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {X : Ω → ℝ} (hX : Measurable X) (hFinite : PsiTwoGauge μ X < ∞) : LpMomentGrowth μ X (16 * Real.exp 1 * (PsiTwoGauge μ X).toReal)Equation (2.16)
Lean statement
theorem psiTwoGaugeToMGF {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {X : Ω → ℝ} (hX : Measurable X) (hFinite : PsiTwoGauge μ X < ∞) (hCenter : Integrable X μ ∧ (∫ ω, X ω ∂μ) = 0) (lam : ℝ) : Integrable (fun ω => Real.exp (lam * X ω)) μ ∧ (∫ ω, Real.exp (lam * X ω) ∂μ) ≤ Real.exp ((128 * Real.exp 1) ^ 2 * lam ^ 2 * (PsiTwoGauge μ X).toReal ^ 2)Equation (2.17)
Lean statement
theorem essentiallyBoundedPsiTwoGauge {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {X : Ω → ℝ} {B : ℝ} (hX : Measurable X) (hB : 0 < B) (hBound : ∀ᵐ ω ∂μ, |X ω| ≤ B) : PsiTwoGauge μ X ≤ ENNReal.ofReal (B / Real.sqrt (Real.log 2))Equation (2.18)
Lean statement
theorem hdp_02_heq_h2_d18 {ι Ω : Type*} [Fintype ι] [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {X : ι → Ω → ℝ} {σ : ι → ℝ≥0} (a : ι → ℝ) (hLaw : ∀ i, HasLaw (X i) (gaussianReal 0 (σ i)) μ) (hIndep : iIndepFun X μ) : HasLaw (fun ω => ∑ i, a i * X i ω) (gaussianReal 0 (∑ i, Real.toNNReal ((a i) ^ 2) * σ i)) μEquation (2.19)
Subtracting the expectation cannot increase the
L²seminorm of a square-integrable real random variable.Lean statement
theorem hdp_02_heq_h2_d19 {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {X : Ω → ℝ} (hX : MemLp X 2 μ) : eLpNorm (fun ω => X ω - ∫ x, X x ∂μ) 2 μ ≤ eLpNorm X 2 μhdp_
02_ · 1 more declaration under this itemheq_ h2_ d19 Equation (2.20)
Lean statement
theorem hdp_02_heq_h2_d20 {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {X : Ω → ℝ} (_hSub : NumStability.HDP.Scalar.SubGaussian.IsSubGaussian μ X) : NumStability.HDP.Scalar.SubGaussian.PsiTwoNorm μ (fun ω => X ω - ∫ x, X x ∂μ) ≤ NumStability.HDP.Scalar.SubGaussian.PsiTwoNorm μ X + NumStability.HDP.Scalar.SubGaussian.PsiTwoNorm μ (fun _ : Ω => ∫ x, X x ∂μ)hdp_
02_ · 1 more declaration under this itemheq_ h2_ d20 Equation (2.21)
The
psi_1gauge is the infimum of its positive finite scales satisfying the displayed exponential-moment bound.Lean statement
theorem hdp_02_heq_h2_d21_exact : ∀ {Omega : Type*} [MeasurableSpace Omega] (mu : Measure Omega) (X : Omega -> Real), PsiOneGauge mu X = sInf {t : ENNReal | PsiOneAdmissible mu X t}hdp_
02_ · 1 more declaration under this itemheq_ h2_ d21_ exact Equation (2.22)
After normalizing both
psi_2scales to one, both quadratic exponential moments are at most two.Lean statement
theorem hdp_02_heq_h2_d22_exact : ∀ {Omega : Type*} [MeasurableSpace Omega] {mu : Measure Omega} [IsProbabilityMeasure mu] {X Y : Omega -> Real}, SubGaussian.IsSubGaussian mu X -> SubGaussian.IsSubGaussian mu Y -> SubGaussian.PsiTwoNorm mu X = 1 -> SubGaussian.PsiTwoNorm mu Y = 1 -> (∫ omega, Real.exp (X omega ^ 2) ∂mu) ≤ 2 ∧ (∫ omega, Real.exp (Y omega ^ 2) ∂mu) ≤ 2hdp_
02_ · 1 more declaration under this itemheq_ h2_ d22_ exact Equation (2.23)
Printed page 36: exponential Markov followed by factorization of the MGF of the independent sum. The extended nonnegative integrals preserve the source's large-
λcases, where an individual MGF can be infinite.Lean statement
theorem hdp_02_heq_h2_d23 {ι Ω : Type*} [Fintype ι] [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {X : ι → Ω → ℝ} (hne : (Finset.univ : Finset ι).Nonempty) (hX : ∀ i, Measurable (X i)) (hCenter : ∀ i, Integrable (X i) μ ∧ (∫ ω, X i ω ∂μ) = 0) (hSubExp : ∀ i, PsiOneGauge μ (X i) < ∞) (hIndep : iIndepFun X μ) {lam t : ℝ} (hlam : 0 < lam) (ht : 0 ≤ t) : μ {ω | ∑ i, X i ω ≥ t} ≤ ENNReal.ofReal (Real.exp (-(lam * t))) * ∏ i, ∫⁻ ω, ENNReal.ofReal (Real.exp (lam * X i ω)) ∂μEquation (2.24)
Equation (2.24) with its nonnegative denominator cleared. This is equivalent to the printed window when the maximum
ψ₁gauge is positive and also expresses the correct unbounded window for the all-zero family.Lean statement
theorem hdp_02_heq_h2_d24_effectiveWindow : hdp_02_heq_h2_d24_effectiveWindow__contract_typehdp_
02_ · 1 more declaration under this itemheq_ h2_ d24_ effective Window Example 2.5.8a
Lean statement
theorem hdp_02_hexample_h2_d5_d8a : ∃ C : ℝ, 0 < C ∧ NumStability.HDP.Scalar.SubGaussian.PsiTwoGauge (ProbabilityTheory.gaussianReal 0 1) id ≤ ENNReal.ofReal C ∧ ∀ σ : ℝ, 0 ≤ σ → NumStability.HDP.Scalar.SubGaussian.PsiTwoGauge (ProbabilityTheory.gaussianReal 0 (⟨σ ^ 2, sq_nonneg σ⟩ : ℝ≥0)) id ≤ ENNReal.ofReal (C * σ)Example 2.5.8c
Lean statement
theorem hdp_02_hexample_h2_d5_d8c {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {X : Ω → ℝ} {B : ℝ} (hX : Measurable X) (hB : 0 < B) (hBound : ∀ᵐ ω ∂μ, |X ω| ≤ B) : NumStability.HDP.Scalar.SubGaussian.PsiTwoGauge μ X ≤ ENNReal.ofReal (B / Real.sqrt (Real.log 2))Example 2.7.8
Canonical sub-exponential variables and the exact positive-rate exponential-law scales in the book's normalization.
Lean statement
theorem hdp_02_hexample_h2_d7_d8 : hdp_02_hexample_h2_d7_d8__contract_typehdp_
02_ · 1 more declaration under this itemhexample_ h2_ d7_ d8 Example 2.7.12
Lean statement
theorem hdp_02_hexample_h2_d7_d12_exact : hdp_02_hexample_h2_d7_d12__contract_typehdp_
02_ · 2 more declarations under this itemhexample_ h2_ d7_ d12_ exact Example 2.7.13
Lean statement
theorem hdp_02_hexample_h2_d7_d13_exact : hdp_02_hexample_h2_d7_d13__contract_typehdp_
02_ · 3 more declarations under this itemhexample_ h2_ d7_ d13_ exact Remark 2.3.4
Lean statement
theorem hdp_02_hrem_h2_d3_d4 (rate : ℝ≥0) (hrate : 0 < rate) : (fun k : ℕ => ProbabilityTheory.poissonPMFReal rate k) ~[Filter.atTop] (fun k : ℕ => Real.exp (-(rate : ℝ)) * (Real.exp 1 * (rate : ℝ) / (k : ℝ)) ^ k / Real.sqrt (2 * (k : ℝ) * Real.pi))hdp_
02_ · 1 more declaration under this itemhrem_ h2_ d3_ d4 Remark 2.7.14
Essentially bounded random variables are sub-gaussian, and sub-gaussian random variables have every finite absolute moment.
Lean statement
theorem hdp_02_hrem_h2_d7_d14_exact : (∀ {Omega : Type*} [MeasurableSpace Omega] {mu : Measure Omega} [IsProbabilityMeasure mu] {X : Omega -> Real} {B : Real}, Measurable X -> 0 < B -> (∀ᵐ omega ∂mu, |X omega| ≤ B) -> PsiTwoGauge mu X < (⊤ : ENNReal)) ∧ (∀ {Omega : Type*} [MeasurableSpace Omega] {mu : Measure Omega} [IsProbabilityMeasure mu] {X : Omega -> Real}, Measurable X -> PsiTwoGauge mu X < (⊤ : ENNReal) -> ∀ p : Real, 1 ≤ p -> Integrable (fun omega => |X omega| ^ p) mu)hdp_
02_ · 1 more declaration under this itemhrem_ h2_ d7_ d14_ exact
Problems and exercises
Exercise 2.1.4
Integration by parts for the unnormalized second moment on a Gaussian upper tail. This is the calculus identity behind Exercise 2.1.4.
Lean statement
theorem integral_Ioi_sq_mul_exp_neg_sq_div_two (t : ℝ) (ht : 0 < t) : (∫ x in Ioi t, x ^ 2 * Real.exp (-(x ^ 2) / 2)) = t * Real.exp (-(t ^ 2) / 2) + ∫ x in Ioi t, Real.exp (-(x ^ 2) / 2)integral_
Ioi_ · 3 more declarations under this itemsq_ mul_ exp_ neg_ sq_ div_ two Exercise 2.2.3
Lean statement
theorem hdp_02_hex_h2_d2_d3 (x : ℝ) : Real.cosh x ≤ Real.exp (x ^ 2 / 2)Exercise 2.2.7
Discharged with the exact constant
2stated in Theorem 2.2.6.Lean statement
theorem hdp_02_hex_h2_d2_d7_source {ι Ω : Type*} [Fintype ι] [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {X : ι → Ω → ℝ} {m M : ι → ℝ} {t : ℝ} (hX : ∀ i, Measurable (X i)) (hIndep : iIndepFun X μ) (hbound : ∀ i, ∀ᵐ ω ∂μ, X i ω ∈ Set.Icc (m i) (M i)) (ht : 0 < t) : μ.real {ω | ∑ i, (X i ω - ∫ y, X i y ∂μ) ≥ t} ≤ Real.exp (-2 * t ^ 2 / (∑ i, ‖M i - m i‖ ^ 2))Exercise 2.2.8
Lean statement
theorem hdp_02_hex_h2_d2_d8 {ι Ω : Type*} [Fintype ι] [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {W : ι → Ω → ℝ} {δ ε : ℝ} (hW : ∀ i, Measurable (W i)) (hIndep : iIndepFun W μ) (hbound : ∀ i, ∀ᵐ ω ∂μ, W i ω ∈ Set.Icc 0 1) (hmean : ∀ i, (∫ y, W i y ∂μ) ≤ 1 / 2 - δ) (hδ : 0 < δ) (hε0 : 0 < ε) (hε1 : ε < 1) (hN : 0 < Fintype.card ι) (hNlarge : Real.log (1 / ε) / (2 * δ ^ 2) ≤ (Fintype.card ι : ℝ)) : μ.real {ω | ∑ i, W i ω ≥ (Fintype.card ι : ℝ) / 2} ≤ εExercise 2.2.9a
Exercise 2.2.9(a) with the absolute sample-size constant
C = 4.Lean statement
theorem hdp_02_hex_h2_d2_d9a {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] (N : ℕ) (hN : 0 < N) {X : Fin N → Ω → ℝ} (hMeas : ∀ i, Measurable (X i)) (hX : ∀ i, MemLp (X i) 2 μ) (hIndep : Pairwise ((· ⟂ᵢ[μ] ·) on X)) (hIdent : ∀ i, IdentDistrib (X i) (X ⟨0, hN⟩) μ μ) {σ ε : ℝ} (hVar : Var[X ⟨0, hN⟩; μ] = σ ^ 2) (hε : 0 < ε) (hNlarge : 4 * σ ^ 2 / ε ^ 2 ≤ (N : ℝ)) : μ.real {ω | |(N : ℝ)⁻¹ * ∑ i, X i ω - ∫ y, X ⟨0, hN⟩ y ∂μ| ≥ ε} ≤ 1 / 4Exercise 2.2.9b
Exercise 2.2.9(b), with
nobservations in each of2k+1independent blocks. The explicit weak-estimate constant is4, and the amplification constant is the one from Exercise 2.2.8.Lean statement
theorem hdp_02_hex_h2_d2_d9b {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] (n k : ℕ) (hn : 0 < n) {X : Fin (2 * k + 1) → Fin n → Ω → ℝ} (hMeas : ∀ j i, Measurable (X j i)) (hLp : ∀ j i, MemLp (X j i) 2 μ) (hBlockIndep : iIndepFun (fun j ω i => X j i ω) μ) (hWithin : ∀ j, Pairwise ((· ⟂ᵢ[μ] ·) on X j)) (hIdent : ∀ j i, IdentDistrib (X j i) (X ⟨0, by omega⟩ ⟨0, hn⟩) μ μ) {σ ε δ : ℝ} (hVar : Var[X ⟨0, by omega⟩ ⟨0, hn⟩; μ] = σ ^ 2) (hε : 0 < ε) (hnLarge : 4 * σ ^ 2 / ε ^ 2 ≤ (n : ℝ)) (hδ0 : 0 < δ) (hδ1 : δ < 1) (hkLarge : Real.log (1 / δ) / (2 * (1 / 4 : ℝ) ^ 2) ≤ (Fintype.card (Fin (2 * k + 1)) : ℝ)) : μ.real {ω | ε ≤ |NumStability.HDP.Scalar.IndependentSums.MedianOfMeans.oddMedian k (fun j => (n : ℝ)⁻¹ * ∑ i, X j i ω) - ∫ y, X ⟨0, by omega⟩ ⟨0, hn⟩ y ∂μ|} ≤ δExercise 2.2.10a
Lean statement
theorem hdp_02_hex_h2_d2_d10a {f : ℝ → ℝ} (hf : NumStability.HDP.Scalar.IndependentSums.Hoeffding.BoundedDensityOnNonnegative f) {t : ℝ} (ht : 0 < t) : ∫ x, Real.exp (-t * x) * f x ∂(volume : Measure ℝ) ≤ 1 / tExercise 2.3.2
Exercise 2.3.2 on the effective domain of its printed real expression, with the exact boundary behavior stated separately.
Lean statement
theorem hdp_02_hex_h2_d3_d2_effectiveDomain {ι Ω : Type*} [Fintype ι] [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {B : ι → Ω → Bool} {p : ι → ℝ≥0} (hp : ∀ i, p i ≤ 1) (hB : iIndepFun B μ) (hLaw : ∀ i, HasLaw (B i) (PMF.bernoulli (p i) (hp i)).toMeasure μ) (hMeas : ∀ i, Measurable (B i)) {t : ℝ} (htμ : t < ∑ i, (p i : ℝ)) : (0 < t → μ.real {ω | ∑ i, (if B i ω then (1 : ℝ) else 0) ≤ t} ≤ Real.exp (-(∑ i, (p i : ℝ))) * ((Real.exp 1 * (∑ i, (p i : ℝ)) / t) ^ t)) ∧ (t = 0 → μ.real {ω | ∑ i, (if B i ω then (1 : ℝ) else 0) ≤ t} ≤ Real.exp (-(∑ i, (p i : ℝ)))) ∧ (t < 0 → μ.real {ω | ∑ i, (if B i ω then (1 : ℝ) else 0) ≤ t} = 0)hdp_
02_ · 2 more declarations under this itemhex_ h2_ d3_ d2_ effective Domain Exercise 2.3.3
The Poisson upper-tail estimate stated in Exercise 2.3.3.
Lean statement
theorem hdp_02_hex_h2_d3_d3 (rate : ℝ≥0) {t : ℝ} (ht : (rate : ℝ) < t) : (poissonMeasure rate).real {n : ℕ | t ≤ (n : ℝ)} ≤ Real.exp (-(rate : ℝ)) * ((Real.exp 1 * (rate : ℝ) / t) ^ t)Exercise 2.3.5
Preserving the book's deliberately unnamed absolute constant as one existential witness uniform over every finite Bernoulli family and every relative deviation in
(0, 1].Lean statement
theorem hdp_02_hex_h2_d3_d5 : ∃ c : ℝ, 0 < c ∧ ∀ (ι Ω : Type*) [Fintype ι] [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ] (B : ι → Ω → Bool) (p : ι → ℝ≥0) (hp : ∀ i, p i ≤ 1), iIndepFun B μ → (∀ i, HasLaw (B i) (PMF.bernoulli (p i) (hp i)).toMeasure μ) → (∀ i, Measurable (B i)) → ∀ δ : ℝ, 0 < δ → δ ≤ 1 → μ.real {ω | δ * (∑ i, (p i : ℝ)) ≤ |(∑ i, (if B i ω then 1 else 0)) - ∑ i, (p i : ℝ)|} ≤ 2 * Real.exp (-(c * (∑ i, (p i : ℝ)) * δ ^ 2))hdp_
02_ · 1 more declaration under this itemhex_ h2_ d3_ d5 Exercise 2.3.6
Preserving the book's deliberately unnamed absolute constant as one existential witness that is uniform in the Poisson rate and deviation threshold.
Lean statement
theorem hdp_02_hex_h2_d3_d6 : ∃ c : ℝ, 0 < c ∧ ∀ (rate : ℝ≥0), 0 < rate → ∀ {t : ℝ}, 0 < t → t ≤ (rate : ℝ) → (poissonMeasure rate).real {n : ℕ | t ≤ |(n : ℝ) - (rate : ℝ)|} ≤ 2 * Real.exp (-(c * t ^ 2 / (rate : ℝ)))hdp_
02_ · 1 more declaration under this itemhex_ h2_ d3_ d6 Exercise 2.3.8
The probability-weighted first-moment series of a Poisson law sums to its rate.
Lean statement
theorem poissonPMFReal_firstMoment_hasSum (rate : ℝ≥0) : HasSum (fun n : ℕ => (n : ℝ) * poissonPMFReal rate n) (rate : ℝ)poisson
PMFReal_ · 2 more declarations under this itemfirst Moment_ has Sum Exercise 2.4.2
Lean statement
theorem hdp_02_hex_h2_d4_d2 (p : ℕ → Set.Icc (0 : ℝ) 1) (C : ℝ) (hC : 0 ≤ C) (hbound : ∀ᶠ n in Filter.atTop, ((n - 1 : ℕ) : ℝ) * (p n : ℝ) ≤ C * Real.log (n : ℝ)) : ∀ᶠ n in Filter.atTop, (NumStability.HDP.Scalar.IndependentSums.Chernoff.erdosRenyiModel n (p n)).graphLaw.real {G | ∀ v : Fin n, ((NumStability.HDP.Scalar.IndependentSums.Chernoff.erdosRenyiModel n (p n)).degree v G : ℝ) < (2 * C + 5) * Real.log (n : ℝ)} ≥ (9 : ℝ) / 10Exercise 2.4.3
Lean statement
theorem hdp_02_hex_h2_d4_d3 (p : ℕ → Set.Icc (0 : ℝ) 1) (C : ℝ) (hC : 0 ≤ C) (hbound : ∀ᶠ n in Filter.atTop, ((n - 1 : ℕ) : ℝ) * (p n : ℝ) ≤ C) : ∀ᶠ n in Filter.atTop, (NumStability.HDP.Scalar.IndependentSums.Chernoff.erdosRenyiModel n (p n)).graphLaw.real {G | ∀ v : Fin n, ((NumStability.HDP.Scalar.IndependentSums.Chernoff.erdosRenyiModel n (p n)).degree v G : ℝ) < (C + 5) * Real.log (n : ℝ) / Real.log (Real.log (n : ℝ))} ≥ (9 : ℝ) / 10Exercise 2.4.4
Lean statement
theorem hdp_02_hex_h2_d4_d4 (p : ℕ → Set.Icc (0 : ℝ) 1) (k : ℕ → ℕ) (hrel : ∀ n, (k n : ℝ) = 10 * ((n - 1 : ℕ) : ℝ) * (p n : ℝ)) (hsmall : Tendsto (fun n => (k n : ℝ) / Real.log (n : ℝ)) atTop (𝓝 0)) : ∀ᶠ n in atTop, (erdosRenyiModel n (p n)).graphLaw.real {G | ∃ v : Fin n, (erdosRenyiModel n (p n)).degree v G = k n} ≥ (9 : ℝ) / 10hdp_
02_ · 1 more declaration under this itemhex_ h2_ d4_ d4 Exercise 2.5.1
Lean statement
theorem hdp_02_hex_h2_d5_d1 (p : ℝ) (hp : 1 ≤ p) : (eLpNorm' (fun x : ℝ => x) p (gaussianReal 0 1)).toReal = (2 ^ (p / 2) * Real.Gamma ((1 + p) / 2) / Real.Gamma (1 / 2)) ^ (1 / p)Exercise 2.5.5a
Lean statement
theorem hdp_02_hex_h2_d5_d5a (lam : ℝ) : (|lam| < (Real.sqrt 2)⁻¹ → Integrable (fun x : ℝ => Real.exp (lam ^ 2 * x ^ 2)) (gaussianReal 0 1) ∧ (∫ x : ℝ, Real.exp (lam ^ 2 * x ^ 2) ∂(gaussianReal 0 1)) = (Real.sqrt (1 - 2 * lam ^ 2))⁻¹) ∧ ((Real.sqrt 2)⁻¹ ≤ |lam| → ¬ Integrable (fun x : ℝ => Real.exp (lam ^ 2 * x ^ 2)) (gaussianReal 0 1))Exercise 2.5.5b
Lean statement
theorem squareMGFGlobalTailZero {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {X : Ω → ℝ} {K : ℝ} (hX : Measurable X) (hK : 0 ≤ K) (hMGF : ∀ lam : ℝ, Integrable (fun ω => Real.exp (lam ^ 2 * X ω ^ 2)) μ ∧ (∫ ω, Real.exp (lam ^ 2 * X ω ^ 2) ∂μ) ≤ Real.exp (K * lam ^ 2)) {t : ℝ} (ht : 0 ≤ t) (hthreshold : K < t ^ 2) : μ.real {ω | |X ω| ≥ t} = 0Exercise 2.6.4
Exercise 2.6.4 in the literal no-prefactor form of Theorem 2.2.6. The separate
BoundedHoeffdingFromSubGaussianmodule records the immediate two-sided deduction from Theorem 2.6.3; it necessarily retains a leading2, so this checked source wrapper reuses the already established theorem.Lean statement
theorem hdp_02_hex_h2_d6_d4 : hdp_02_hex_h2_d6_d4__contract_typehdp_
02_ · 2 more declarations under this itemhex_ h2_ d6_ d4 Exercise 2.7.2
The tail, moment, local absolute-MGF, and one-point absolute-MGF conditions are quantitatively equivalent with an absolute factor.
Lean statement
theorem hdp_02_hex_h2_d7_d2_exact : ∃ C : Real, 1 <= C ∧ ∀ {Omega : Type*} [MeasurableSpace Omega] {mu : Measure Omega} [IsProbabilityMeasure mu] {X : Omega -> Real}, ∀ i j : SubExponentialPropertyKind, ∀ {Ki : Real}, 0 < Ki -> SubExponentialProperty mu X i Ki -> ∃ Kj : Real, 0 < Kj ∧ Kj <= C * Ki ∧ SubExponentialProperty mu X j Kjhdp_
02_ · 1 more declaration under this itemhex_ h2_ d7_ d2_ exact Exercise 2.7.3
For every positive power
alpha, applying the four sub-exponential characterizations to|X|^alphagives a quantitative characterization of tails on the scaleexp (-c t^alpha).Lean statement
theorem hdp_02_hex_h2_d7_d3_exact : ∃ C : Real, 1 <= C ∧ ∀ {Omega : Type*} [MeasurableSpace Omega] {mu : Measure Omega} [IsProbabilityMeasure mu] {X : Omega -> Real} {alpha : Real}, 0 < alpha -> ∀ i j : SubWeibullPropertyKind, ∀ {Ki : Real}, 0 < Ki -> SubWeibullProperty mu X alpha i Ki -> ∃ Kj : Real, 0 < Kj ∧ Kj <= C * Ki ∧ SubWeibullProperty mu X alpha j Kjhdp_
02_ · 1 more declaration under this itemhex_ h2_ d7_ d3_ exact Exercise 2.7.4
The property-(c) bound cannot be extended from
0 <= lambdato every|lambda| <= K3⁻¹. The constant-zero random variable already violates the proposed bound atK3 = 1andlambda = -1.Lean statement
theorem hdp_02_hex_h2_d7_d4_exact : let mu : Measure Real := Measure.dirac 0 let X : Real -> Real := fun _ => 0 let K3 : Real := 1 IsProbabilityMeasure mu ∧ Measurable X ∧ 0 < K3 ∧ (∀ lam : Real, 0 <= lam -> lam <= K3⁻¹ -> (∫ x, Real.exp (lam * |X x|) ∂mu) <= Real.exp (K3 * lam)) ∧ ∃ lam : Real, lam < 0 ∧ |lam| <= K3⁻¹ ∧ ¬ (∫ x, Real.exp (lam * |X x|) ∂mu) <= Real.exp (K3 * lam)hdp_
02_ · 1 more declaration under this itemhex_ h2_ d7_ d4_ exact Exercise 2.7.11
Lean statement
theorem hdp_02_hex_h2_d7_d11_exact : hdp_02_hex_h2_d7_d11__contract_typehdp_
02_ · 1 more declaration under this itemhex_ h2_ d7_ d11_ exact Exercise 2.8.5
Exercise 2.8.5 (printed page 38): the MGF bound for a centered bounded variable, with the printed
g (λ) = (λ²/2) / (1 - |λ| K / 3).Lean statement
theorem hdp_02_hex_h2_d8_d5 {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {X : Ω → ℝ} {K : ℝ} (hK : 0 < K) (hX : Measurable X) (hCenter : Integrable X μ ∧ (∫ ω, X ω ∂μ) = 0) (hBound : ∀ᵐ ω ∂μ, |X ω| ≤ K) {lam : ℝ} (hlam : |lam| * K < 3) : Integrable (fun ω => Real.exp (lam * X ω)) μ ∧ (∫ ω, Real.exp (lam * X ω) ∂μ) ≤ Real.exp (((lam ^ 2 / 2) / (1 - |lam| * K / 3)) * (∫ ω, X ω ^ 2 ∂μ))hdp_
02_ · 3 more declarations under this itemhex_ h2_ d8_ d5 Exercise 2.8.6
Effective-domain deduction requested by Exercise 2.8.6.
Lean statement
theorem hdp_02_hex_h2_d8_d6_effectiveDomain : hdp_02_hex_h2_d8_d6_effectiveDomain__contract_typehdp_
02_ · 2 more declarations under this itemhex_ h2_ d8_ d6_ effective Domain
Chapter 4 · Random matrices all chapters
Definitions, theorems and lemmas
Algorithm 4.5
Vershynin's graph spectral-clustering algorithm: construct the adjacency matrix, select the second vector in a complete decreasing eigenbasis, and put strictly positive coordinates in the first community and all others in the second. Symmetry and looplessness express the input graph domain; every
SimpleGraphsupplies these fields, and conversely they construct one. No eigengap or nonempty-community hypothesis is imposed.Lean statement
theorem hdp_04_algorithm_4_5_spectral_clustering {n : ℕ} (adj : Fin n → Fin n → Prop) [DecidableRel adj] (hsym : ∀ i j, adj i j → adj j i) (hloop : ∀ i, ¬adj i i) (hn : 1 < n) : let A : Matrix (Fin n) (Fin n) ℝ := fun i j ↦ if adj i j then 1 else 0 ∃ (eigenvalue : Fin n → ℝ) (b : Fin n → Fin n → ℝ) (first second : Set (Fin n)), (∀ i j, i.val ≤ j.val → eigenvalue j ≤ eigenvalue i) ∧ (∀ i j, (∑ k, b i k * b j k) = if i = j then 1 else 0) ∧ (∀ x : Fin n → ℝ, ∀ j, (∑ i, (∑ k, b i k * x k) * b i j) = x j) ∧ (∀ i j, (∑ k, A j k * b i k) = eigenvalue i * b i j) ∧ (∀ j, j ∈ first ↔ 0 < b ⟨1, hn⟩ j) ∧ (∀ j, j ∈ second ↔ b ⟨1, hn⟩ j ≤ 0)Algorithm 4.7
Vershynin, Section 4.7.1: form the uncentered empirical second moment, choose a unit leading eigenvector, and split the sample by projection sign. Unit normalization is a compatible algorithm choice. The case
m=0is a nonvacuous totalization beyond the printed averaging domain.Lean statement
theorem hdp_04_algorithm_4_7_spectral_clustering {m n : ℕ} (hn : 0 < n) (X : Fin m → Fin n → ℝ) : let M : Matrix (Fin n) (Fin n) ℝ := fun a b ↦ (m : ℝ)⁻¹ * ∑ i, X i a * X i b let v := NumStability.HDP.Vector.EuclideanSpectralClustering.leadingEigenvector hn X (∑ j, v j ^ 2) = 1 ∧ (∃ eigenvalue : ℝ, (∀ a, (∑ b, M a b * v b) = eigenvalue * v a) ∧ (∀ w : Fin n → ℝ, (∑ j, w j ^ 2) = 1 → (∑ a, w a * ∑ b, M a b * w b) ≤ eigenvalue)) ∧ (∃ first second : Set (Fin m), (∀ i, i ∈ first ↔ 0 < ∑ j, v j * X i j) ∧ (∀ i, i ∈ second ↔ (∑ j, v j * X i j) ≤ 0))hdp_
04_ · 1 more declaration under this itemalgorithm_ 4_ 7_ spectral_ clustering Corollary 4.2.13
For every positive radius, the internal covering number of the Euclidean unit ball lies between
(1 / ε)ⁿand(2 / ε + 1)ⁿ; the same upper bound holds for the Euclidean unit sphere. Mathlib's covering number isℕ∞; compactness makes it finite here, so the displayed source bounds are stated on its exact natural value.Lean statement
theorem hdp_04_corollary_4_2_13 (n : ℕ) {ε : ℝ≥0} (hε : 0 < ε) : (1 / (ε : ℝ)) ^ n ≤ ((_root_.Metric.coveringNumber ε (closedBall (0 : EuclideanSpace ℝ (Fin n)) 1)).toNat : ℝ) ∧ ((_root_.Metric.coveringNumber ε (closedBall (0 : EuclideanSpace ℝ (Fin n)) 1)).toNat : ℝ) ≤ (2 / (ε : ℝ) + 1) ^ n ∧ ((_root_.Metric.coveringNumber ε (sphere (0 : EuclideanSpace ℝ (Fin n)) 1)).toNat : ℝ) ≤ (2 / (ε : ℝ) + 1) ^ nDefinition 4.2.1
An epsilon-net lies in the covered set, covers every point within epsilon, and equivalently covers the set by closed epsilon-balls centered in the net. The source assumes a positive radius; this characterization also holds at radius zero.
Lean statement
theorem hdp_04_hdef_h4_d2_d1 {T : Type*} [MetricSpace T] {K N : Set T} {ε : ℝ≥0} : (N ⊆ K ∧ ∀ x ∈ K, ∃ x₀ ∈ N, dist x x₀ ≤ ε) ↔ (N ⊆ K ∧ K ⊆ ⋃ y ∈ N, Metric.closedBall y ε)Definition 4.2.2
The covering number is the least cardinality of an internal epsilon-net, equivalently the least cardinality of a family of closed epsilon-balls centered in the set and covering it. The source uses positive radii; the same exact-cardinal definition and characterization also apply at radius zero.
Lean statement
theorem hdp_04_hdef_h4_d2_d2 {T : Type*} [MetricSpace T] {K : Set T} {ε : ℝ≥0} : (NumStability.HDP.Metric.internalCoveringCardinal ε K = sInf {c : Cardinal | ∃ N : Set T, N ⊆ K ∧ (∀ x ∈ K, ∃ x₀ ∈ N, dist x x₀ ≤ (ε : ℝ)) ∧ c = Cardinal.mk N}) ∧ (NumStability.HDP.Metric.internalCoveringCardinal ε K = sInf {c : Cardinal | ∃ N : Set T, N ⊆ K ∧ K ⊆ ⋃ y ∈ N, Metric.closedBall y (ε : ℝ) ∧ c = Cardinal.mk N})Definition 4.2.4
Lean statement
theorem definition424OwnerQualifiedPositiveTarget_proved : definition424OwnerQualifiedPositiveTargetdefinition424Owner
Qualified · 1 more declaration under this itemPositive Target_ proved Definition 4.2.11
The Minkowski sum consists exactly of sums of one point from each input set. The additive formulation applies in particular to subsets of
ℝⁿ.Lean statement
theorem hdp_04_hdef_h4_d2_d11 {E : Type*} [Add E] (A B : Set E) : A + B = {x | ∃ a ∈ A, ∃ b ∈ B, a + b = x}Definition 4.2.14
Binary strings of length
nform the Hamming cube, their Hamming distance counts the coordinates where they disagree, and theHammingtype synonym equips this cube with that metric.Lean statement
theorem hdp_04_hdef_h4_d2_d14 (n : ℕ) (x y : Fin n → Fin 2) : Nonempty {m : MetricSpace (Hamming (fun _ : Fin n => Fin 2)) // m.toDist = Hamming.instDist} ∧ hammingDist x y = #{i | x i ≠ y i} ∧ dist (Hamming.toHamming x) (Hamming.toHamming y) = (hammingDist x y : ℝ)Definition 4.3.3
An arbitrary encoder
Ecan correctrerrors exactly when there is a decoder recovering every message from every word at Hamming distance at mostr. Such an encoder is an error-correcting code; its range is its code/codebook, and the members of that range are its codewords. String lengths are natural numbers, while the integer error threshold remains unrestricted.Lean statement
theorem hdp_04_definition_4_3_3 (k n : ℕ) (r : ℤ) (E : NumStability.HDP.Coding.BinaryWord k → NumStability.HDP.Coding.BinaryWord n) (D : NumStability.HDP.Coding.BinaryWord n → NumStability.HDP.Coding.BinaryWord k) : (NumStability.HDP.Coding.IntegerCorrectsErrors (k := (k : ℤ)) (n := (n : ℤ)) r E D ↔ ∀ (x : NumStability.HDP.Coding.BinaryWord k) (y : NumStability.HDP.Coding.BinaryWord n), (hammingDist y (E x) : ℤ) ≤ r → D y = x) ∧ (NumStability.HDP.Coding.IntegerIsErrorCorrectingCode (k := (k : ℤ)) (n := (n : ℤ)) r E ↔ ∃ D' : NumStability.HDP.Coding.BinaryWord n → NumStability.HDP.Coding.BinaryWord k, ∀ (x : NumStability.HDP.Coding.BinaryWord k) (y : NumStability.HDP.Coding.BinaryWord n), (hammingDist y (E x) : ℤ) ≤ r → D' y = x) ∧ NumStability.HDP.Coding.integerCodebook (k := (k : ℤ)) (n := (n : ℤ)) E = Set.range E ∧ (∀ w : NumStability.HDP.Coding.BinaryWord n, NumStability.HDP.Coding.IntegerIsCodeword (k := (k : ℤ)) (n := (n : ℤ)) E w ↔ w ∈ Set.range E)Definition 4.5.1
Two communities of size
k, independent Bernoulli edge choices with probabilitiespwithin andqacross them, and the equal-parameter Erdős--Rényi specialization. Finite configurations include the empty configuration with probability one, includingk=0. The parameters range over all of[0,1]², with no separation hypothesis.Lean statement
theorem hdp_04_definition_4_5_1 (k : ℕ) (θ : NumStability.HDP.Graph.StochasticBlock.Parameters) : let probability : NumStability.HDP.Graph.StochasticBlock.Edge k → ℝ≥0 := fun e ↦ if e.1.1.1 = e.1.2.1 then θ.p else θ.q let μ := NumStability.HDP.Graph.StochasticBlock.graphMeasure k θ Fintype.card (NumStability.HDP.Graph.StochasticBlock.Vertex k) = 2 * k ∧ μ Set.univ = 1 ∧ (∀ e : NumStability.HDP.Graph.StochasticBlock.Edge k, μ {x | x e = true} = (probability e : ℝ≥0∞)) ∧ (∀ (S : Finset (NumStability.HDP.Graph.StochasticBlock.Edge k)) (v : NumStability.HDP.Graph.StochasticBlock.Edge k → Bool), μ {x | ∀ e ∈ S, x e = v e} = ∏ e ∈ S, if v e then (probability e : ℝ≥0∞) else ((1 - probability e : ℝ≥0) : ℝ≥0∞)) ∧ (θ.p = θ.q → ∀ (S : Finset (NumStability.HDP.Graph.StochasticBlock.Edge k)) (v : NumStability.HDP.Graph.StochasticBlock.Edge k → Bool), μ {x | ∀ e ∈ S, x e = v e} = ∏ e ∈ S, if v e then (θ.p : ℝ≥0∞) else ((1 - θ.p : ℝ≥0) : ℝ≥0∞))Definition 4.7.4
The equal mixture of
N(μ,I)andN(-μ,I)is the law ofθμ+gfor an independent Rademacher sign and standard Gaussian vector; anm-sample has the corresponding product law.Lean statement
theorem hdp_04_definition_4_7_4 (m : ℕ) {n : ℕ} (μ : Fin n → ℝ) : NumStability.HDP.Vector.GaussianMixture.gaussianMixtureMeasure μ = Measure.map (fun z : ℝ × (Fin n → ℝ) ↦ fun i ↦ z.1 * μ i + z.2 i) (rademacherPMF.toMeasure.prod (NumStability.standardGaussianVectorMeasure n)) ∧ NumStability.HDP.Vector.GaussianMixture.gaussianMixtureSampleMeasure m μ = Measure.pi (fun _ : Fin m ↦ NumStability.HDP.Vector.GaussianMixture.gaussianMixtureMeasure μ)Lemma 4.1.5
If the right Gram matrix of a real rectangular matrix is within
max δ δ²of the identity in operator norm, then every vector is distorted by factors between1 - δand1 + δ, and consequently the smallest and largest singular values obey the same bounds.Lean statement
theorem hdp_04_lemma_4_1_5 {m n : ℕ} (A : Matrix (Fin m) (Fin (n + 1)) ℝ) {δ : ℝ} (hδ : 0 < δ) (hGram : NumStability.realMatrixOperatorNorm (A.transpose * A - 1) ≤ max δ (δ ^ 2)) : NumStability.ApproximateIsometryBounds A δ ∧ NumStability.ExtremeSingularValueBounds A δLemma 4.2.6
Positive-radius source correspondence for Lemma 4.2.6, with maximality expressed by the source's adjoining-point criterion and the net conclusion expressed using the original real metric. The broader characterization remains available as
hdp_04_hlemma_h4_d2_d6.Lean statement
theorem hdp_04_maximal_separated_positive_is_net {T : Type*} [MetricSpace T] {K N : Set T} {ε : ℝ≥0} (hε : 0 < ε) (hNK : N ⊆ K) (hsep : N.Pairwise fun x y => (ε : ℝ) < dist x y) (hmax : ∀ x ∈ K, x ∉ N → ¬ (insert x N).Pairwise (fun a b => (ε : ℝ) < dist a b)) : ∀ ⦃x⦄, x ∈ K → ∃ y ∈ N, dist x y ≤ (ε : ℝ)hdp_
04_ · 3 more declarations under this itemmaximal_ separated_ positive_ is_ net Lemma 4.2.8
Lean statement
theorem hdp_04_lemma_4_2_8_owner_qualified_numerical_proved : hdp_04_lemma_4_2_8_owner_qualified_numerical.{u}hdp_
04_ · 2 more declarations under this itemlemma_ 4_ 2_ 8_ owner_ qualified_ numerical_ proved Lemma 4.3.4
If the base-two logarithm of the packing number of the binary Hamming cube at separation
2ris at leastk, then there is ann-bit encoding ofk-bit strings which correctsrerrors. The source uses positive integer parameters; natural lengths and error counts also allow the valid zero boundary cases.Lean statement
theorem hdp_04_lemma_4_3_4 (k n r : ℕ) (hlog : (k : ℝ) ≤ Real.logb 2 (NumStability.HDP.Coding.binaryHammingPackingNumber n r).toNat) : Nonempty (NumStability.HDP.Coding.ErrorCorrectingCode k n r)Lemma 4.4.1
The supremum of a matrix's action on any set-valued
ε-net of the Euclidean unit sphere approximates its operator norm within the factor(1 - ε)⁻¹.Lean statement
theorem hdp_04_lemma_4_4_1 {m n : ℕ} (hn : 0 < n) (A : Matrix (Fin m) (Fin n) ℝ) (ε : ℝ) (N : Set (EuclideanSpace ℝ (Fin n))) (hε0 : 0 ≤ ε) (hε1 : ε < 1) (hN : NumStability.HDP.Metric.IsUnitSphereNet ε N) : sSup {a : ℝ | ∃ y ∈ N, a = ‖Matrix.toEuclideanLin A y‖} ≤ ‖NumStability.realMatrixContinuousLinearMap A‖ ∧ ‖NumStability.realMatrixContinuousLinearMap A‖ ≤ (1 - ε)⁻¹ * sSup {a : ℝ | ∃ y ∈ N, a = ‖Matrix.toEuclideanLin A y‖}Proposition 4.2.12
The covering number is bounded below by the volume comparison with radius-
εballs, bounded above by the packing number, and the packing number is bounded above by the volume comparison with the Minkowski enlargement by a radius-ε / 2ball. The two volume-ratio inequalities are written in cross-multiplied form inENNReal. Positive finite-dimensional balls have nonzero finite volume, so this retains the source ratios while also covering infinite covering or packing numbers without an extra boundedness assumption onK.Lean statement
theorem hdp_04_proposition_4_2_12 (n : ℕ) (K : Set (EuclideanSpace ℝ (Fin n))) {ε : ℝ≥0} (hε : 0 < ε) : NumStability.HDP.Metric.borelAddHaarVolume K ≤ (_root_.Metric.coveringNumber ε K : ℝ≥0∞) * NumStability.HDP.Metric.borelAddHaarVolume (closedBall (0 : EuclideanSpace ℝ (Fin n)) (ε : ℝ)) ∧ (_root_.Metric.coveringNumber ε K : ℝ≥0∞) ≤ (_root_.Metric.packingNumber ε K : ℝ≥0∞) ∧ (_root_.Metric.packingNumber ε K : ℝ≥0∞) * NumStability.HDP.Metric.borelAddHaarVolume (ball (0 : EuclideanSpace ℝ (Fin n)) ((ε : ℝ) / 2)) ≤ NumStability.HDP.Metric.borelAddHaarVolume (K + closedBall (0 : EuclideanSpace ℝ (Fin n)) ((ε : ℝ) / 2))hdp_
04_ · 1 more declaration under this itemproposition_ 4_ 2_ 12 Proposition 4.3.1
In its exact integer-threshold form. An
N-bit code at accuracyεforces theε-covering number to be at most2^N. Conversely, anε/2-cover with at most2^Ncenters produces anN-bit code at accuracyε. Taking the least admissibleNgives the source's floor/ceiling metric-entropy inequalities without hiding the zero/infinite boundary cases in logarithm conventions.Lean statement
theorem hdp_04_proposition_4_3_1 {T : Type*} [PseudoEMetricSpace T] (K : Set T) (ε : ℝ≥0) (N : ℕ) : (NumStability.HDP.Metric.IsMetricCode K ε N → Metric.coveringNumber ε K ≤ (2 ^ N : ℕ)) ∧ (Metric.coveringNumber (ε / 2) K ≤ (2 ^ N : ℕ) → NumStability.HDP.Metric.IsMetricCode K ε N)Theorem 4.5.3
Theorem 4.5.3 (Weyl's inequality): corresponding ordered eigenvalues of real symmetric matrices differ by at most the operator norm of the matrix perturbation.
Lean statement
theorem hdp_04_theorem_4_5_3 {n : ℕ} (S T : Matrix (Fin n) (Fin n) ℝ) (hS : S.IsHermitian) (hT : T.IsHermitian) (i : Fin n) : (∀ j k : Fin n, j ≤ k → NumStability.hermitianOrderedEigenvalue hS k ≤ NumStability.hermitianOrderedEigenvalue hS j) ∧ (∀ j k : Fin n, j ≤ k → NumStability.hermitianOrderedEigenvalue hT k ≤ NumStability.hermitianOrderedEigenvalue hT j) ∧ spectrum ℝ S.toEuclideanLin = Set.range (NumStability.hermitianOrderedEigenvalue hS) ∧ (∀ μ : ℝ, Module.End.HasEigenvalue S.toEuclideanLin μ → Finset.card {j | NumStability.hermitianOrderedEigenvalue hS j = μ} = Module.finrank ℝ (Module.End.eigenspace S.toEuclideanLin μ)) ∧ spectrum ℝ T.toEuclideanLin = Set.range (NumStability.hermitianOrderedEigenvalue hT) ∧ (∀ μ : ℝ, Module.End.HasEigenvalue T.toEuclideanLin μ → Finset.card {j | NumStability.hermitianOrderedEigenvalue hT j = μ} = Module.finrank ℝ (Module.End.eigenspace T.toEuclideanLin μ)) ∧ |NumStability.hermitianOrderedEigenvalue hS i - NumStability.hermitianOrderedEigenvalue hT i| ≤ NumStability.realMatrixOperatorNorm (S - T)Theorem 4.5.5
Theorem 4.5.5 (Davis--Kahan): if the
i-th ordered eigenvalue of a real symmetric matrix is separated from every other eigenvalue by the positive gapδ, then the sine of the angle between the corresponding ordered unit eigenvectors before and after perturbation is at most2 ‖S - T‖ / δ. The second conjunct inhgaprecords thatδis the attained minimum gap, not merely a lower bound.Lean statement
theorem hdp_04_theorem_4_5_5 {n : ℕ} (S T : Matrix (Fin n) (Fin n) ℝ) (hS : S.IsHermitian) (hT : T.IsHermitian) (i : Fin n) (δ : ℝ) (hδ : 0 < δ) (hgap : (∀ j : Fin n, j ≠ i → δ ≤ |NumStability.hermitianOrderedEigenvalue hS i - NumStability.hermitianOrderedEigenvalue hS j|) ∧ ∃ j : Fin n, j ≠ i ∧ |NumStability.hermitianOrderedEigenvalue hS i - NumStability.hermitianOrderedEigenvalue hS j| = δ) : (∀ j k : Fin n, j ≤ k → NumStability.hermitianOrderedEigenvalue hS k ≤ NumStability.hermitianOrderedEigenvalue hS j) ∧ (∀ j k : Fin n, j ≤ k → NumStability.hermitianOrderedEigenvalue hT k ≤ NumStability.hermitianOrderedEigenvalue hT j) ∧ (∀ j : Fin n, S.toEuclideanLin (NumStability.hermitianOrderedEigenbasis hS j) = NumStability.hermitianOrderedEigenvalue hS j • NumStability.hermitianOrderedEigenbasis hS j ∧ T.toEuclideanLin (NumStability.hermitianOrderedEigenbasis hT j) = NumStability.hermitianOrderedEigenvalue hT j • NumStability.hermitianOrderedEigenbasis hT j ∧ ‖NumStability.hermitianOrderedEigenbasis hS j‖ = 1 ∧ ‖NumStability.hermitianOrderedEigenbasis hT j‖ = 1) ∧ Real.sin (InnerProductGeometry.angle (NumStability.hermitianOrderedEigenbasis hS i) (NumStability.hermitianOrderedEigenbasis hT i)) ≤ 2 * NumStability.realMatrixOperatorNorm (S - T) / δTheorem 4.5.6
The owner-qualified complete Theorem 4.5.6 for the actual loopless balanced stochastic block model.
kranges over positive half-sizes throughhn, son = 2*k ≥ 2;communityranges over every balanced labeling of the vertices. The bound holds on one event for every unit vector in the algebraically ordered second eigenspace, including multiplicities. The Boolean choice swaps the two output labels while leaving the strict-positive/otherwise threshold unchanged.Lean statement
theorem theorem456_owner_qualified_all_unit_proved : hdp_04_theorem_4_5_6_owner_qualified_all_unittheorem456_
owner_ · 3 more declarations under this itemqualified_ all_ unit_ proved Theorem 4.6.1
Theorem 4.6.1 with exhaustive coordinate SVD data and a scalar gauge bound along every unit direction. These premises are equivalent to the existing decomposition and vector-gauge premises, pointwise in the sample.
Lean statement
theorem hdp_04_theorem_4_6_1_explicit_svd : ∃ C : ℝ, 0 < C ∧ ∀ {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {m n : ℕ} (_hm : 0 < m) (A : Ω → Matrix (Fin m) (Fin (n + 1)) ℝ) {K : ℝ}, 1 ≤ K → (∀ i j, Measurable (fun ω => A ω i j)) → (∀ i j, MemLp (fun ω => A ω i j) 2 μ) → (∀ i j, ∫ ω, A ω i j ∂μ = 0) → (∀ i, NumStability.HDP.Vector.Isotropy.IsIsotropic μ (fun j ω => A ω i j)) → (∀ i (z : Fin (n + 1) → ℝ), (∑ j, z j ^ 2) = 1 → NumStability.HDP.Scalar.SubGaussian.PsiTwoNorm μ (fun ω ↦ ∑ j, A ω i j * z j) ≤ ENNReal.ofReal K) → iIndepFun (fun i ω => fun j => A ω i j) μ → ∀ {t : ℝ}, 0 ≤ t → ∀ (r : Ω → ℕ) (s : Ω → Fin (n + 1) → ℝ) (u : ∀ ω, Fin (r ω) → EuclideanSpace ℝ (Fin m)) (v : ∀ ω, Fin (r ω) → EuclideanSpace ℝ (Fin (n + 1))), (∀ ω, NumStability.RealMatrixSVDExplicitFields (A ω) (r ω) (s ω) (u ω) (v ω)) → μ.real {ω | Real.sqrt (m : ℝ) - C * K ^ 2 * (Real.sqrt (n + 1 : ℝ) + t) > s ω (Fin.last n) ∨ s ω ⟨0, Nat.succ_pos n⟩ > Real.sqrt (m : ℝ) + C * K ^ 2 * (Real.sqrt (n + 1 : ℝ) + t)} ≤ 2 * Real.exp (-(t ^ 2))hdp_
04_ · 2 more declarations under this itemtheorem_ 4_ 6_ 1_ explicit_ svd Theorem 4.7.1
The covariance estimate with explicit probability normalization, full vector laws and joint row-event independence, finite ordinary second moments, and literal coordinate operator norms. The ambient dimension may be zero.
Lean statement
theorem hdp_04_theorem_4_7_1_explicit_probability : ∃ C : ℝ, 0 < C ∧ ∀ {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} {m n : ℕ}, μ Set.univ = 1 → 0 < m → ∀ (Z : Ω → Fin n → ℝ) (X : Fin m → Ω → Fin n → ℝ) (K : ℝ≥0), 1 ≤ K → (∀ j, Measurable (fun ω ↦ Z ω j)) → (∀ j, Integrable (fun ω ↦ Z ω j ^ 2) μ) → (∀ i j, Measurable (fun ω ↦ X i ω j)) → (∀ i, AEMeasurable (X i) μ ∧ AEMeasurable Z μ ∧ Measure.map (X i) μ = Measure.map Z μ) → (∀ (S : Finset (Fin m)) (B : Fin m → Set (Fin n → ℝ)), (∀ i, i ∈ S → MeasurableSet (B i)) → μ (⋂ i ∈ S, (X i) ⁻¹' B i) = ∏ i ∈ S, μ ((X i) ⁻¹' B i)) → (∀ x : Fin n → ℝ, NumStability.HDP.Scalar.SubGaussian.PsiTwoNorm μ (fun ω ↦ ∑ j, Z ω j * x j) ≤ (K : ℝ≥0∞) * ENNReal.ofReal (Real.sqrt (∫ ω, (∑ j, Z ω j * x j) ^ 2 ∂μ))) → (∫ ω, sSup {q : ℝ | ∃ x : Fin n → ℝ, (∑ j, x j ^ 2) = 1 ∧ q = Real.sqrt (∑ a, (∑ b, ((m : ℝ)⁻¹ * ∑ i, X i ω a * X i ω b - ∫ η, Z η a * Z η b ∂μ) * x b) ^ 2)} ∂μ) ≤ C * (K : ℝ) ^ 2 * (Real.sqrt ((n : ℝ) / (m : ℝ)) + (n : ℝ) / (m : ℝ)) * sSup {q : ℝ | ∃ x : Fin n → ℝ, (∑ j, x j ^ 2) = 1 ∧ q = Real.sqrt (∑ a, (∑ b, (∫ ω, Z ω a * Z ω b ∂μ) * x b) ^ 2)}hdp_
04_ · 1 more declaration under this itemtheorem_ 4_ 7_ 1_ explicit_ probability
Equations and other results
Result
Vershynin, Section 4.3.1: coding complexity is the least bit length of an encoding for which points sharing a codeword are within the requested metric accuracy.
Lean statement
theorem hdp_04_coding_complexity_definition {T : Type*} [PseudoEMetricSpace T] (K : Set T) (ε : ℝ≥0) : NumStability.HDP.Metric.codingComplexity K ε = ⨅ (N : ℕ) (_ : ∃ encode : K → Fin (2 ^ N), ∀ x y : K, encode x = encode y → edist (x : T) y ≤ ε), (N : ℕ∞)Result
Vershynin, Section 4.7: for a centered vector the covariance is its second-moment matrix; without centering it is the expected centered outer product.
Lean statement
theorem hdp_04_covariance_matrix_definition {n : ℕ} {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] (X : Fin n → Ω → ℝ) (hX : ∀ i, MemLp (X i) 2 μ) : NumStability.HDP.Vector.Covariance.covarianceMatrix μ X = (fun i j => ∫ ω, (X i ω - ∫ ω, X i ω ∂μ) * (X j ω - ∫ ω, X j ω ∂μ) ∂μ) ∧ (NumStability.HDP.Vector.Covariance.meanVector μ X = 0 → NumStability.HDP.Vector.Covariance.covarianceMatrix μ X = NumStability.HDP.Vector.Covariance.secondMomentMatrix μ X)Result
Vershynin, High-Dimensional Probability, Chapter 4 footnote:
diam(K) = sup {d(x,y) : x,y ∈ K}. The extended codomain represents the formula for every set; the additional conjuncts make the empty and unbounded semantics explicit.Lean statement
theorem hdp_04_diameter_definition {T : Type*} [MetricSpace T] (K : Set T) : chapterFourDiameter K = Metric.ediam K ∧ chapterFourDiameter (∅ : Set T) = 0 ∧ (¬Bornology.IsBounded K → chapterFourDiameter K = ⊤)Result
The distance-distortion check for the same exhaustive coordinate SVD data, applied to the difference of any two points.
Lean statement
theorem hdp_04_distance_distortion_explicit_svd {m n r : ℕ} (A : Matrix (Fin m) (Fin (n + 1)) ℝ) (s : Fin (n + 1) → ℝ) (u : Fin r → EuclideanSpace ℝ (Fin m)) (v : Fin r → EuclideanSpace ℝ (Fin (n + 1))) (hSVD : NumStability.RealMatrixSVDExplicitFields A r s u v) : ∀ x y : Fin (n + 1) → ℝ, s (Fin.last n) * Real.sqrt (∑ j, (x j - y j) ^ 2) ≤ Real.sqrt (∑ i, ((∑ j, A i j * x j) - (∑ j, A i j * y j)) ^ 2) ∧ Real.sqrt (∑ i, ((∑ j, A i j * x j) - (∑ j, A i j * y j)) ^ 2) ≤ s ⟨0, Nat.succ_pos n⟩ * Real.sqrt (∑ j, (x j - y j) ^ 2)Result
Vershynin, Chapter 4, printed page 78, Eckart--Young--Mirsky: if
A = ∑ᵢ sᵢ uᵢvᵢᵀhas rankk+qwithq>0, its firstkSVD terms form a rank-at-most-kapproximation whose operator-norm error is the next singular value. The same truncation is best in Frobenius norm and, simultaneously, in every real unitarily invariant norm.Lean statement
theorem hdp_04_eckart_young_mirsky {m n k q : ℕ} {A : Matrix (Fin m) (Fin n) ℝ} {s : Fin n → ℝ} {u : Fin (k + q) → EuclideanSpace ℝ (Fin m)} {v : Fin (k + q) → EuclideanSpace ℝ (Fin n)} (h : NumStability.IsRealMatrixSVD A (k + q) s u v) (hq : 0 < q) : let Ak := NumStability.realSVDHead s u v h.rank_le_width NumStability.lowRankResidualOperator A Ak = s (Fin.castLE h.rank_le_width (Fin.natAdd k (⟨0, hq⟩ : Fin q))) ∧ NumStability.IsBestRankApproxOperator m n k A Ak ∧ NumStability.IsBestRankApproxFrob m n k A Ak ∧ NumStability.IsBestRankApproxUnitaryInvariant m n k A AkResult
The displayed Chapter 4 corruption example under both retained space conventions.
Lean statement
theorem errorCorruptionStringAtMostTwoExample : rawSent.length = rawReceived.length ∧ hammingDist (fun i : Fin rawSent.length => rawSent.get i) (fun i : Fin rawSent.length => rawReceived.get i) ≤ 2 ∧ lettersSent.length = lettersReceived.length ∧ hammingDist (fun i : Fin lettersSent.length => lettersSent.get i) (fun i : Fin lettersSent.length => lettersReceived.get i) ≤ 2Result
Reuse the existing positive-radius countable-domain inverse and the norm-distance identity; there is no new minimum or net construction.
Lean statement
theorem hdp_04_euclidean_positive_covering_value : HDP04EuclideanPositiveCoveringValueResult
Vershynin, Chapter 4, p. 77: the canonical matrix inner product generates the Frobenius norm.
Lean statement
theorem hdp_04_frobenius_norm_sq_eq_inner_self {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) : NumStability.frobNormRect A ^ 2 = NumStability.HDP.Tensor.inner (NumStability.HDP.Tensor.matrixTensor A) (NumStability.HDP.Tensor.matrixTensor A)Result
Vershynin, Chapter 4, p. 77: the Frobenius norm is the square root of the sum of the squares of all matrix entries.
Lean statement
theorem hdp_04_frobenius_norm_definition {m n : ℕ} (A : Fin m → Fin n → ℝ) : NumStability.frobNormRect A = Real.sqrt (∑ i : Fin m, ∑ j : Fin n, A i j ^ 2)Result
Vershynin, Chapter 4, p. 77: the Frobenius norm is the square root of the sum of the squared singular values.
Lean statement
theorem hdp_04_frobenius_norm_eq_sqrt_sum_singular_values_sq {m n : ℕ} (A : Fin m → Fin n → ℝ) : NumStability.frobNormRect A = Real.sqrt (∑ i : Fin n, NumStability.complexMatrixSingularValue (NumStability.realRectToCMatrix A) i ^ 2)Result
Vershynin, Section 4.3.1: the metric entropy is the base-two logarithm of the covering number.
Lean statement
theorem hdp_04_metric_entropy_definition {T : Type*} [PseudoEMetricSpace T] (K : Set T) (ε : ℝ≥0) : NumStability.HDP.Metric.metricEntropy K ε = ENNReal.log (Metric.coveringNumber ε K).toENNReal / ENNReal.log 2Result
The literal printed definition on the complete ordinary real-logarithm domain. The endpoint and exterior extensions are not source conventions.
Lean statement
theorem hdp_04_notes_binary_entropy_ordinary_domain (x : ℝ) (_hx : 0 < x) (_hx1 : x < 1) : NumStability.HDP.Coding.printedBinaryEntropy x = -x * Real.logb 2 x + (1 - x) * Real.logb 2 (1 - x)Result
Printed page 76: for a real
mbynmatrix with nonzero domain and codomain dimensions, the operator norm is the maximum of⟪A x, y⟫_ℝover unit vectorsxandy.Lean statement
theorem hdp_04_operator_norm_bilinear {m n : ℕ} (hm : 0 < m) (hn : 0 < n) (A : Matrix (Fin m) (Fin n) ℝ) : NumStability.IsRealMatrixBilinearOperatorNorm A (NumStability.realMatrixOperatorNorm A)Result
Printed page 76: for a real m by n matrix with nonzero domain dimension, the subordinate Euclidean operator norm is both the maximum nonzero-vector ratio and the maximum image norm on the unit sphere.
Lean statement
theorem hdp_04_operator_norm_definition {m n : ℕ} (hn : 0 < n) (A : Matrix (Fin m) (Fin n) ℝ) : NumStability.IsRealMatrixOperatorNorm A (NumStability.realMatrixOperatorNorm A)Result
Printed pages 76–77: the leading coefficient of the explicit ordered SVD equals the literal Euclidean coordinate supremum and attains that maximum on the unit sphere. The column dimension is nonempty; the row dimension and rank may be zero.
Lean statement
theorem hdp_04_operator_norm_eq_largest_singular_value_coordinate_max {m n : ℕ} (A : Matrix (Fin m) (Fin (n + 1)) ℝ) : ∃ (r : ℕ) (s : Fin (n + 1) → ℝ) (u : Fin r → EuclideanSpace ℝ (Fin m)) (v : Fin r → EuclideanSpace ℝ (Fin (n + 1))), NumStability.RealMatrixSVDExplicitFields A r s u v ∧ (∀ i : Fin (n + 1), s i ≤ s (0 : Fin (n + 1))) ∧ s (0 : Fin (n + 1)) = sSup {q : ℝ | ∃ x : Fin (n + 1) → ℝ, (∑ j, x j ^ 2) = 1 ∧ q = Real.sqrt (∑ a, (∑ b, A a b * x b) ^ 2)} ∧ ∃ x : Fin (n + 1) → ℝ, (∑ j, x j ^ 2) = 1 ∧ Real.sqrt (∑ a, (∑ b, A a b * x b) ^ 2) = s (0 : Fin (n + 1)) ∧ ∀ y : Fin (n + 1) → ℝ, (∑ j, y j ^ 2) = 1 → Real.sqrt (∑ a, (∑ b, A a b * y b) ^ 2) ≤ s (0 : Fin (n + 1))hdp_
04_ operator_ norm_ eq_ largest_ singular_ value_ coordinate_ max Result
Vershynin, High-Dimensional Probability, Chapter 4 footnote: a projection is idempotent, and it is orthogonal when its image and kernel are orthogonal subspaces. The statement uses Mathlib's canonical predicates and exposes their pointwise content. It applies to real inner-product spaces, and therefore includes the finite-dimensional Euclidean matrix setting of the source.
Lean statement
theorem hdp_04_orthogonal_projection_definition {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] (P : Module.End ℝ E) : (IsIdempotentElem P ∧ LinearMap.range P ⟂ LinearMap.ker P) ↔ (P * P = P ∧ ∀ u ∈ LinearMap.range P, ∀ v ∈ LinearMap.ker P, ⟪u, v⟫_ℝ = 0)Result
The entrywise law-of-large-numbers statement in Section 4.7: the sample covariance matrices converge almost surely to the population second-moment matrix. The source uses a probability space. The integrability, independence and identical-distribution hypotheses already suffice for the underlying strong law under an arbitrary measure, so this statement includes that broader measure domain.
Lean statement
theorem hdp_04_sample_covariance_almost_sure {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} {n : ℕ} (X : ℕ → Ω → Fin n → ℝ) (hInt : ∀ a b, Integrable (fun ω ↦ X 0 ω a * X 0 ω b) μ) (hIndep : Pairwise (fun i j ↦ IndepFun (X i) (X j) μ)) (hIdent : ∀ i, IdentDistrib (X i) (X 0) μ μ) : ∀ᵐ ω ∂μ, ∀ a b, Filter.Tendsto (fun m ↦ NumStability.HDP.Vector.Covariance.sequenceSampleCovariance X m ω a b) Filter.atTop (nhds (NumStability.HDP.Vector.Covariance.secondMomentMatrix μ (fun i ω ↦ X 0 ω i) a b))Result
Vershynin, Section 4.7: the sample covariance is the average of the sample outer products.
Lean statement
theorem hdp_04_sample_covariance_definition {m n : ℕ} (X : Fin m → Fin n → ℝ) (a b : Fin n) : NumStability.HDP.Vector.Covariance.sampleCovariance X a b = (m : ℝ)⁻¹ * ∑ i, X i a * X i bResult
Vershynin, Section 4.7: the empirical second-moment matrix of identically distributed samples is an unbiased estimator of the population second-moment matrix. Integrability states the finite-expectation convention explicitly.
Lean statement
theorem hdp_04_sample_covariance_unbiased {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} {m n : ℕ} (hm : 0 < m) (X : Fin m → Ω → Fin n → ℝ) (Z : Ω → Fin n → ℝ) (hident : ∀ i, IdentDistrib (X i) Z μ μ) (hint : ∀ i a b, Integrable (fun ω ↦ X i ω a * X i ω b) μ) (a b : Fin n) : (∫ ω, NumStability.HDP.Vector.Covariance.randomSampleCovariance X ω a b ∂μ) = NumStability.HDP.Vector.Covariance.secondMomentMatrix μ (fun i ω ↦ Z ω i) a bResult
The dense-regime bound together with the exact probability law and a complete ordered coordinate eigendecomposition of every sampled adjacency matrix. The constant is uniform in the size, probabilities and positive lower bound
c₀; the probability and spectral identities are conclusions.Lean statement
theorem hdp_04_sbm_dense_regime_constant_error_explicit : ∃ C : ℝ, 0 < C ∧ ∀ {k : ℕ} (hk : 0 < k) (θ : NumStability.HDP.Graph.StochasticBlock.Parameters) (c₀ : ℝ), 0 < c₀ → c₀ ≤ (θ.q : ℝ) → c₀ ≤ (θ.p : ℝ) - θ.q → let n := 2 * k let community := BalancedFinSBM.community k let P := NumStability.HDP.Graph.FinStochasticBlock.measure community θ let A : (NumStability.HDP.Graph.FinStochasticBlock.UpperPair n → Bool) → Matrix (Fin n) (Fin n) ℝ := NumStability.HDP.Graph.FinStochasticBlock.adjacency let hA : ∀ ω, (A ω).IsHermitian := NumStability.HDP.Graph.FinStochasticBlock.adjacency_hermitian let hn : 1 < n := by omega P Set.univ = 1 ∧ (∀ (S : Finset (NumStability.HDP.Graph.FinStochasticBlock.UpperPair n)) (v : NumStability.HDP.Graph.FinStochasticBlock.UpperPair n → Bool), P {x | ∀ e ∈ S, x e = v e} = ∏ e ∈ S, if v e then (NumStability.HDP.Graph.FinStochasticBlock.upperProbability community θ e : ℝ≥0∞) else ((1 - NumStability.HDP.Graph.FinStochasticBlock.upperProbability community θ e : ℝ≥0) : ℝ≥0∞)) ∧ (∀ i : Fin n, P {x | x ⟨(i, i), le_rfl⟩ = true} = 0) ∧ (∀ ω, ∃ (eigenvalue : Fin n → ℝ) (b : Fin n → Fin n → ℝ), (∀ i j, i.val ≤ j.val → eigenvalue j ≤ eigenvalue i) ∧ (∀ i j, (∑ l, b i l * b j l) = if i = j then 1 else 0) ∧ (∀ x : Fin n → ℝ, ∀ j, (∑ i, (∑ l, b i l * x l) * b i j) = x j) ∧ (∀ i j, (∑ l, A ω j l * b i l) = eigenvalue i * b i j) ∧ (∀ j, NumStability.HDP.Graph.SpectralClustering.secondEigenvector (A ω) (hA ω) hn j = b ⟨1, hn⟩ j)) ∧ P.real {ω | ¬ sbmSpectralClusteringSucceeds community (Real.sqrt n • NumStability.HDP.Graph.SpectralClustering.secondEigenvector (A ω) (hA ω) (by omega : 2 ≤ n)) (C / c₀ ^ 2)} ≤ 4 * Real.exp (-(n : ℝ))Result
One event supplies the coupled unit-vector, scaled-error and classifier bounds.
Lean statement
theorem sbm_eigenvector_sign_correction_full_body_proved : HDP04SBMEigenvectorSignCorrectionFullBodyTargetResult
The common-event sign-disagreement bound, with global label matching.
Lean statement
theorem sbm_sign_disagreement_full_body_proved : HDP04SBMSignDisagreementFullBodyTargetResult
Printed pages 75–76: the left and right singular-vector families are orthonormal eigenvectors of
A AᵀandAᵀ A; their Gram eigenvalue is the square of the corresponding nonnegative singular value.Lean statement
theorem hdp_04_singular_eigenvalue_relations {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) : ∃ (r : ℕ) (s : Fin n → ℝ) (u : Fin r → EuclideanSpace ℝ (Fin m)) (v : Fin r → EuclideanSpace ℝ (Fin n)), NumStability.IsRealMatrixSVDWithGramEigenrelations A r s u vResult
Printed page 76: the decreasingly ordered singular values of a real rectangular matrix have the Courant--Fischer max--min characterization. The sequence is the repository's explicit canonical right-Gram singular-value sequence, rather than an existentially chosen sequence unrelated to the SVD. The reusable predicate states the maximum and minimum through their attaining and universal witness properties.
Lean statement
theorem hdp_04_singular_value_minmax {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) : Antitone (NumStability.rectCourantFischerSingularValue A) ∧ ∀ i : Fin n, NumStability.IsSingularValueMaxMin A (NumStability.rectCourantFischerSingularValue A) iResult
Vershynin, Chapter 4, p. 77, inline check: for the
r-component singular-value vector, its infinity and Euclidean norms satisfy‖s‖∞ ≤ ‖s‖₂ ≤ sqrt r * ‖s‖∞.Lean statement
theorem hdp_04_singular_vector_norm_comparison_check {r : ℕ} (s : Fin r → ℝ) : NumStability.infNormVec s ≤ NumStability.vecNorm2 s ∧ NumStability.vecNorm2 s ≤ Real.sqrt (r : ℝ) * NumStability.infNormVec sResult
Printed page 76: for a real symmetric matrix, the singular values are the absolute values of its eigenvalues, and both left and right singular vectors are eigenvectors of the matrix.
Lean statement
theorem hdp_04_symmetric_singular_values {n : ℕ} (A : Matrix (Fin n) (Fin n) ℝ) (hA : A.IsHermitian) : ∃ (eigenvalue singularValue : Fin n → ℝ) (leftVector rightVector : Fin n → EuclideanSpace ℝ (Fin n)), NumStability.IsSymmetricRealMatrixSVD A eigenvalue singularValue leftVector rightVectorResult
A thirty-letter codeword corrects every corruption of the displayed phrase at Hamming radius two, under the selected 26-letter interpretation.
Lean statement
theorem thirtyLetterQualifiedProof : thirtyLetterQualifiedTargetEquation (4.1)
Printed page 75: every real rectangular matrix is a sum of
rank Asingular-value rank-one termss k • (u k) (v k)ᵀ, stated entrywise. The SVD certificate preserves the immediately defined roles of the coefficients and vector families instead of weakening them to arbitrary rank-factorization data.Lean statement
theorem hdp_04_heq_h4_d1 {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) : ∃ (r : ℕ) (s : Fin n → ℝ) (u : Fin r → EuclideanSpace ℝ (Fin m)) (v : Fin r → EuclideanSpace ℝ (Fin n)) (h : NumStability.IsRealMatrixSVD A r s u v), r = A.rank ∧ ∀ i j, A i j = ∑ k : Fin r, s (Fin.castLE h.rank_le_width k) * u k i * v k jEquation (4.2)
The decreasingly ordered eigenvalues of a real symmetric matrix have the Courant--Fischer max--min characterization. The reusable predicate states the maximum and minimum by their attaining and universal witness properties.
Lean statement
theorem hdp_04_heq_h4_d2 {n : ℕ} (A : Matrix (Fin n) (Fin n) ℝ) (hA : A.IsHermitian) : Antitone (NumStability.hermitianOrderedEigenvalue hA) ∧ ∀ i : Fin n, NumStability.IsCourantFischerMaxMin A (NumStability.hermitianOrderedEigenvalue hA) iEquation (4.3)
The canonical matrix inner product is both the trace of
AᵀBand the sum of the entrywise products. The identity also includes matrices with an empty row or column index set.Lean statement
theorem hdp_04_eq_4_3 {m n : ℕ} (A B : Matrix (Fin m) (Fin n) ℝ) : NumStability.HDP.Tensor.inner (NumStability.HDP.Tensor.matrixTensor A) (NumStability.HDP.Tensor.matrixTensor B) = Matrix.trace (A.transpose * B) ∧ NumStability.HDP.Tensor.inner (NumStability.HDP.Tensor.matrixTensor A) (NumStability.HDP.Tensor.matrixTensor B) = ∑ i, ∑ j, A i j * B i jEquation (4.4)
Full source contract for Vershynin, Chapter 4, Equation (4.4), combining the real-matrix inequalities with the accompanying best-possible assertion.
Lean statement
theorem hdp_04_equation_4_4 {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) : (NumStability.realMatrixOperatorNorm A ≤ NumStability.frobNormRect A ∧ NumStability.frobNormRect A ≤ Real.sqrt (NumStability.realRectMatrixRank A : ℝ) * NumStability.realMatrixOperatorNorm A) ∧ NumStability.RealOperatorFrobeniusRelationIsBestPossiblehdp_
04_ · 2 more declarations under this itemequation_ 4_ 4 Equation (4.5)
The smallest and largest singular values are the largest lower and smallest upper expansion constants. Every matrix admits the SVD certificate used here, and the result holds for every such certificate. The positive column dimension makes both extreme indices meaningful. The zero-row case is a nonvacuous extension of the printed matrix convention.
Lean statement
theorem hdp_04_equation_4_5 {m n r : ℕ} (A : Matrix (Fin m) (Fin (n + 1)) ℝ) (s : Fin (n + 1) → ℝ) (u : Fin r → EuclideanSpace ℝ (Fin m)) (v : Fin r → EuclideanSpace ℝ (Fin (n + 1))) (hSVD : NumStability.IsRealMatrixSVD A r s u v) : (∀ x : Fin (n + 1) → ℝ, s (Fin.last n) * Real.sqrt (∑ j, x j ^ 2) ≤ Real.sqrt (∑ i, (∑ j, A i j * x j) ^ 2) ∧ Real.sqrt (∑ i, (∑ j, A i j * x j) ^ 2) ≤ s ⟨0, Nat.succ_pos n⟩ * Real.sqrt (∑ j, x j ^ 2)) ∧ (∀ upper : ℝ, (∀ x : Fin (n + 1) → ℝ, Real.sqrt (∑ i, (∑ j, A i j * x j) ^ 2) ≤ upper * Real.sqrt (∑ j, x j ^ 2)) → s ⟨0, Nat.succ_pos n⟩ ≤ upper) ∧ (∀ lower : ℝ, (∀ x : Fin (n + 1) → ℝ, lower * Real.sqrt (∑ j, x j ^ 2) ≤ Real.sqrt (∑ i, (∑ j, A i j * x j) ^ 2)) → lower ≤ s (Fin.last n))hdp_
04_ · 2 more declarations under this itemequation_ 4_ 5 Equation (4.6)
Under the approximate-isometry Gram-deviation hypothesis, every vector is distorted by factors between
1 - δand1 + δ.Lean statement
theorem hdp_04_equation_4_6 {m n : ℕ} (A : Matrix (Fin m) (Fin (n + 1)) ℝ) {δ : ℝ} (hδ : 0 < δ) (hGram : NumStability.realMatrixOperatorNorm (A.transpose * A - 1) ≤ max δ (δ ^ 2)) : NumStability.ApproximateIsometryBounds A δEquation (4.7)
Under the approximate-isometry Gram-deviation hypothesis, the smallest and largest singular values lie between
1 - δand1 + δ.Lean statement
theorem hdp_04_equation_4_7 {m n : ℕ} (A : Matrix (Fin m) (Fin (n + 1)) ℝ) {δ : ℝ} (hδ : 0 < δ) (hGram : NumStability.realMatrixOperatorNorm (A.transpose * A - 1) ≤ max δ (δ ^ 2)) : NumStability.ExtremeSingularValueBounds A δEquation (4.8)
Printed page 79: for a nonnegative real
z, the deviation ofz²from one dominates both the linear and squared deviations ofzfrom one.Lean statement
theorem hdp_04_heq_h4_d8 {z : ℝ} (hz : 0 ≤ z) : max |z - 1| (|z - 1| ^ 2) ≤ |z ^ 2 - 1|Equation (4.9)
Euclidean distance on
ℝⁿis the Euclidean norm of the difference.Lean statement
theorem hdp_04_heq_h4_d9 {n : ℕ} (x y : EuclideanSpace ℝ (Fin n)) : dist x y = ‖x - y‖Equation (4.10)
In the nontrivial range
0 < ε ≤ 1, the covering number of the Euclidean unit ball lies between(1 / ε)ⁿand the simplified upper bound(3 / ε)ⁿ.Lean statement
theorem hdp_04_equation_4_10 (n : ℕ) {ε : ℝ≥0} (hε : 0 < ε) (hεone : ε ≤ 1) : (1 / (ε : ℝ)) ^ n ≤ ((_root_.Metric.coveringNumber ε (closedBall (0 : EuclideanSpace ℝ (Fin n)) 1)).toNat : ℝ) ∧ ((_root_.Metric.coveringNumber ε (closedBall (0 : EuclideanSpace ℝ (Fin n)) 1)).toNat : ℝ) ≤ (3 / (ε : ℝ)) ^ nhdp_
04_ · 1 more declaration under this itemequation_ 4_ 10 Equation (4.11)
2r+1copies of ak-letter message use(2r+1)kletters.Lean statement
theorem hdp_04_equation_4_11 (r k : ℕ) : Fintype.card (Fin (2 * r + 1) × Fin k) = (2 * r + 1) * kEquation (4.12)
The two Euclidean unit spheres admit quarter-nets whose cardinalities are bounded by
9^nand9^m, respectively.Lean statement
theorem hdp_04_equation_4_12 {m n : ℕ} (hm : 0 < m) (hn : 0 < n) : ∃ (N : Finset (EuclideanSpace ℝ (Fin n))) (M : Finset (EuclideanSpace ℝ (Fin m))), NumStability.HDP.Metric.IsFiniteUnitSphereNet (1 / 4 : ℝ) N ∧ NumStability.HDP.Metric.IsFiniteUnitSphereNet (1 / 4 : ℝ) M ∧ N.Nonempty ∧ M.Nonempty ∧ N.card ≤ 9 ^ n ∧ M.card ≤ 9 ^ mEquation (4.13)
Quarter-nets of the domain and codomain unit spheres control the matrix operator norm by twice the largest sampled bilinear form.
Lean statement
theorem hdp_04_equation_4_13 {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (N : Finset (EuclideanSpace ℝ (Fin n))) (M : Finset (EuclideanSpace ℝ (Fin m))) (hN : NumStability.HDP.Metric.IsFiniteUnitSphereNet (1 / 4 : ℝ) N) (hM : NumStability.HDP.Metric.IsFiniteUnitSphereNet (1 / 4 : ℝ) M) (hNnonempty : N.Nonempty) (hMnonempty : M.Nonempty) : ∃ x ∈ N, ∃ y ∈ M, (∀ u ∈ N, ∀ v ∈ M, inner ℝ (Matrix.toEuclideanLin A u) v ≤ inner ℝ (Matrix.toEuclideanLin A x) y) ∧ ‖NumStability.realMatrixContinuousLinearMap A‖ ≤ 2 * inner ℝ (Matrix.toEuclideanLin A x) yEquation (4.14)
For fixed unit vectors
xandy, the bilinear form⟪A x, y⟫of a matrix with independent centered sub-Gaussian entries has a Gaussian upper tail at the maximum entrywiseψ₂scale. The positive-scale premise makes explicit the effective domain of the printed quotientu² / K²; the source gives no extended-value convention atK = 0.Lean statement
theorem hdp_04_equation_4_14 : ∃ c : ℝ, 0 < c ∧ ∀ {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {m n : ℕ} [Nonempty (Fin m)] [Nonempty (Fin n)], ∀ (A : Ω → Matrix (Fin m) (Fin n) ℝ), (∀ ij : Fin m × Fin n, NumStability.HDP.Scalar.SubGaussian.IsSubGaussian μ (fun ω ↦ A ω ij.1 ij.2)) → (∀ ij : Fin m × Fin n, Integrable (fun ω ↦ A ω ij.1 ij.2) μ ∧ (∫ ω, A ω ij.1 ij.2 ∂μ) = 0) → iIndepFun (fun ij : Fin m × Fin n ↦ fun ω ↦ A ω ij.1 ij.2) μ → 0 < NumStability.HDP.Scalar.SubGaussian.psiTwoNormMax μ (fun ij : Fin m × Fin n ↦ fun ω ↦ A ω ij.1 ij.2) → ∀ (x : EuclideanSpace ℝ (Fin n)) (y : EuclideanSpace ℝ (Fin m)), ‖x‖ = 1 → ‖y‖ = 1 → ∀ {u : ℝ}, 0 ≤ u → μ.real {ω | inner ℝ (Matrix.toEuclideanLin (A ω) x) y ≥ u} ≤ 2 * Real.exp (-(c * u ^ 2 / (NumStability.HDP.Scalar.SubGaussian.psiTwoNormMax μ (fun ij : Fin m × Fin n ↦ fun ω ↦ A ω ij.1 ij.2)) ^ 2))Equation (4.15)
Lean statement
theorem equation415_owner_qualified_proved : CompleteOwnerQualifiedParent.{u}equation415_
owner_ · 2 more declarations under this itemqualified_ proved Equation (4.16)
The threshold selected after the net union bound is
C K (√n + √m + t).Lean statement
theorem hdp_04_equation_4_16 (C K : ℝ) (n m : ℕ) (t : ℝ) : NumStability.HDP.Matrix.subGaussianNormThreshold C K n m t = C * K * (Real.sqrt n + Real.sqrt m + t)Equation (4.19)
The Davis--Kahan sine bound implies Euclidean closeness of the corresponding unit eigenvectors after choosing one of their two possible signs. The constant
2 * sqrt 2is2^(3/2). The premise is precisely the conclusion of Theorem 4.5.5, withdstanding for‖S - T‖andδfor the spectral separation.Lean statement
theorem hdp_04_equation_4_19 {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] (uS uT : E) (huS : ‖uS‖ = 1) (huT : ‖uT‖ = 1) (d δ : ℝ) (hδ : 0 < δ) (hDavisKahan : Real.sin (InnerProductGeometry.angle uS uT) ≤ 2 * d / δ) : ∃ θ : ℝ, (θ = -1 ∨ θ = 1) ∧ ‖uS - θ • uT‖ ≤ 2 * Real.sqrt 2 * d / δEquation (4.20)
For the exact balanced loopless independent-Bernoulli stochastic-block law. Outside an event of probability at most
4 exp (-n), one global sign makes the squared coefficient error between the rescaled population and empirical second eigenvectors at mostC / μ², whereμ = min(q, p-q).Lean statement
theorem hdp_04_equation_4_20 : ∃ C : ℝ, 0 < C ∧ ∀ {k : ℕ} (hk : 0 < k) (θ : NumStability.HDP.Graph.StochasticBlock.Parameters), 0 < θ.q → θ.q < θ.p → let n := 2 * k let community := BalancedFinSBM.community k let P := NumStability.HDP.Graph.FinStochasticBlock.measure community θ let A : (NumStability.HDP.Graph.FinStochasticBlock.UpperPair n → Bool) → Matrix (Fin n) (Fin n) ℝ := NumStability.HDP.Graph.FinStochasticBlock.adjacency let hA : ∀ ω, (A ω).IsHermitian := NumStability.HDP.Graph.FinStochasticBlock.adjacency_hermitian let hD := BalancedFinSBM.population_hermitian k θ.p θ.q let μ : ℝ := min θ.q (θ.p - θ.q) P.real {ω | ¬ ∃ α : ℝ, (α = -1 ∨ α = 1) ∧ ∑ j, |(Real.sqrt n • NumStability.hermitianOrderedEigenbasis hD ⟨1, by omega⟩) j - (α • (Real.sqrt n • NumStability.hermitianOrderedEigenbasis (hA ω) ⟨1, by omega⟩)) j| ^ 2 ≤ C / μ ^ 2} ≤ 4 * Real.exp (-(n : ℝ))Equation (4.21)
Equation (4.21) for exhaustive coordinate SVD data and all unit scalar marginals, retaining the coefficient ordering and simultaneous tail bound.
Lean statement
theorem hdp_04_equation_4_21_explicit_svd : ∃ C : ℝ, 0 < C ∧ ∀ {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {m n : ℕ} (_hm : 0 < m) (A : Ω → Matrix (Fin m) (Fin (n + 1)) ℝ) {K : ℝ}, 1 ≤ K → (∀ i j, Measurable (fun ω => A ω i j)) → (∀ i j, MemLp (fun ω => A ω i j) 2 μ) → (∀ i j, ∫ ω, A ω i j ∂μ = 0) → (∀ i, NumStability.HDP.Vector.Isotropy.IsIsotropic μ (fun j ω => A ω i j)) → (∀ i (z : Fin (n + 1) → ℝ), (∑ j, z j ^ 2) = 1 → NumStability.HDP.Scalar.SubGaussian.PsiTwoNorm μ (fun ω ↦ ∑ j, A ω i j * z j) ≤ ENNReal.ofReal K) → iIndepFun (fun i ω => fun j => A ω i j) μ → ∀ {t : ℝ}, 0 ≤ t → ∀ (r : Ω → ℕ) (s : Ω → Fin (n + 1) → ℝ) (u : ∀ ω, Fin (r ω) → EuclideanSpace ℝ (Fin m)) (v : ∀ ω, Fin (r ω) → EuclideanSpace ℝ (Fin (n + 1))), (∀ ω, NumStability.RealMatrixSVDExplicitFields (A ω) (r ω) (s ω) (u ω) (v ω)) → (∀ ω i, s ω (Fin.last n) ≤ s ω i ∧ s ω i ≤ s ω ⟨0, Nat.succ_pos n⟩) ∧ μ.real {ω | Real.sqrt (m : ℝ) - C * K ^ 2 * (Real.sqrt (n + 1 : ℝ) + t) > s ω (Fin.last n) ∨ s ω ⟨0, Nat.succ_pos n⟩ > Real.sqrt (m : ℝ) + C * K ^ 2 * (Real.sqrt (n + 1 : ℝ) + t)} ≤ 2 * Real.exp (-(t ^ 2))hdp_
04_ · 1 more declaration under this itemequation_ 4_ 21_ explicit_ svd Equation (4.22)
For a matrix with independent, mean-zero, isotropic sub-Gaussian rows, the normalized right Gram matrix is uniformly close to the identity at scale
K² max(δ,δ²), except on an event of probability at most2 exp (-t²).Lean statement
theorem hdp_04_equation_4_22 : ∃ C : ℝ, 0 < C ∧ ∀ {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {m n : ℕ} (_hm : 0 < m) (_hn : 0 < n) (A : Ω → Matrix (Fin m) (Fin n) ℝ) {K : ℝ}, 0 < K → (∀ i j, Measurable (fun ω => A ω i j)) → (∀ i j, MemLp (fun ω => A ω i j) 2 μ) → (∀ i j, ∫ ω, A ω i j ∂μ = 0) → (∀ i, NumStability.HDP.Vector.Isotropy.IsIsotropic μ (fun j ω => A ω i j)) → (∀ i, NumStability.HDP.Vector.SubGaussian.PsiTwoNorm μ (fun j ω => A ω i j) ≤ ENNReal.ofReal K) → iIndepFun (fun i ω => fun j => A ω i j) μ → ∀ {t : ℝ}, 0 ≤ t → let δ := C * (Real.sqrt ((n : ℝ) / (m : ℝ)) + t / Real.sqrt (m : ℝ)) μ.real {ω | K ^ 2 * max δ (δ ^ 2) < NumStability.realMatrixOperatorNorm (((m : ℝ)⁻¹) • ((A ω).transpose * A ω) - (1 : Matrix (Fin n) (Fin n) ℝ))} ≤ 2 * Real.exp (-(t ^ 2))Equation (4.23)
For a fixed vector
x, settingXᵢ=⟨Aᵢ,x⟩expands the squared Euclidean norm ofAxas∑ᵢ Xᵢ². The identity does not require the source's unit-vector specialization.Lean statement
theorem hdp_04_equation_4_23 {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (x : Fin n → ℝ) : ∃ X : Fin m → ℝ, (∀ i, X i = dotProduct (A i) x) ∧ ‖(WithLp.toLp 2 (A.mulVec x) : EuclideanSpace ℝ (Fin m))‖ ^ 2 = ∑ i, (X i) ^ 2Equation (4.24)
Exact expanded condition-definition audit surface for Equation (4.24), on its probability space and finite ordinary-second-moment domain.
Lean statement
theorem hdp_04_equation_4_24_probability_ordinary {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {n : ℕ} (X : Fin n → Ω → ℝ) : HDP04Equation424ProbabilityOrdinaryCondition (μ := μ) X ↔ (∀ j, Measurable (X j)) ∧ ∃ K : ℝ≥0, 1 ≤ K ∧ ∀ x : Fin n → ℝ, NumStability.HDP.Scalar.SubGaussian.IsSubGaussian μ (NumStability.HDP.Vector.linearMarginal X x) ∧ Integrable (fun ω => (NumStability.HDP.Vector.linearMarginal X x ω) ^ 2) μ ∧ (NumStability.HDP.Scalar.SubGaussian.PsiTwoNorm μ (NumStability.HDP.Vector.linearMarginal X x)).toReal ≤ (K : ℝ) * Real.sqrt (∫ ω, (NumStability.HDP.Vector.linearMarginal X x ω) ^ 2 ∂μ)hdp_
04_ · 1 more declaration under this itemequation_ 4_ 24_ probability_ ordinary Equation (4.25)
Complete owner-qualified pointwise law realization and the actual coefficient-one sample Gram identity and Euclidean operator-norm estimate.
Lean statement
theorem equation425_constructed_pointwise_proved : equation425ConstructedPointwiseTargetequation425_
constructed_ · 2 more declarations under this itempointwise_ proved Example 4.3.2
Over any finite nonempty alphabet, after repeating a message
2r+1times, coordinatewise majority decoding recovers it from any received word with at mostrcorrupted letters.Lean statement
theorem hdp_04_example_4_3_2 {α : Type*} [Fintype α] [Nonempty α] [DecidableEq α] (r k : ℕ) (x : NumStability.HDP.Coding.AlphabetWord α k) (y : Fin (2 * r + 1) × Fin k → α) (hy : hammingDist y (NumStability.HDP.Coding.generalRepetitionEncode r x) ≤ r) : NumStability.HDP.Coding.generalMajorityDecode r k y = xRemark 4.1.7
With
Q = Aᵀ,Q Qᵀ = Iis equivalent toQᵀ Qbeing the rank-northogonal projection, and an isometric embedding is equivalently a projection after transposition. For the source's qualitative approximate analogue, the final conjunct uses an independent row-Gram defect for approximate projections and records explicit quantitative implications in both directions.Lean statement
theorem hdp_04_remark_4_1_7 {n m : ℕ} (A : Matrix (Fin m) (Fin (n + 1)) ℝ) : (NumStability.IsRealMatrixProjection A.transpose ↔ NumStability.IsRealOrthogonalProjectionMatrix (A.transpose.transpose * A.transpose) ∧ (A.transpose.transpose * A.transpose).rank = n + 1) ∧ (NumStability.IsRealMatrixIsometry A ↔ NumStability.IsRealMatrixProjection A.transpose) ∧ ∀ δ : ℝ, 0 ≤ δ → (NumStability.ApproximateIsometryBounds A δ → NumStability.ApproximateProjectionDefect A.transpose (3 * max δ (δ ^ 2))) ∧ (NumStability.ApproximateProjectionDefect A.transpose (max δ (δ ^ 2)) → NumStability.ApproximateIsometryBounds A δ)Remark 4.2.7
At a positive scale, the greedy separated-point construction on a compact set cannot run forever; every non-covering separated stage can be extended; and a finite separated net exists.
Lean statement
theorem hdp_04_hremark_h4_d2_d7 {T : Type*} [MetricSpace T] {K : Set T} {ε : ℝ≥0} (hε : 0 < ε) (hK : IsCompact K) : (¬ ∃ x : ℕ → T, (∀ i, x i ∈ K) ∧ ∀ i j, i ≠ j → (ε : ℝ≥0∞) < edist (x i) (x j)) ∧ (∀ N : Set T, N.Finite → N ⊆ K → Metric.IsSeparated ε N → ¬ Metric.IsCover ε K N → ∃ x ∈ K, x ∉ N ∧ Metric.IsSeparated ε (insert x N)) ∧ ∃ N : Set T, N ⊆ K ∧ N.Finite ∧ Metric.IsSeparated ε N ∧ Metric.IsCover ε K N
Problems and exercises
Exercise 4.1.1
Inverting a full square SVD reciprocates the nonzero singular values and swaps its left and right singular bases.
Lean statement
theorem hdp_04_exercise_4_1_1 {n : ℕ} (A : Matrix (Fin n) (Fin n) ℝ) (s : Fin n → ℝ) (u v : OrthonormalBasis (Fin n) ℝ (EuclideanSpace ℝ (Fin n))) (hs : ∀ i, 0 < s i) (hsvd : NumStability.IsSquareRealSVD A s u v) : NumStability.nonsingInv n A = NumStability.inverseSVDFormula s u vExercise 4.1.2
The
i-th singular value in one-based mathematical indexing is at most||A||_F / sqrt i. The witness sequence is characterized transparently by the full Courant--Fischer property at every index, rather than by Mathlib's opaque implementation of an ordered eigenvalue enumeration. Lean'sFin nindex is zero-based, so the denominator issqrt (i.1 + 1). No positive-row premise is needed, including for the unique zero-row matrix.Lean statement
theorem hdp_04_exercise_4_1_2 {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (i : Fin n) : ∃ singularValue : Fin n → ℝ, Antitone singularValue ∧ (∀ j, NumStability.IsSingularValueMaxMin A singularValue j) ∧ singularValue i ≤ NumStability.frobNormRect A / Real.sqrt (i.1 + 1 : ℕ)Exercise 4.1.3
For the best rank-
kapproximation obtained by truncating an exact rank-k+qSVD, the squared operator error is the square of the next singular value and the squared Frobenius error is the sum of the squared omitted singular values.Lean statement
theorem hdp_04_exercise_4_1_3 {m n k q : ℕ} {A : Matrix (Fin m) (Fin n) ℝ} {s : Fin n → ℝ} {u : Fin (k + q) → EuclideanSpace ℝ (Fin m)} {v : Fin (k + q) → EuclideanSpace ℝ (Fin n)} (h : NumStability.IsRealMatrixSVD A (k + q) s u v) (hq : 0 < q) : let Ak := NumStability.realSVDHead s u v h.rank_le_width NumStability.lowRankResidualOperator A Ak ^ 2 = s (Fin.castLE h.rank_le_width (Fin.natAdd k (⟨0, hq⟩ : Fin q))) ^ 2 ∧ NumStability.lowRankResidualFrob A Ak ^ 2 = ∑ c : Fin q, s (Fin.castLE h.rank_le_width (Fin.natAdd k c)) ^ 2Exercise 4.1.4
The right Gram identity, the rank-
Northogonal-projection property of the left Gram matrix, Euclidean norm preservation, and equality of every singular value to one are equivalent. The source assumesm ≥ N > 0. HereN = n + 1remains positive, while the equivalence also covers wide and rank-deficient matrices: the singular value family has allNentries of the ordered right-Gram spectrum, with zeros retained, including the extra zeros whenm < N. In that wide case all four characterizations are false. Each equivalence is exposed as its two implications; the reusable producer retains the biconditional API.Lean statement
theorem hdp_04_exercise_4_1_4 {m n : ℕ} (A : Matrix (Fin m) (Fin (n + 1)) ℝ) : let gramIdentity : Prop := A.transpose * A = 1 let rangeProjection : Prop := NumStability.IsRealOrthogonalProjectionMatrix (A * A.transpose) ∧ (A * A.transpose).rank = n + 1 let normIsometry : Prop := NumStability.IsRealMatrixIsometry A let allSingularValuesOne : Prop := ∀ i : Fin (n + 1), NumStability.rectCourantFischerSingularValue A i = 1 ((gramIdentity → rangeProjection) ∧ (rangeProjection → gramIdentity)) ∧ ((rangeProjection → normIsometry) ∧ (normIsometry → rangeProjection)) ∧ ((normIsometry → allSingularValuesOne) ∧ (allSingularValuesOne → normIsometry))Exercise 4.1.6
If the extreme singular values satisfy (4.7), then the right Gram matrix differs from the identity by at most
3 * max δ δ²in operator norm.Lean statement
theorem hdp_04_exercise_4_1_6 {m n : ℕ} (A : Matrix (Fin m) (Fin (n + 1)) ℝ) {δ : ℝ} (hδ : 0 < δ) (hSingular : NumStability.ExtremeSingularValueBounds A δ) : NumStability.realMatrixOperatorNorm (A.transpose * A - 1) ≤ 3 * max δ (δ ^ 2)Exercise 4.1.8
Any submatrix formed from distinct columns of a real orthogonal matrix is an isometry, while the corresponding statement for distinct rows gives a projection.
Lean statement
theorem hdp_04_exercise_4_1_8 {N k : ℕ} (U : Matrix (Fin N) (Fin N) ℝ) (hU : U ∈ Matrix.orthogonalGroup (Fin N) ℝ) (f : Fin k → Fin N) (hf : Function.Injective f) : NumStability.IsRealMatrixIsometry (U.submatrix id f) ∧ NumStability.IsRealMatrixProjection (U.submatrix f id)Exercise 4.2.9
Lean statement
theorem exercise429NumericalTarget_proved : exercise429NumericalTargetexercise429Numerical
Target_ · 2 more declarations under this itemproved Exercise 4.2.10
In an exact-cardinal witness form. The real three-point example has an internal one-center cover, while its two-point subset has exact internal covering cardinality two. Under inclusion, every internal half-radius cover of the larger set yields an internal full-radius cover of the subset with no larger cardinality.
Lean statement
theorem hdp_04_exercise_4_2_10 : (∃ (L K : Set ℝ) (ε : ℝ≥0), 0 < ε ∧ L ⊆ K ∧ (∃ C : Set ℝ, C ⊆ K ∧ (∀ ⦃x⦄, x ∈ K → ∃ y ∈ C, dist x y ≤ (ε : ℝ)) ∧ Cardinal.mk C = 1) ∧ (∃ N : Set ℝ, N ⊆ L ∧ (∀ ⦃x⦄, x ∈ L → ∃ y ∈ N, dist x y ≤ (ε : ℝ)) ∧ Cardinal.mk N = 2) ∧ ∀ N : Set ℝ, N ⊆ L → (∀ ⦃x⦄, x ∈ L → ∃ y ∈ N, dist x y ≤ (ε : ℝ)) → 2 ≤ Cardinal.mk N) ∧ (∀ {T : Type*} [MetricSpace T] {L K : Set T} {ε : ℝ≥0}, 0 < ε → L ⊆ K → ∀ C : Set T, C ⊆ K → (∀ ⦃x⦄, x ∈ K → ∃ y ∈ C, dist x y ≤ ((ε / 2 : ℝ≥0) : ℝ)) → ∃ N : Set T, N ⊆ L ∧ (∀ ⦃x⦄, x ∈ L → ∃ y ∈ N, dist x y ≤ (ε : ℝ)) ∧ Cardinal.mk N ≤ Cardinal.mk C)Exercise 4.2.15
The Hamming distance is a metric. Mathlib proves the stronger alphabet-generic result for every finite coordinate type.
Lean statement
theorem hdp_04_hexercise_h4_d2_d15 {ι : Type*} (β : ι → Type*) [Fintype ι] [∀ i, DecidableEq (β i)] : Nonempty {m : MetricSpace (Hamming β) // m.toDist = Hamming.instDist} ∧ ∀ x y : ∀ i, β i, hammingDist x y = #{i | x i ≠ y i}Exercise 4.2.16
The covering and packing numbers of the binary Hamming cube are bounded by the reciprocal volumes of Hamming balls. Multiplying by the positive binomial sums avoids division in
ℕ∞and is equivalent to the three displayed inequalities in the source.Lean statement
theorem hdp_04_exercise_4_2_16 (n m : ℕ) (hm : m ≤ n) : (2 ^ n : ℕ∞) ≤ NumStability.HDP.Coding.binaryHammingCoveringNumber n m * (∑ j ∈ Finset.range (m + 1), n.choose j) ∧ NumStability.HDP.Coding.binaryHammingCoveringNumber n m ≤ NumStability.HDP.Coding.binaryHammingPackingNumberAt n m ∧ NumStability.HDP.Coding.binaryHammingPackingNumberAt n m * (∑ j ∈ Finset.range (m / 2 + 1), n.choose j) ≤ (2 ^ n : ℕ∞)Exercise 4.3.7
Exercise 4.3.7 (Optimality). For every code correcting
rerrors, its codebook is bounded by the2r-packing number, its radius-rHamming balls satisfy the sphere-packing count, and (when0 < r ≤ n) its rate satisfies the literal bound from the exerciseR ≤ 1 - δ log₂(1/δ), whereδ = r/n.Lean statement
theorem hdp_04_exercise_4_3_7_converse {k n r : ℕ} (C : NumStability.HDP.Coding.ErrorCorrectingCode k n r) (hk : 0 < k) (hr : 0 < r) : Metric.IsSeparated (((2 * r : ℕ) : ℝ≥0) : ℝ≥0∞) (Set.range fun x : NumStability.HDP.Coding.BinaryWord k ↦ Hamming.toHamming (C.encode x) : Set (NumStability.HDP.Coding.BinaryHammingSpace n)) ∧ ENat.card (NumStability.HDP.Coding.BinaryWord k) ≤ NumStability.HDP.Coding.binaryHammingPackingNumber n r ∧ 2 ^ k * NumStability.HDP.Coding.hammingBallVolume n r ≤ 2 ^ n ∧ NumStability.HDP.Coding.codingRate k n ≤ 1 - NumStability.HDP.Coding.errorFraction r n * Real.logb 2 (1 / NumStability.HDP.Coding.errorFraction r n)Exercise 4.4.2
The supremum of the inner products of
xwith any set-valuedε-net of the Euclidean unit sphere approximates‖x‖₂within the factor(1 - ε)⁻¹. The surrounding Lemma 4.4.1 allows0 ≤ ε < 1; here onlyε < 1is an explicit premise. The net condition in positive dimension already excludes negative radii, so the stated domain includes the source's zero-radius case.Lean statement
theorem hdp_04_exercise_4_4_2 {n : ℕ} (hn : 0 < n) (x : EuclideanSpace ℝ (Fin n)) (ε : ℝ) (N : Set (EuclideanSpace ℝ (Fin n))) (hε1 : ε < 1) (hN : NumStability.HDP.Metric.IsUnitSphereNet ε N) : sSup {a : ℝ | ∃ y ∈ N, a = inner ℝ x y} ≤ ‖x‖ ∧ ‖x‖ ≤ (1 - ε)⁻¹ * sSup {a : ℝ | ∃ y ∈ N, a = inner ℝ x y}Exercise 4.4.3
An arbitrary
ε-net in each sphere controls a rectangular matrix's bilinear operator norm, and for a symmetric square matrix one arbitrary net controls the absolute quadratic form, in both cases with factor(1 - 2ε)⁻¹.Lean statement
theorem hdp_04_exercise_4_4_3 : (∀ {m n : ℕ}, 0 < m → 0 < n → (A : Matrix (Fin m) (Fin n) ℝ) → (ε : ℝ) → (N : Set (EuclideanSpace ℝ (Fin n))) → (M : Set (EuclideanSpace ℝ (Fin m))) → 0 ≤ ε → ε < 1 / 2 → NumStability.HDP.Metric.IsUnitSphereNet ε N → NumStability.HDP.Metric.IsUnitSphereNet ε M → sSup {a : ℝ | ∃ x ∈ N, ∃ y ∈ M, a = inner ℝ (Matrix.toEuclideanLin A x) y} ≤ NumStability.realMatrixOperatorNorm A ∧ NumStability.realMatrixOperatorNorm A ≤ (1 - 2 * ε)⁻¹ * sSup {a : ℝ | ∃ x ∈ N, ∃ y ∈ M, a = inner ℝ (Matrix.toEuclideanLin A x) y}) ∧ (∀ {n : ℕ}, 0 < n → (A : Matrix (Fin n) (Fin n) ℝ) → A.IsHermitian → (ε : ℝ) → (N : Set (EuclideanSpace ℝ (Fin n))) → 0 ≤ ε → ε < 1 / 2 → NumStability.HDP.Metric.IsUnitSphereNet ε N → sSup {a : ℝ | ∃ x ∈ N, a = |NumStability.realMatrixQuadraticForm A x|} ≤ NumStability.realMatrixOperatorNorm A ∧ NumStability.realMatrixOperatorNorm A ≤ (1 - 2 * ε)⁻¹ * sSup {a : ℝ | ∃ x ∈ N, a = |NumStability.realMatrixQuadraticForm A x|})hdp_
04_ · 1 more declaration under this itemexercise_ 4_ 4_ 3 Exercise 4.4.4
With the absolute constant quantified before all matrix dimensions and data. The preceding theorem supplies the explicit universal choice
C = 3.Lean statement
theorem hdp_04_exercise_4_4_4 : ∃ C : ℝ, 0 < C ∧ ∀ {m n : ℕ} (_hn : 0 < n) (A : Matrix (Fin m) (Fin n) ℝ) (μ ε : ℝ) (N : Set (EuclideanSpace ℝ (Fin n))), 0 ≤ ε → ε < 1 / 2 → NumStability.HDP.Metric.IsUnitSphereNet ε N → ∀ u : EuclideanSpace ℝ (Fin n), ‖u‖ = 1 → |‖Matrix.toEuclideanLin A u‖ - μ| ≤ C * (1 - 2 * ε)⁻¹ * sSup {a : ℝ | ∃ x ∈ N, a = |‖Matrix.toEuclideanLin A x‖ - μ|}hdp_
04_ · 2 more declarations under this itemexercise_ 4_ 4_ 4 Exercise 4.4.7
Under Theorem 4.4.5's independent centered sub-Gaussian hypotheses and the additional unit-variance assumption, the expected operator norm is at least
(sqrt m + sqrt n) / 4once both dimensions are sufficiently large. The threshold is chosen before the dimensions and the matrix, and depends only on a common upper bound for the entrywiseψ₂scale (and on the absolute constant).Lean statement
theorem hdp_04_exercise_4_4_7 : ∃ C : ℝ, 1 ≤ C ∧ ∀ K : ℝ, 0 ≤ K → ∃ N : ℕ, ∀ {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {m n : ℕ} (hm : 0 < m) (hn : 0 < n), N ≤ m → N ≤ n → letI : Nonempty (Fin m) := Fin.pos_iff_nonempty.mp hm letI : Nonempty (Fin n) := Fin.pos_iff_nonempty.mp hn ∀ (A : Ω → Matrix (Fin m) (Fin n) ℝ), (∀ ij : Fin m × Fin n, NumStability.HDP.Scalar.SubGaussian.IsSubGaussian μ (fun ω ↦ A ω ij.1 ij.2)) → (∀ ij : Fin m × Fin n, Integrable (fun ω ↦ A ω ij.1 ij.2) μ ∧ (∫ ω, A ω ij.1 ij.2 ∂μ) = 0) → (∀ ij : Fin m × Fin n, (∫ ω, A ω ij.1 ij.2 ^ 2 ∂μ) = 1) → iIndepFun (fun ij : Fin m × Fin n ↦ fun ω ↦ A ω ij.1 ij.2) μ → NumStability.HDP.Scalar.SubGaussian.psiTwoNormMax μ (fun ij : Fin m × Fin n ↦ fun ω ↦ A ω ij.1 ij.2) ≤ K → (Real.sqrt (m : ℝ) + Real.sqrt (n : ℝ)) / 4 ≤ ∫ ω, NumStability.realMatrixOperatorNorm (A ω) ∂μExercise 4.5.4
Weyl's inequality, here proved by the reusable theorem whose proof proceeds from the Courant--Fischer max--min characterization as requested by the exercise.
Lean statement
theorem hdp_04_exercise_4_5_4 {n : ℕ} (S T : Matrix (Fin n) (Fin n) ℝ) (hS : S.IsHermitian) (hT : T.IsHermitian) (i : Fin n) : (∀ j k : Fin n, j ≤ k → NumStability.hermitianOrderedEigenvalue hS k ≤ NumStability.hermitianOrderedEigenvalue hS j) ∧ (∀ j k : Fin n, j ≤ k → NumStability.hermitianOrderedEigenvalue hT k ≤ NumStability.hermitianOrderedEigenvalue hT j) ∧ |NumStability.hermitianOrderedEigenvalue hS i - NumStability.hermitianOrderedEigenvalue hT i| ≤ NumStability.realMatrixOperatorNorm (S - T)Exercise 4.6.2
Integrating Equation (4.22) bounds the expected normalized Gram-matrix deviation by
C K² (sqrt (n/m) + n/m). Integrability is explicit under the module's finite-expectation convention.Lean statement
theorem hdp_04_exercise_4_6_2 : ∃ C : ℝ, 0 < C ∧ ∀ {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {m n : ℕ} (_hm : 0 < m) (_hn : 0 < n) (A : Ω → Matrix (Fin m) (Fin n) ℝ) {K : ℝ}, 0 < K → (∀ i j, Measurable (fun ω => A ω i j)) → (∀ i j, MemLp (fun ω => A ω i j) 2 μ) → (∀ i j, ∫ ω, A ω i j ∂μ = 0) → (∀ i, NumStability.HDP.Vector.Isotropy.IsIsotropic μ (fun j ω => A ω i j)) → (∀ i, NumStability.HDP.Vector.SubGaussian.PsiTwoNorm μ (fun j ω => A ω i j) ≤ ENNReal.ofReal K) → iIndepFun (fun i ω => fun j => A ω i j) μ → Integrable (fun ω => NumStability.realMatrixOperatorNorm (((m : ℝ)⁻¹) • ((A ω).transpose * A ω) - (1 : Matrix (Fin n) (Fin n) ℝ))) μ → (∫ ω, NumStability.realMatrixOperatorNorm (((m : ℝ)⁻¹) • ((A ω).transpose * A ω) - (1 : Matrix (Fin n) (Fin n) ℝ)) ∂μ) ≤ C * K ^ 2 * (Real.sqrt ((n : ℝ) / (m : ℝ)) + (n : ℝ) / (m : ℝ))Exercise 4.6.4
The conclusion of Theorem 4.6.1, whose alternative proof combines Theorem 3.1.1 norm concentration with the unsquared net estimate from Exercise 4.4.4 and a finite union bound. The complete endpoint statement is preserved.
Lean statement
theorem hdp_04_exercise_4_6_4 : ∃ C : ℝ, 0 < C ∧ ∀ {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {m n : ℕ} (_hm : 0 < m) (A : Ω → Matrix (Fin m) (Fin (n + 1)) ℝ) {K : ℝ}, 1 ≤ K → (∀ i j, Measurable (fun ω => A ω i j)) → (∀ i j, MemLp (fun ω => A ω i j) 2 μ) → (∀ i j, ∫ ω, A ω i j ∂μ = 0) → (∀ i, NumStability.HDP.Vector.Isotropy.IsIsotropic μ (fun j ω => A ω i j)) → (∀ i, NumStability.HDP.Vector.SubGaussian.PsiTwoNorm μ (fun j ω => A ω i j) ≤ ENNReal.ofReal K) → iIndepFun (fun i ω => fun j => A ω i j) μ → ∀ {t : ℝ}, 0 ≤ t → ∀ (r : Ω → ℕ) (s : Ω → Fin (n + 1) → ℝ) (u : ∀ ω, Fin (r ω) → EuclideanSpace ℝ (Fin m)) (v : ∀ ω, Fin (r ω) → EuclideanSpace ℝ (Fin (n + 1))), (∀ ω, NumStability.IsRealMatrixSVD (A ω) (r ω) (s ω) (u ω) (v ω)) → (∀ ω i, s ω (Fin.last n) ≤ s ω i ∧ s ω i ≤ s ω ⟨0, Nat.succ_pos n⟩) ∧ μ.real {ω | Real.sqrt (m : ℝ) - C * K ^ 2 * (Real.sqrt (n + 1 : ℝ) + t) > s ω (Fin.last n) ∨ s ω ⟨0, Nat.succ_pos n⟩ > Real.sqrt (m : ℝ) + C * K ^ 2 * (Real.sqrt (n + 1 : ℝ) + t)} ≤ 2 * Real.exp (-(t ^ 2))hdp_
04_ · 1 more declaration under this itemexercise_ 4_ 6_ 4 Exercise 4.7.3
The covariance-estimation error obeys the stated
n+uhigh-probability bound. As in Theorem 4.7.1, the contract uses the proof's whitened representationXᵢ = B Zᵢ, allowing singularB.Lean statement
theorem hdp_04_exercise_4_7_3 : ∃ C : ℝ, 0 < C ∧ ∀ {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {m n : ℕ}, 0 < m → 0 < n → ∀ (A : Ω → Matrix (Fin m) (Fin n) ℝ) (B Sigma : Matrix (Fin n) (Fin n) ℝ) (SigmaM : Ω → Matrix (Fin n) (Fin n) ℝ) {K : ℝ}, 1 ≤ K → (∀ i j, Measurable (fun ω ↦ A ω i j)) → (∀ i j, MemLp (fun ω ↦ A ω i j) 2 μ) → (∀ i, NumStability.HDP.Vector.Isotropy.IsIsotropic μ (fun j ω ↦ A ω i j)) → (∀ i, NumStability.HDP.Vector.SubGaussian.PsiTwoNorm μ (fun j ω ↦ A ω i j) ≤ ENNReal.ofReal K) → iIndepFun (fun i ω ↦ fun j ↦ A ω i j) μ → Sigma = B * B.transpose → (∀ ω, SigmaM ω = B * ((m : ℝ)⁻¹ • ((A ω).transpose * A ω)) * B.transpose) → ∀ {u : ℝ}, 0 ≤ u → μ.real {ω | C * K ^ 2 * (Real.sqrt (((n : ℝ) + u) / (m : ℝ)) + ((n : ℝ) + u) / (m : ℝ)) * NumStability.realMatrixOperatorNorm Sigma < NumStability.realMatrixOperatorNorm (SigmaM ω - Sigma)} ≤ 2 * Real.exp (-u)