Sub-Exponential Sample Means and Bernstein Regimes

Why Two Deviation Regimes Appear

A sample mean can concentrate sharply near its expectation even when its observations do not have bounded support. The shape of its tail matters: for moderate deviations, the probability often falls at a rate resembling a Gaussian tail, while for sufficiently large deviations it falls exponentially in the deviation size. This change of behavior is captured by sub-exponential moment-generating-function control.

The key distinction from a purely quadratic bound is that the moment-generating-function control is guaranteed only over a finite range of tilting parameters. Applying the Chernoff method within that range produces a bound with a quadratic term in its denominator. That denominator is what yields the two regimes.

Definition and Main Bound

Definition: A random variable $X$ is sub-exponential with parameters $(\nu^2,b)$, where $\nu^2>0$ and $b>0$, if $E[X]$ exists and, for $Z=X-E[X]$, $$ E[\exp(\lambda Z)]\leq \exp\left(\frac{\nu^2\lambda^2}{2(1-b|\lambda|)}\right) \quad\text{for every }|\lambda|<1/b. $$ The variable $Z$ is centered. The parameter $\nu^2$ controls the quadratic part of the bound, and $b$ controls the range of moment-generating-function parameters and the eventual linear regime.

This is a Bernstein-form definition: it specifies a particular moment-generating-function envelope, not a claim that every distribution has the same tail at every deviation size. Smaller admissible values of $\nu^2$ and $b$ give sharper guarantees. The following result shows how the parameters act for a sample mean.

Theorem: Let $X_1,\ldots,X_n$ be independent, identically distributed sub-exponential random variables with parameters $(\nu^2,b)$, and let $\bar X=n^{-1}\sum_{i=1}^n X_i$. For every $t>0$, $$ P\left(|\bar X-E[X_1]|\geq t\right) \leq 2\exp\left(-\frac{nt^2}{2(\nu^2+bt)}\right) \leq 2\exp\left[-\frac{n}{4}\min\left(\frac{t^2}{\nu^2},\frac{t}{b}\right)\right]. $$ The first bound displays the transition directly. Its denominator is dominated by $\nu^2$ when $t$ is small relative to $\nu^2/b$, and by $bt$ when $t$ is large relative to that scale.

Proof. Put $Z_i=X_i-E[X_i]$ and $S_n=\sum_{i=1}^n Z_i$. Independence and the defining moment-generating-function bound give, for $0<\lambda<1/b$, $$ E[\exp(\lambda S_n)] =\prod_{i=1}^n E[\exp(\lambda Z_i)] \leq \exp\left(\frac{n\nu^2\lambda^2}{2(1-b\lambda)}\right). $$ By Markov's inequality, for any such $\lambda$, $$ P(S_n\geq nt) \leq \exp\left(-n\lambda t+\frac{n\nu^2\lambda^2}{2(1-b\lambda)}\right). $$ Choose $\lambda=t/(\nu^2+bt)$. This is positive and strictly less than $1/b$, because $bt<\nu^2+bt$. Also $1-b\lambda=\nu^2/(\nu^2+bt)$. Substitution gives $$ -n\lambda t+\frac{n\nu^2\lambda^2}{2(1-b\lambda)} =-\frac{nt^2}{\nu^2+bt}+\frac{nt^2}{2(\nu^2+bt)} =-\frac{nt^2}{2(\nu^2+bt)}. $$ Thus the asserted bound holds for the upper tail. Apply the same argument to $-Z_i$, which satisfies the same moment-generating-function bound by the absolute value in its definition, to obtain the lower-tail bound. Adding the two probabilities proves the first inequality.

For the second inequality, write $a=t^2/\nu^2$ and $c=t/b$. If $t\leq\nu^2/b$, then $a\leq c$ and $\nu^2+bt\leq2\nu^2$, so $t^2/[2(\nu^2+bt)]\geq a/4$. If $t\geq\nu^2/b$, then $c\leq a$ and $\nu^2+bt\leq2bt$, so $t^2/[2(\nu^2+bt)]\geq c/4$. In either case the exponent is at least $\frac14\min(a,c)$, as required. $\square$

