Gaussian, Sub-Gaussian, and Hoeffding Bounds

SECTION 01Gaussian Tail Bounds and Sub-Gaussian Variables

The Chernoff bound depends on the growth rate of the moment generating function. It is therefore natural to classify random variables by their MGF behavior. Information about a particular class gives us more control over its MGF and can lead to more specific, potentially tighter tail bounds.

We first consider Gaussian-like random variables. We proceed in four steps: (1) start with a familiar Gaussian variable, whose MGF can be computed explicitly; (2) observe that the tail-bound derivation depends on the MGF’s growth, rather than on the variable being Gaussian; (3) introduce sub-Gaussian variables, whose centered MGFs are bounded by the same Gaussian form. Sub-Gaussian variables satisfy the same form of Chernoff bound as Gaussian variables. (4) show that many commonly used types of random variables are sub-Gaussian.

Gaussian Tail Bounds

Setting

Let X ∼ N(μ, σ²), with σ > 0. Its moment generating function is

E [e^{λ X}] = e^{μ λ + \frac{σ^{2} λ^{2}}{2}}, λ \in R

Formulation · Gaussian Tail Bound

Substituting the Gaussian MGF into the Chernoff bound gives

inf_{λ \geq 0} {\log E [e^{λ (X - μ)}] - λ t} = inf_{λ \geq 0} {\frac{σ^{2} λ^{2}}{2} - λ t} = - \frac{t^{2}}{2 σ^{2}}

Therefore, any N(μ, σ²) random variable satisfies the upper-deviation bound

P (X \geq μ + t) \leq e^{- \frac{t^{2}}{2 σ^{2}}}, t \geq 0

The Chernoff bound is not sharp for a Gaussian variable: at t = 0, the true tail probability is 1/2, while the bound is 1. To compare them far from the mean, we use the following approximation for large t/σ:

P (X \geq μ + t) \sim \frac{σ}{t \sqrt{2 π}} e^{- \frac{t^{2}}{2 σ^{2}}}, \frac{t}{σ} \to \infty

The expression on the right approximates the true tail probability on the left. Compared with this approximation, the Chernoff bound captures the correct exponential decay but omits the multiplier σ/(t√(2π)).

Its advantage is simplicity and broad applicability: the same argument extends to all sub-Gaussian variables using only a bound on the centered MGF, without knowing the exact distribution. This makes it useful for concentration guarantees. For Gaussian variables, however, it can substantially overestimate the true tail probability, so it is less suitable for precise Gaussian probability estimates. For other sub-Gaussian variables, its tightness depends on the distribution.

SECTION 02Sub-Gaussian Variables

The calculation above relies on the Gaussian form of the centered MGF. This motivates a broader class of random variables with the same MGF bound.

Definition · Sub-Gaussian Variable

A random variable X with mean μ = E[X] is sub-Gaussian if there is a σ > 0 such that

E [e^{λ (X - μ)}] \leq e^{\frac{σ^{2} λ^{2}}{2}}, λ \in R

The constant σ is called a sub-Gaussian parameter.

Formulation · Sub-Gaussian Concentration Bound

Applying the Chernoff argument gives the one-sided bound

P (X - μ \geq t) \leq e^{- \frac{t^{2}}{2 σ^{2}}}, t \geq 0

Combining the right and left tails gives the two-sided concentration bound

P (| X - μ | \geq t) \leq 2 e^{- \frac{t^{2}}{2 σ^{2}}}, t \geq 0

SECTION 03Sub-Gaussian Examples

Claim 1 · A Rademacher Variable Is Sub-Gaussian

A Rademacher random variable ε takes −1 and +1 with equal probability. It is sub-Gaussian with parameter σ = 1.

Proof of Claim 1

Expanding the two exponentials cancels all odd powers:

E [e^{λ ε}] = \frac{e^{- λ} + e^{λ}}{2} = \sum_{k = 0}^{\infty} \frac{λ^{2 k}}{(2 k)!}

Since (2k)! ≥ 2ᵏk!,

\sum_{k = 0}^{\infty} \frac{λ^{2 k}}{(2 k)!} \leq 1 + \sum_{k = 1}^{\infty} \frac{λ^{2 k}}{2^{k} k!} = e^{\frac{λ^{2}}{2}}

Claim 2 · A Bounded Variable Is Sub-Gaussian

Let X have mean zero and take values in [a, b]. Then X is sub-Gaussian with parameter σ = b − a.

Proof of Claim 2

Let X′ be an independent copy of X. For any λ ∈ ℝ,

E_{X} [e^{λ X}] = E_{X} [e^{λ (X - E_{X'} [X'])}] \leq E_{X, X'} [e^{λ (X - X')}]

Let ε be an independent Rademacher variable. Since X − X′ has a symmetric distribution, it has the same distribution as ε(X − X′). Apply Claim 1 with X and X′ fixed:

E_{X, X'} [e^{λ (X - X')}] = E_{X, X'} [E_{ε} [e^{λ ε (X - X')}]] \leq E_{X, X'} [e^{\frac{λ^{2} {(X - X')}^{2}}{2}}]

Since |X − X′| ≤ b − a,

E_{X, X'} [e^{\frac{λ^{2} {(X - X')}^{2}}{2}}] \leq e^{\frac{λ^{2} {(b - a)}^{2}}{2}}

Thus X is sub-Gaussian with parameter at most b − a.

SECTION 04Hoeffding Bounds

Claim · Independent Sums Remain Sub-Gaussian

Just as Gaussianity is preserved by linear operations, so is sub-Gaussianity. In particular, independent sums have the following property. If X₁ and X₂ are independent sub-Gaussian variables with parameters σ₁ and σ₂, then X₁ + X₂ is sub-Gaussian with parameter

\sqrt{{σ_{1}}^{2} + {σ_{2}}^{2}}

Formulation · Hoeffding Bound for Independent Sub-Gaussian Variables

Suppose X₁, …, Xₙ are independent, with means μᵢ and sub-Gaussian parameters σᵢ. Combining the independent-sum property with the sub-Gaussian tail bound gives

P (\sum_{i = 1}^{n} (X_{i} - μ_{i}) \geq t) \leq e^{- \frac{t^{2}}{2 \sum_{i = 1}^{n} {σ_{i}}^{2}}}, t \geq 0

Formulation · Hoeffding Bound for Bounded Variables

The Hoeffding bound is often stated only for bounded random variables. If the independent variables Xᵢ all take values in [a, b], then

P (\sum_{i = 1}^{n} (X_{i} - μ_{i}) \geq t) \leq e^{- \frac{2 t^{2}}{n {(b - a)}^{2}}}, t \geq 0