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 ^ 2

    hdp_01_hcor_h1_d2_d5

  • Theorem 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 ω ∂μ))

    hdp_01_hthm_h1_d3_d1

  • 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_hthm_h1_d3_d2_tail · 4 more declarations under this item

  • 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 to Poisson(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))

    hdp_01_hthm_h1_d3_d4

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 ω)) ∂μ

    hdp_01_hdef_hmgf_spec

  • Result

    The two displayed L^p norm 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 μ

    hdp_01_hdef_hlp_hnorm_spec

  • Result

    The two displayed formulas for Z_N agree when the partial sum has mean N m, variance N σ², and N, σ 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 σ N

    hdp_01_hdef_hzn_eq_source_normalization

  • Result

    For every exponent p ∈ [1,∞], the L^p quotient 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 μ))

    hdp_01_hthm_hlp_hbanach_spec

  • Result

    For a measurable representative and a positive exponent, membership in L^p is exactly finiteness of the extended L^p norm.

    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 μ < ⊤

    hdp_01_hdef_hlp_hspace_spec

  • 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 X is the Lebesgue integral of X. The second conjunct is the printed formula Var(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))

    hdp_01_hdef_hexpectation_hvariance_spec

  • Result

    For every 0 < p < 1, two disjoint singleton indicators on the uniform two-point probability space violate the L^p triangle 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 μ

    hdp_01_hclaim_hlp_hquasinorm_spec

  • 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 μ).toReal

    hdp_01_hthm_hcauchy_hschwarz

  • Result

    Hölder's inequality on the book's probability-space L^p classes. 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)

    hdp_01_hthm_hholder_spec

  • 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 ω))

    hdp_01_hthm_hjensen

  • 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)

    hdp_01_hdef_hcdf_spec

  • 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) * φ y

    hdp_01_hdef_hconvex_hfunction_spec

  • Result

    The source's indicator 1_E is one on E and zero off E.

    Lean statement
    theorem hdp_01_hdef_hindicator
        {Ω : Type*} [MeasurableSpace Ω] (E : Set Ω) (ω : Ω) :
        (ω ∈ E → indicatorFunction E ω = 1) ∧
          (ω ∉ E → indicatorFunction E ω = 0)

    hdp_01_hdef_hindicator

  • 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 t

    hdp_01_heq_htail_hcdf_spec

  • Result

    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)

    hdp_01_hdef_hbernoulli

  • Result

    The binomial component of the Chapter 1 model: the success count of the canonical vector of N Bernoulli 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) N

    hdp_01_hdef_hbinomial

  • Result

    The variance of the mean of the first N + 1 iid 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)

    hdp_01_hclaim_hsample_hmean_hvariance_hlimit

  • 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; μ]

    hdp_01_hlem_hindependent_hvariance_hsum

  • 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 of E|X|². Mathlib's Lp supplies 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_heq_h1_d1_spec · 1 more declaration under this item

  • 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)

    hdp_01_heq_h1_d2_spec

  • Equation (1.4)

    On the book's probability-space L^p, the L^p size satisfies the triangle inequality for every extended exponent p ≥ 1, including p = ∞. The MemLp hypotheses record the source's premise that X and Y belong to L^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 μ

    hdp_01_heq_h1_d4_spec

  • 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⟩; μ]

    hdp_01_heq_h1_d5

  • 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)

    hdp_01_heq_h1_d6

  • 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)

    hdp_01_heq_h1_d8

  • 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 ω}

    hdp_01_hlem_h1_d2_d1_hindicator_hexpectation_spec

  • Result

    A real number splits across the complementary events x ≥ t and x < 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)

    hdp_01_hprop_h1_d2_d4_hdecomposition_spec

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 ^ 2

    hdp_01_hex_h1_d2_d6 · 1 more declaration under this item

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_hdef_h2_d5_d6 · 1 more declaration under this item

  • 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_hdef_h2_d7_d5_exact · 1 more declaration under this item

  • 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 ^ 2

    hdp_02_hlem_h2_d7_d6_exact · 3 more declarations under this item

  • 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_hprop_h2_d1_d2 · 3 more declarations under this item

  • 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 : ℝ) / 10

    hdp_02_hprop_h2_d4_d1

  • Theorem 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))

    hdp_02_hthm_h2_d2_d2

  • 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))

    hdp_02_hthm_h2_d2_d5_source

  • 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))

    hdp_02_hthm_h2_d2_d6_source

  • 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)

    hdp_02_hthm_h2_d3_d1_source

  • Theorem 2.9.1

    Lean statement
    theorem hdp_02_hthm_h2_d9_d1_exact :
        hdp_02_hthm_h2_d9_d1__contract_type

    hdp_02_hthm_h2_d9_d1_exact · 2 more declarations under this item

  • Theorem 2.9.2

    Lean statement
    theorem hdp_02_hthm_h2_d9_d2_exact :
        hdp_02_hthm_h2_d9_d2__contract_type

    hdp_02_hthm_h2_d9_d2_exact · 1 more declaration under this item

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|)

    hdp_02_hbody_h2_d6_hconstant_hpsi2

  • 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 : ℝ))))

    hdp_02_hbody_h2_d4_hdegree_hchernoff

  • 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)

    hdp_02_hbody_h2_d4_hunion_hbound

  • Result

    Section 2.1, printed page 12: if S_N is the number of heads in N independent fair coin tosses, then E S_N = N / 2 and Var(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 ι : ℝ) / 4

    hdp_02_hbody_h2_d1_hsn_hmoments

  • Result

    Printed page 14: in N = 2n fair tosses the central count has probability 2⁻ᴺ * binom(N,N/2), the standardized count has the same mass at zero, and that mass is comparable to 1 / 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 : ℝ)))

    hdp_02_hbody_h2_d1_hbinom_hcentral

  • 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} = 0

    hdp_02_hbody_h2_d1_hgaussian_hatom

  • Result

    Section 2.1, printed page 13: with Z_N = (S_N - N/2) / sqrt (N/4), the events S_N ≥ 3N/4 and Z_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)}

    hdp_02_hbody_h2_d1_hzn_hidentity

  • 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)

    hdp_02_hnotation_h2_d1_hasymptotic

  • 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)

    hdp_02_hbody_h2_d2_hcosh_hmgf

  • 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)

    hdp_02_hbody_h2_d2_hcoin_hbound

  • 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}

    hdp_02_hbody_h2_d2_htwo_hsided_hsplit

  • 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)

    affineBernoulliIsRademacherIff

  • 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 x

    hdp_02_hbody_h2_d3_hone_hplus_hx

  • Result

    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 : ℝ)))

    hdp_02_hlem_hbernoulli_hmgf_hbound_scalar

  • 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 : ℝ)

    hdp_02_hbody_h2_d4_hexpected_hdegree

  • 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 μ X

    hdp_02_hbody_h2_d5_hpsi2_hsquare_hpoint_effectiveDomain

  • Result

    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))

    hdp_02_hbody_h2_d5_hpsi2_hminimality_effectiveDomain

  • 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))

    hdp_02_hbody_h2_d7_hgaussian_hsquare_htail

  • Result

    Lean statement
    theorem hdp_02_hbody_h2_d7_horlicz_hbanach_exact :
        hdp_02_hbody_h2_d7_horlicz_hbanach__contract_type

    hdp_02_hbody_h2_d7_horlicz_hbanach_exact

  • Result

    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)})

    hdp_02_hbody_h2_d2_hwlog_hnorm

  • Equation (2.1)

    Printed page 12: Chebyshev's 4/N bound for at least 3N/4 heads.

    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_heq_h2_d1 · 1 more declaration under this item

  • Equation (2.3)

    Printed page 13: for t ≥ 1, the standard-normal upper tail is bounded by the standard-normal density at t.

    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_heq_h2_d3 · 1 more declaration under this item

  • 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 ω) ∂μ))

    hdp_02_heq_h2_d5

  • 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 ω)) ∂μ

    hdp_02_hlem_hmgf_hindependent_hsum

  • 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)) ∂μ

    hdp_02_heq_h2_d7

  • 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)

    hdp_02_heq_h2_d8

  • 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)

    hdp_02_heq_h2_d10

  • Equation (2.11)

    Lean statement
    theorem standardNormalLpNormGrowth :
        ∃ C : ℝ, 0 < C ∧
          ∀ p : ℝ, 1 ≤ p →
            (∫ x : ℝ, |x| ^ p ∂(gaussianReal 0 1)) ^ (1 / p) ≤ C * Real.sqrt p

    standardNormalLpNormGrowth

  • Equation (2.12)

    Lean statement
    theorem hdp_02_heq_h2_d12 (lam : ℝ) :
        ∫ x, Real.exp (lam * x) ∂(gaussianReal 0 1) =
          Real.exp (lam ^ 2 / 2)

    hdp_02_heq_h2_d12

  • 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}

    psiTwoNorm_eq_sInf

  • 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)

    psiTwoGaugeToTail

  • 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)

    psiTwoGaugeToLpMomentGrowth

  • 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)

    psiTwoGaugeToMGF

  • 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))

    essentiallyBoundedPsiTwoGauge

  • 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)) μ

    hdp_02_heq_h2_d18

  • 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_heq_h2_d19 · 1 more declaration under this item

  • 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_heq_h2_d20 · 1 more declaration under this item

  • Equation (2.21)

    The psi_1 gauge 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_heq_h2_d21_exact · 1 more declaration under this item

  • Equation (2.22)

    After normalizing both psi_2 scales 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) ≤ 2

    hdp_02_heq_h2_d22_exact · 1 more declaration under this item

  • 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 ω)) ∂μ

    hdp_02_heq_h2_d23

  • 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_type

    hdp_02_heq_h2_d24_effectiveWindow · 1 more declaration under this item

  • 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 * σ)

    hdp_02_hexample_h2_d5_d8a

  • 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))

    hdp_02_hexample_h2_d5_d8c

  • 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_type

    hdp_02_hexample_h2_d7_d8 · 1 more declaration under this item

  • Example 2.7.12

    Lean statement
    theorem hdp_02_hexample_h2_d7_d12_exact :
        hdp_02_hexample_h2_d7_d12__contract_type

    hdp_02_hexample_h2_d7_d12_exact · 2 more declarations under this item

  • Example 2.7.13

    Lean statement
    theorem hdp_02_hexample_h2_d7_d13_exact :
        hdp_02_hexample_h2_d7_d13__contract_type

    hdp_02_hexample_h2_d7_d13_exact · 3 more declarations under this item

  • 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_hrem_h2_d3_d4 · 1 more declaration under this item

  • 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_hrem_h2_d7_d14_exact · 1 more declaration under this item

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_sq_mul_exp_neg_sq_div_two · 3 more declarations under this item

  • Exercise 2.2.3

    Lean statement
    theorem hdp_02_hex_h2_d2_d3 (x : ℝ) :
        Real.cosh x ≤ Real.exp (x ^ 2 / 2)

    hdp_02_hex_h2_d2_d3

  • Exercise 2.2.7

    Discharged with the exact constant 2 stated 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))

    hdp_02_hex_h2_d2_d7_source

  • 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} ≤ ε

    hdp_02_hex_h2_d2_d8

  • 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 / 4

    hdp_02_hex_h2_d2_d9a

  • Exercise 2.2.9b

    Exercise 2.2.9(b), with n observations in each of 2k+1 independent blocks. The explicit weak-estimate constant is 4, 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 ∂μ|} ≤ δ

    hdp_02_hex_h2_d2_d9b

  • 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 / t

    hdp_02_hex_h2_d2_d10a

  • Exercise 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_hex_h2_d3_d2_effectiveDomain · 2 more declarations under this item

  • 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)

    hdp_02_hex_h2_d3_d3

  • 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_hex_h2_d3_d5 · 1 more declaration under this item

  • 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_hex_h2_d3_d6 · 1 more declaration under this item

  • 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 : ℝ)

    poissonPMFReal_firstMoment_hasSum · 2 more declarations under this item

  • 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 : ℝ) / 10

    hdp_02_hex_h2_d4_d2

  • Exercise 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 : ℝ) / 10

    hdp_02_hex_h2_d4_d3

  • Exercise 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 : ℝ) / 10

    hdp_02_hex_h2_d4_d4 · 1 more declaration under this item

  • 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)

    hdp_02_hex_h2_d5_d1

  • 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))

    hdp_02_hex_h2_d5_d5a

  • 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} = 0

    squareMGFGlobalTailZero

  • Exercise 2.6.4

    Exercise 2.6.4 in the literal no-prefactor form of Theorem 2.2.6. The separate BoundedHoeffdingFromSubGaussian module records the immediate two-sided deduction from Theorem 2.6.3; it necessarily retains a leading 2, 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_type

    hdp_02_hex_h2_d6_d4 · 2 more declarations under this item

  • 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 Kj

    hdp_02_hex_h2_d7_d2_exact · 1 more declaration under this item

  • Exercise 2.7.3

    For every positive power alpha, applying the four sub-exponential characterizations to |X|^alpha gives a quantitative characterization of tails on the scale exp (-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 Kj

    hdp_02_hex_h2_d7_d3_exact · 1 more declaration under this item

  • Exercise 2.7.4

    The property-(c) bound cannot be extended from 0 <= lambda to every |lambda| <= K3⁻¹. The constant-zero random variable already violates the proposed bound at K3 = 1 and lambda = -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_hex_h2_d7_d4_exact · 1 more declaration under this item

  • Exercise 2.7.11

    Lean statement
    theorem hdp_02_hex_h2_d7_d11_exact : hdp_02_hex_h2_d7_d11__contract_type

    hdp_02_hex_h2_d7_d11_exact · 1 more declaration under this item

  • 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_hex_h2_d8_d5 · 3 more declarations under this item

  • 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_type

    hdp_02_hex_h2_d8_d6_effectiveDomain · 2 more declarations under this item

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 SimpleGraph supplies 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)

    hdp_04_algorithm_4_5_spectral_clustering

  • 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=0 is 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_algorithm_4_7_spectral_clustering · 1 more declaration under this item

  • 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) ^ n

    hdp_04_corollary_4_2_13

  • Definition 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 ε)

    hdp_04_hdef_h4_d2_d1

  • 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})

    hdp_04_hdef_h4_d2_d2

  • Definition 4.2.4

    Lean statement
    theorem definition424OwnerQualifiedPositiveTarget_proved :
        definition424OwnerQualifiedPositiveTarget

    definition424OwnerQualifiedPositiveTarget_proved · 1 more declaration under this item

  • 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}

    hdp_04_hdef_h4_d2_d11

  • Definition 4.2.14

    Binary strings of length n form the Hamming cube, their Hamming distance counts the coordinates where they disagree, and the Hamming type 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 : ℝ)

    hdp_04_hdef_h4_d2_d14

  • Definition 4.3.3

    An arbitrary encoder E can correct r errors exactly when there is a decoder recovering every message from every word at Hamming distance at most r. 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)

    hdp_04_definition_4_3_3

  • Definition 4.5.1

    Two communities of size k, independent Bernoulli edge choices with probabilities p within and q across them, and the equal-parameter Erdős--Rényi specialization. Finite configurations include the empty configuration with probability one, including k=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∞))

    hdp_04_definition_4_5_1

  • Definition 4.7.4

    The equal mixture of N(μ,I) and N(-μ,I) is the law of θμ+g for an independent Rademacher sign and standard Gaussian vector; an m-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 μ)

    hdp_04_definition_4_7_4

  • 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 between 1 - δ and 1 + δ, 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 δ

    hdp_04_lemma_4_1_5

  • 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_maximal_separated_positive_is_net · 3 more declarations under this item

  • 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_lemma_4_2_8_owner_qualified_numerical_proved · 2 more declarations under this item

  • Lemma 4.3.4

    If the base-two logarithm of the packing number of the binary Hamming cube at separation 2r is at least k, then there is an n-bit encoding of k-bit strings which corrects r errors. 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)

    hdp_04_lemma_4_3_4

  • 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‖}

    hdp_04_lemma_4_4_1

  • 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-ε / 2 ball. The two volume-ratio inequalities are written in cross-multiplied form in ENNReal. 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 on K.

    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_proposition_4_2_12 · 1 more declaration under this item

  • Proposition 4.3.1

    In its exact integer-threshold form. An N-bit code at accuracy ε forces the ε-covering number to be at most 2^N. Conversely, an ε/2-cover with at most 2^N centers produces an N-bit code at accuracy ε. Taking the least admissible N gives 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)

    hdp_04_proposition_4_3_1

  • 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)

    hdp_04_theorem_4_5_3

  • 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 most 2 ‖S - T‖ / δ. The second conjunct in hgap records 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) / δ

    hdp_04_theorem_4_5_5

  • Theorem 4.5.6

    The owner-qualified complete Theorem 4.5.6 for the actual loopless balanced stochastic block model. k ranges over positive half-sizes through hn, so n = 2*k ≥ 2; community ranges 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_unit

    theorem456_owner_qualified_all_unit_proved · 3 more declarations under this item

  • 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_theorem_4_6_1_explicit_svd · 2 more declarations under this item

  • 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_theorem_4_7_1_explicit_probability · 1 more declaration under this item

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 : ℕ∞)

    hdp_04_coding_complexity_definition

  • 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)

    hdp_04_covariance_matrix_definition

  • 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 = ⊤)

    hdp_04_diameter_definition

  • 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)

    hdp_04_distance_distortion_explicit_svd

  • Result

    Vershynin, Chapter 4, printed page 78, Eckart--Young--Mirsky: if A = ∑ᵢ sᵢ uᵢvᵢᵀ has rank k+q with q>0, its first k SVD terms form a rank-at-most-k approximation 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 Ak

    hdp_04_eckart_young_mirsky

  • Result

    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) ≤ 2

    errorCorruptionStringAtMostTwoExample

  • Result

    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 :
        HDP04EuclideanPositiveCoveringValue

    hdp_04_euclidean_positive_covering_value

  • Result

    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)

    hdp_04_frobenius_norm_sq_eq_inner_self

  • 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)

    hdp_04_frobenius_norm_definition

  • 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)

    hdp_04_frobenius_norm_eq_sqrt_sum_singular_values_sq

  • 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 2

    hdp_04_metric_entropy_definition

  • Result

    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)

    hdp_04_notes_binary_entropy_ordinary_domain

  • Result

    Printed page 76: for a real m by n matrix with nonzero domain and codomain dimensions, the operator norm is the maximum of ⟪A x, y⟫_ℝ over unit vectors x and y.

    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)

    hdp_04_operator_norm_bilinear

  • 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)

    hdp_04_operator_norm_definition

  • 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)

    hdp_04_orthogonal_projection_definition

  • 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))

    hdp_04_sample_covariance_almost_sure

  • 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 b

    hdp_04_sample_covariance_definition

  • Result

    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 b

    hdp_04_sample_covariance_unbiased

  • Result

    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 : ℝ))

    hdp_04_sbm_dense_regime_constant_error_explicit

  • Result

    One event supplies the coupled unit-vector, scaled-error and classifier bounds.

    Lean statement
    theorem sbm_eigenvector_sign_correction_full_body_proved : HDP04SBMEigenvectorSignCorrectionFullBodyTarget

    sbm_eigenvector_sign_correction_full_body_proved

  • Result

    The common-event sign-disagreement bound, with global label matching.

    Lean statement
    theorem sbm_sign_disagreement_full_body_proved : HDP04SBMSignDisagreementFullBodyTarget

    sbm_sign_disagreement_full_body_proved

  • Result

    Printed pages 75–76: the left and right singular-vector families are orthonormal eigenvectors of A Aᵀ and Aᵀ 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 v

    hdp_04_singular_eigenvalue_relations

  • Result

    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) i

    hdp_04_singular_value_minmax

  • Result

    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 s

    hdp_04_singular_vector_norm_comparison_check

  • Result

    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 rightVector

    hdp_04_symmetric_singular_values

  • Result

    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 : thirtyLetterQualifiedTarget

    thirtyLetterQualifiedProof

  • Equation (4.1)

    Printed page 75: every real rectangular matrix is a sum of rank A singular-value rank-one terms s 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 j

    hdp_04_heq_h4_d1

  • Equation (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) i

    hdp_04_heq_h4_d2

  • Equation (4.3)

    The canonical matrix inner product is both the trace of AᵀB and 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 j

    hdp_04_eq_4_3

  • Equation (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.RealOperatorFrobeniusRelationIsBestPossible

    hdp_04_equation_4_4 · 2 more declarations under this item

  • 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_equation_4_5 · 2 more declarations under this item

  • Equation (4.6)

    Under the approximate-isometry Gram-deviation hypothesis, every vector is distorted by factors between 1 - δ and 1 + δ.

    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 δ

    hdp_04_equation_4_6

  • Equation (4.7)

    Under the approximate-isometry Gram-deviation hypothesis, the smallest and largest singular values lie between 1 - δ and 1 + δ.

    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 δ

    hdp_04_equation_4_7

  • Equation (4.8)

    Printed page 79: for a nonnegative real z, the deviation of z² from one dominates both the linear and squared deviations of z from one.

    Lean statement
    theorem hdp_04_heq_h4_d8 {z : ℝ} (hz : 0 ≤ z) :
        max |z - 1| (|z - 1| ^ 2) ≤ |z ^ 2 - 1|

    hdp_04_heq_h4_d8

  • 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‖

    hdp_04_heq_h4_d9

  • 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 / (ε : ℝ)) ^ n

    hdp_04_equation_4_10 · 1 more declaration under this item

  • Equation (4.11)

    2r+1 copies of a k-letter message use (2r+1)k letters.

    Lean statement
    theorem hdp_04_equation_4_11 (r k : ℕ) :
        Fintype.card (Fin (2 * r + 1) × Fin k) = (2 * r + 1) * k

    hdp_04_equation_4_11

  • Equation (4.12)

    The two Euclidean unit spheres admit quarter-nets whose cardinalities are bounded by 9^n and 9^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 ^ m

    hdp_04_equation_4_12

  • Equation (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) y

    hdp_04_equation_4_13

  • Equation (4.14)

    For fixed unit vectors x and y, 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 quotient u² / K²; the source gives no extended-value convention at K = 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))

    hdp_04_equation_4_14

  • Equation (4.15)

    Lean statement
    theorem equation415_owner_qualified_proved : CompleteOwnerQualifiedParent.{u}

    equation415_owner_qualified_proved · 2 more declarations under this item

  • 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)

    hdp_04_equation_4_16

  • 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 2 is 2^(3/2). The premise is precisely the conclusion of Theorem 4.5.5, with d standing 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 / δ

    hdp_04_equation_4_19

  • 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 most C / μ², 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 : ℝ))

    hdp_04_equation_4_20

  • 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_equation_4_21_explicit_svd · 1 more declaration under this item

  • 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 most 2 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))

    hdp_04_equation_4_22

  • Equation (4.23)

    For a fixed vector x, setting Xᵢ=⟨Aᵢ,x⟩ expands the squared Euclidean norm of Ax as ∑ᵢ 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) ^ 2

    hdp_04_equation_4_23

  • Equation (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_equation_4_24_probability_ordinary · 1 more declaration under this item

  • 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 : equation425ConstructedPointwiseTarget

    equation425_constructed_pointwise_proved · 2 more declarations under this item

  • Example 4.3.2

    Over any finite nonempty alphabet, after repeating a message 2r+1 times, coordinatewise majority decoding recovers it from any received word with at most r corrupted 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 = x

    hdp_04_example_4_3_2

  • Remark 4.1.7

    With Q = Aᵀ, Q Qᵀ = I is equivalent to Qᵀ Q being the rank-n orthogonal 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 δ)

    hdp_04_remark_4_1_7

  • 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

    hdp_04_hremark_h4_d2_d7

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 v

    hdp_04_exercise_4_1_1

  • Exercise 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's Fin n index is zero-based, so the denominator is sqrt (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 : ℕ)

    hdp_04_exercise_4_1_2

  • Exercise 4.1.3

    For the best rank-k approximation obtained by truncating an exact rank-k+q SVD, 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)) ^ 2

    hdp_04_exercise_4_1_3

  • Exercise 4.1.4

    The right Gram identity, the rank-N orthogonal-projection property of the left Gram matrix, Euclidean norm preservation, and equality of every singular value to one are equivalent. The source assumes m ≥ N > 0. Here N = n + 1 remains positive, while the equivalence also covers wide and rank-deficient matrices: the singular value family has all N entries of the ordered right-Gram spectrum, with zeros retained, including the extra zeros when m < 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))

    hdp_04_exercise_4_1_4

  • 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)

    hdp_04_exercise_4_1_6

  • 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)

    hdp_04_exercise_4_1_8

  • Exercise 4.2.9

    Lean statement
    theorem exercise429NumericalTarget_proved : exercise429NumericalTarget

    exercise429NumericalTarget_proved · 2 more declarations under this item

  • 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)

    hdp_04_exercise_4_2_10

  • 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}

    hdp_04_hexercise_h4_d2_d15

  • 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 : ℕ∞)

    hdp_04_exercise_4_2_16

  • Exercise 4.3.7

    Exercise 4.3.7 (Optimality). For every code correcting r errors, its codebook is bounded by the 2r-packing number, its radius-r Hamming balls satisfy the sphere-packing count, and (when 0 < r ≤ n) its rate satisfies the literal bound from the exercise R ≤ 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)

    hdp_04_exercise_4_3_7_converse

  • Exercise 4.4.2

    The supremum of the inner products of x with any set-valued ε-net of the Euclidean unit sphere approximates ‖x‖₂ within the factor (1 - ε)⁻¹. The surrounding Lemma 4.4.1 allows 0 ≤ ε < 1; here only ε < 1 is 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}

    hdp_04_exercise_4_4_2

  • 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_exercise_4_4_3 · 1 more declaration under this item

  • 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_exercise_4_4_4 · 2 more declarations under this item

  • 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) / 4 once 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 ω) ∂μ

    hdp_04_exercise_4_4_7

  • 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)

    hdp_04_exercise_4_5_4

  • 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 : ℝ))

    hdp_04_exercise_4_6_2

  • 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_exercise_4_6_4 · 1 more declaration under this item

  • Exercise 4.7.3

    The covariance-estimation error obeys the stated n+u high-probability bound. As in Theorem 4.7.1, the contract uses the proof's whitened representation Xᵢ = B Zᵢ, allowing singular B.

    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)

    hdp_04_exercise_4_7_3