Reading the Bernstein Regimes

The exact bound is governed by the denominator $\nu^2+bt$. The two simpler regimes follow by considering which term is larger. When $0<t\leq\nu^2/b$, the quadratic term dominates up to a factor of two: $$ P\left(|\bar X-E[X_1]|\geq t\right) \leq 2\exp\left(-\frac{nt^2}{4\nu^2}\right). $$ When $t\geq\nu^2/b$, the linear term dominates up to a factor of two: $$ P\left(|\bar X-E[X_1]|\geq t\right) \leq 2\exp\left(-\frac{nt}{4b}\right). $$

These are convenient regime-wise simplifications of the theorem, not separate assumptions. At fixed $t$ in the small-deviation regime, the exponent grows proportionally to $n t^2$. In the large-deviation regime it grows proportionally to $n t$. The crossover $t=\nu^2/b$ is where the two denominator terms are equal; it is not a boundary at which the probability suddenly changes form.

Worked Example: Centered Exponential Observations

Let $X$ have an exponential distribution with rate $1$, so its density is $f(x)=e^{-x}$ for $x\geq0$, and $E[X]=1$. Verify sub-exponential parameters and calculate a sample-mean bound for $n=25$.

For $\lambda<1$, $$ E[\exp(\lambda(X-1))]=\frac{e^{-\lambda}}{1-\lambda}, \qquad \log E[\exp(\lambda(X-1))]=-\lambda-\log(1-\lambda). $$ For $|\lambda|<1$, expansion of the logarithm gives $$ -\lambda-\log(1-\lambda) =\sum_{k=2}^{\infty}\frac{\lambda^k}{k} \leq\sum_{k=2}^{\infty}\frac{|\lambda|^k}{k} \leq\frac12\sum_{k=2}^{\infty}|\lambda|^k =\frac{\lambda^2}{2(1-|\lambda|)}. $$ The series converges absolutely on this range, and $1/k\leq1/2$ for $k\geq2$. Therefore $X$ satisfies the definition with $\nu^2=1$ and $b=1$.

For $n=25$, the sample mean $\bar X$ has expectation $1$. At $t=1$, the exact bound gives $$ P(|\bar X-1|\geq1) \leq2\exp\left(-\frac{25}{2(1+1)}\right) =2e^{-6.25} \approx0.00386. $$ At the smaller deviation $t=0.5$, it gives $$ P(|\bar X-1|\geq0.5) \leq2\exp\left(-\frac{25(0.5)^2}{2(1+0.5)}\right) =2e^{-25/12} \approx0.2494. $$ Here the crossover is $t=\nu^2/b=1$. These calculations use the same bound; the smaller deviation has a smaller exponent because its quadratic contribution is smaller.

Worked Example: A Gaussian Distribution Also Fits the Bound

Suppose $X\sim N(\mu,4)$, so its variance is $4$. Its centered moment-generating function is $$ E[\exp(\lambda(X-\mu))]=\exp(2\lambda^2). $$ For $|\lambda|<1$, $1/(1-|\lambda|)\geq1$, so $$ \exp(2\lambda^2) \leq \exp\left(\frac{4\lambda^2}{2(1-|\lambda|)}\right). $$ Thus the sub-exponential definition holds with $\nu^2=4$ and $b=1$. The parameter choice is valid though not the only possible one.

For $n=16$ independent observations and $t=2$, the sample-mean bound is $$ P(|\bar X-\mu|\geq2) \leq2\exp\left(-\frac{16(2)^2}{2(4+2)}\right) =2e^{-16/3} \approx0.00967. $$ This bound is conservative: it follows from the stated sub-exponential parameters and does not use a sharper, distribution-specific Gaussian tail calculation.

