TheoremStatement: AI-adaptedProof: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Finite sub-Gaussian maxima and epsilon-net reduction

Statement

Let $Y_{1}, \dots, Y_{m}$ be centered sub-Gaussian real random variables with a common proxy $σ^{2} \geq 0$ , where $m \geq 1$ . No independence is assumed. For $t > 0$ , if $σ^{2} > 0$ then $P (\max_{1 \leq j \leq m} ∣ Y_{j} ∣ \geq t) \leq 2 m \exp ⁣ (- \frac{t^{2}}{2 σ^{2}}),$ and if $σ^{2} = 0$ the probability is $0$ .

Let $Z$ be a centered sub-Gaussian vector in $R^{d}$ with proxy $σ^{2}$ , where $d \geq 1$ . For $0 < ϵ < 1$ , let $N$ be the sphere net supplied by Finite epsilon nets of the Euclidean sphere. Then for $t > 0$ , if $σ^{2} > 0$ , $P (∥ Z ∥_{2} \geq t) \leq 2 (1 + 2 / ϵ)^{d} \exp ⁣ (- \frac{(1 - ϵ)^{2} t^{2}}{2 σ^{2}}),$ and if $σ^{2} = 0$ this probability is $0$ . The deterministic reduction is $∥ z ∥_{2} \leq (1 - ϵ)^{- 1} \max_{u \in N} ∣ ⟨ u, z ⟩ ∣$ for every $z \in R^{d}$ .

Facts & Assumptions

Given: Centered scalar or vector random elements satisfying the sub-Gaussian proxy bounds; a finite integer $m \geq 1$ ; and, in the vector clause, $d \geq 1$ and $0 < ϵ < 1$ .

[F1]

A centered scalar $X$ is sub-Gaussian with proxy $σ^{2}$ when $E e^{λ X} \leq e^{λ^{2} σ^{2} / 2}$ for every real $λ$ ; the vector condition bounds each projection (Sub-Gaussian variables and vectors, and sub-exponential variables).

[F2]