Independent Observations with Different Parameters

Identical distributions are not essential. Suppose $X_1,\ldots,X_n$ are independent and $X_i-E[X_i]$ satisfies the definition with parameters $(\nu_i^2,b_i)$. Define $V=\sum_{i=1}^n\nu_i^2$, $B=\max_i b_i$, and $\bar X=n^{-1}\sum_iX_i$. For $0<\lambda<1/B$, each $1-b_i\lambda\geq1-B\lambda$. Consequently, multiplying the individual moment-generating-function bounds yields $$ E\left[\exp\left(\lambda\sum_{i=1}^n(X_i-E[X_i])\right)\right] \leq \exp\left(\frac{V\lambda^2}{2(1-B\lambda)}\right). $$

Apply Markov's inequality and choose $\lambda=nt/(V+Bnt)$, which is positive and less than $1/B$. The same substitution as in the theorem gives $$ P\left(|\bar X-E[\bar X]|\geq t\right) \leq2\exp\left(-\frac{n^2t^2}{2(V+Bnt)}\right). $$ Here $E[\bar X]=n^{-1}\sum_iE[X_i]$. Independence is needed to multiply the moment-generating functions; identical distributions are not.

Worked Example: A Conservative Confidence Threshold

Return to the rate-$1$ exponential observations, with $n=25$, $\nu^2=1$, and $b=1$. Find a deviation threshold $t$ for which the two-sided probability bound is at most $0.05$.

Let $L=\log(2/0.05)=\log(40)\approx3.688879$. It is sufficient that $$ \frac{25t^2}{2(1+t)}\geq L. $$ Solving the corresponding equality gives the positive root $$ t_*=\frac{L+\sqrt{L^2+50L}}{25}. $$ The expression $t_*$ is the exact threshold from this bound. For a convenient conservative decimal threshold, take $t=0.711$. Indeed, $$ \frac{25(0.711)^2}{2(1+0.711)} =\frac{12.638025}{3.422} >3.688879=L. $$ It follows that $$ P(|\bar X-1|\geq0.711) \leq2\exp\left(-\frac{25(0.711)^2}{2(1+0.711)}\right) <0.05. $$ The displayed decimal is rounded upward relative to the equality threshold, so it preserves the guarantee.

Common Pitfall and Practical Meaning

A common mistake is to treat the quadratic regime as valid for every $t$, producing a Gaussian-shaped bound even for arbitrarily large deviations. The defining moment-generating-function control is restricted to $|\lambda|<1/b$; the Chernoff optimization must respect that restriction. The resulting denominator $\nu^2+bt$ records the limitation, and for large $t$ it leads to an exponent proportional to $t/b$, not $t^2/\nu^2$.

A second practical point is that the theorem is a guarantee, not an estimate of the actual tail probability. It can be loose, as the Gaussian example illustrates. Its value is that it applies from verified moment-generating-function control without requiring bounded observations, and it makes explicit how the sample size, deviation, and tail parameters affect the guarantee.

Key takeaway: Under the Bernstein-form sub-exponential condition, independent sample means have a quadratic small-deviation exponent and a linear large-deviation exponent. The crossover scale is $\nu^2/b$, and the exact bound $2\exp\{-nt^2/[2(\nu^2+bt)]\}$ keeps both behaviors in one expression.

Check Your Understanding

Use the definition and bounds above to answer the following questions.

For a variable with parameters $(\nu^2,b)$, at what deviation scale are the two denominator terms $\nu^2$ and $bt$ equal?
Why does independence allow the moment-generating-function bounds for the observations to be multiplied?
For fixed $n$, which term controls the denominator when $t$ is much larger than $\nu^2/b$, and what does that imply for the exponent?
In the exponential example, verify why $1/k\leq1/2$ gives the stated logarithmic moment-generating-function bound.
Why is rounding a confidence threshold downward potentially unsafe when the threshold is obtained by solving a tail-bound equality?