For $W \geq 0$ and $r > 0$ , Markov gives $P (W \geq r) \leq E [W] / r$ (Markov's inequality for random variables).

[F3]

Finite unions satisfy $P (⋃_{j} A_{j}) \leq \sum_{j} P (A_{j})$ (Basic identities for a probability measure).

[F4]

For $d \geq 1$ and $0 < ϵ < 1$ , there is a finite $ϵ$ -net $N \subseteq S^{d - 1}$ with $∣ N ∣ \leq (1 + 2 / ϵ)^{d}$ (Finite epsilon nets of the Euclidean sphere).

[F5]

$S^{d - 1} = {u \in R^{d} : ∥ u ∥_{2} = 1}$ and $∥ \cdot ∥_{2}$ is the Euclidean norm (Euclidean spheres and closed balls as subspaces of $R^{n}$ ).

[F6]

The Euclidean inner product satisfies $∣ ⟨ u, z ⟩ ∣ \leq ∥ u ∥_{2} ∥ z ∥_{2}$ (The Cauchy-Schwarz inequality for finite sums).

[F7]

Every nonempty finite set of real numbers has a maximum (Every nonempty finite set of reals has a maximum and a minimum, Maximum and minimum of a set).

[F8]

The exponential is continuous and strictly increasing, positive, and satisfies $e^{- x} = 1 / e^{x}$ and $e^{x + y} = e^{x} e^{y}$ (The exponential function is strictly increasing, The exponential is positive and satisfies $\exp (- x) = 1 / \exp (x)$ , The exponential addition formula $\exp (x + y) = \exp (x) \exp (y)$ ).

[F9]

For every $a > 0$ and natural $m$ , $x^{m} / e^{a x} \to 0$ as $x \to + \infty$ ; use $m = 0$ to get $1 / e^{a x} \to 0$ (The exponential dominates every fixed nonnegative integer power at $+ \infty$ ).

Proof

1.1F1F2F8F9algebraconstruct

For each $λ > 0$ , $h_{λ} (x) = e^{λ x}$ is continuous by [F8] and continuity of scalar multiplication, hence Borel: the Borel sets with Borel preimage form a sigma-algebra containing all opens, so contain the sigma-algebra generated by opens (The Borel sigma-algebra of a topological space). For each Borel $B$ , ${h_{λ} (Y_{j}) \in B} = Y_{j}^{- 1} (h_{λ}^{- 1} (B))$ is measurable, and $h_{λ} (Y_{j}) \geq 0$ by [F8]. If $σ^{2} > 0$ , then $Y_{j} \geq t$ implies $e^{λ Y_{j}} \geq e^{λ t} > 0$ by [F8]; Markov [F2], the MGF bound [F1], and the reciprocal and addition formulas in [F8] give $P (Y_{j} \geq t) \leq \exp (- λ t + λ^{2} σ^{2} / 2)$ . Choosing $λ = t / σ^{2}$ gives $P (Y_{j} \geq t) \leq e^{- t^{2} / (2 σ^{2})}$ ; Using parameter $- λ$ , $Y_{j} \leq - t$ implies $e^{- λ Y_{j}} \geq e^{λ t} > 0$ ; the same Markov calculation gives $P (Y_{j} \leq - t) \leq \exp (- λ t + λ^{2} σ^{2} / 2)$ , and $λ = t / σ^{2}$ gives the same lower-tail bound. If $σ^{2} = 0$ , Markov gives $P (Y_{j} \geq t) \leq 1 / e^{λ t} = e^{- λ t}$ for every $λ > 0$ . By [F9] with $m = 0$ and $a = t$ , the right side tends to $0$ as $λ \to \infty$ , so the tail is zero, and at parameter $- λ$ the same calculation gives $P (Y_{j} \leq - t) \leq e^{- λ t} \to 0$ .

1.2givenF4F5F6algebra

Fix $z \neq 0$ and put $u = z / ∥ z ∥_{2} \in S^{d - 1}$ by [F5]. By [F4], some $v \in N$ satisfies $∥ u - v ∥_{2} \leq ϵ$ . Then [F6] gives $∣ ⟨ v, z ⟩ ∣ \geq ⟨ u, z ⟩ - ∣ ⟨ u - v, z ⟩ ∣ \geq (1 - ϵ) ∥ z ∥_{2}$ . For $z = 0$ the claimed reduction is immediate. Thus the deterministic net inequality holds.

2.1F3F7step 1.1

By the finite maximum convention in [F7], the event ${\max_{j} ∣ Y_{j} ∣ \geq t}$ is the union of the $2 m$ upper- and lower-tail events from step 1.1. Applying [F3] gives the stated finite-maximum bounds, without any independence assumption.

3.1F1F4step 2.1step 1.2algebra∎

Apply step 1.2 to $Z$ . If $∥ Z ∥_{2} \geq t$ , then at least one of the $∣ N ∣$ projections has absolute value at least $(1 - ϵ) t$ . Each projection is centered sub-Gaussian with proxy $σ^{2}$ by [F1] because its direction is a unit vector. Step 2.1 and [F4] therefore give the displayed vector tail bound; when $σ^{2} = 0$ , step 2.1 gives probability zero.

Depends on

Used by

Finite variance does not imply a sub-Gaussian tail Counterexample
A Gaussian maximum without independence Example
A sub-Gaussian vector norm bound Example
Products of sub-Gaussian coordinates are sub-exponential Lemma
Sub-Gaussian score bound under fixed-design incoherence Lemma
Dense sample covariance concentration for sub-Gaussian vectors Theorem
Entrywise deviation for sample-centered covariance under directional Gaussian tails Theorem
Sub-Gaussian projection risk bounds Theorem

Dependency tree · two levels

71 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Philippe Rigollet and Jan-Christian Hütter, High-Dimensional Statistics: Lecture Notes, Chapter 1, Theorems 1.14 and 1.19 (standard reference, not scraped)
John Duchi, Lecture Notes on Statistics and Information Theory, Chapter 4, §4.1.1 (standard reference, not scraped)