Empirical Mean Bounds With a Known Variance Upper Bound

Why Use a Known Variance Bound?

Hoeffding’s inequality controls deviations using only the range of each observation. Bernstein’s inequality can give a sharper bound when the observations have a small variance as well. This tutorial develops that improvement for an empirical mean when the observations are bounded and an upper bound on their variance is available in advance.

The two assumptions play different roles. Boundedness limits the size of any single centered observation, while the variance upper bound controls the typical squared size of the fluctuations. Both enter the tail bound; knowing only the variance is not enough for the version of Bernstein’s inequality proved here.

Setup: Let $X_1,\ldots,X_n$ be independent and identically distributed random variables with $E[X_i]=\mu$. Assume that, for a known constant $c>0$, $P(|X_i-\mu|\le c)=1$, and that $\operatorname{Var}(X_i)\le \nu$ for a known $\nu\ge 0$. The empirical mean is $\bar X_n=n^{-1}\sum_{i=1}^n X_i$.

A simple way to ensure the boundedness assumption is to know that each observation lies in a fixed interval $[a,b]$. Then $\mu\in[a,b]$. If $a<b$, $|X_i-\mu|\le b-a$ almost surely and one may take $c=b-a$. If $a=b$, then $X_i=\mu=a$ almost surely and the deviation probability is zero; alternatively, any $c>0$ satisfies the setup. The interval width is a safe bound; it need not be the smallest possible bound on the centered observations.

Bernstein’s Bound for the Empirical Mean

Theorem (two-sided Bernstein bound): Under the setup above, for every $\varepsilon>0$, $$ P\bigl(|\bar X_n-\mu|\ge \varepsilon\bigr) \le 2\exp\!\left(-\frac{n\varepsilon^2}{2(\nu+c\varepsilon/3)}\right). $$ In particular, each one-sided deviation has probability at most $\exp\!\left(-n\varepsilon^2/[2(\nu+c\varepsilon/3)]\right)$.

The proof rests on a moment-generating-function bound for a centered, bounded variable. We give the details, including the inequality that produces the constant $1/3$.

Lemma: If $Y$ is a random variable with $E[Y]=0$, $|Y|\le c$ almost surely, and $E[Y^2]\le \nu$, then for $0<\lambda<3/c$, $$ E[e^{\lambda Y}] \le \exp\!\left(\frac{\lambda^2\nu}{2(1-\lambda c/3)}\right). $$

Proof. Since $|Y|\le c$, the exponential series for $e^{\lambda Y}$ is absolutely bounded by $e^{\lambda c}$. Thus its terms can be integrated term by term. The linear term vanishes because $E[Y]=0$. For each integer $k\ge2$, the bounds $|Y|^k\le c^{k-2}Y^2$ and $k!\ge 2\cdot 3^{k-2}$ give

\begin{aligned} E[e^{\lambda Y}] &=1+\sum_{k=2}^{\infty}\frac{\lambda^k E[Y^k]}{k!}\\ &\le 1+\sum_{k=2}^{\infty}\frac{\lambda^k E[|Y|^k]}{k!}\\ &\le 1+\frac{\lambda^2 E[Y^2]}{2} \sum_{k=2}^{\infty}\left(\frac{\lambda c}{3}\right)^{k-2}\\ &\le 1+\frac{\lambda^2\nu}{2(1-\lambda c/3)}\\ &\le \exp\!\left(\frac{\lambda^2\nu}{2(1-\lambda c/3)}\right). \end{aligned}

The geometric series converges because $\lambda c/3<1$; the last inequality uses $1+u\le e^u$ for $u\ge0$. This proves the lemma. $\square$

To prove the theorem, set $Y_i=X_i-\mu$ and $S_n=\sum_{i=1}^nY_i$. Independence and the lemma imply, for $0<\lambda<3/c$,

E[e^{\lambda S_n}] =\prod_{i=1}^n E[e^{\lambda Y_i}] \le \exp\!\left(\frac{n\lambda^2\nu}{2(1-\lambda c/3)}\right).

For $x>0$, Markov’s inequality applied to $e^{\lambda S_n}$ gives

P(S_n\ge x) \le \exp\!\left(-\lambda x+\frac{n\lambda^2\nu}{2(1-\lambda c/3)}\right).

When $\nu>0$, choose $\lambda=x/(n\nu+cx/3)$. This is positive and less than $3/c$, since $n\nu>0$. Substitution gives

P(S_n\ge x) \le \exp\!\left(-\frac{x^2}{2(n\nu+cx/3)}\right).

Apply the same argument to $-Y_i$, which has the same bound on its absolute value and variance, to bound $P(S_n\le -x)$. Adding the two one-sided bounds and taking $x=n\varepsilon$ proves the stated inequality. If $\nu=0$, then $E[Y_i^2]=0$, so $Y_i=0$ almost surely and the deviation probability is zero. The theorem holds in this case too. $\square$

Turning the Tail Bound Into a Confidence Radius

The theorem can be inverted to give a radius that guarantees a chosen error probability. Let $0<\delta<1$ and define $L=\log(2/\delta)$. Then

Corollary (explicit radius): Under the theorem’s assumptions, $$ P\!\left( |\bar X_n-\mu| \ge \sqrt{\frac{2\nu L}{n}}+\frac{2cL}{3n} \right)\le \delta. $$

Proof. Write $r=\sqrt{2n\nu L}+(2/3)cL$, the corresponding threshold for the sum $S_n$. It satisfies $r^2\ge 2L(n\nu+cr/3)$: expanding both sides, the terms involving $n\nu$ agree, and the remaining difference is nonnegative. Therefore $r^2/[2(n\nu+cr/3)]\ge L$. The two-sided Bernstein bound at $\varepsilon=r/n$ is at most $2e^{-L}=\delta$. $\square$

The radius has two contributions. The square-root term reflects the variance bound, while the term proportional to $c/n$ accounts for the finite maximum size of a centered observation. At moderate sample sizes and small variance, the first term can be much smaller than a range-only bound.

Worked Applications

Worked Example: A Small Variance Bound for Bounded Measurements

Suppose $n=100$ independent measurements have common mean $\mu$, each centered measurement satisfies $|X_i-\mu|\le1$, and the known variance bound is $\operatorname{Var}(X_i)\le0.05$. Bound the probability that the empirical mean differs from $\mu$ by at least $0.05$.

Here $c=1$, $\nu=0.05$, and $\varepsilon=0.05$. The exponent in the two-sided bound is

\frac{n\varepsilon^2}{2(\nu+c\varepsilon/3)} = \frac{100(0.05)^2}{2(0.05+0.05/3)} = \frac{0.25}{2(1/15)} = 1.875.

Consequently,

P(|\bar X_{100}-\mu|\ge0.05) \le 2e^{-1.875}\approx 0.3067.

This is an upper bound, not an estimate of the actual probability. It is fairly loose here, but the calculation illustrates how to use a variance upper bound together with the centered bound.

Worked Example: A 95% Error Radius

Assume $n=200$, $|X_i-\mu|\le1$ almost surely, and $\operatorname{Var}(X_i)\le0.04$. Find a radius that the corollary guarantees will cover the empirical-mean error with probability at least $0.95$.

For $\delta=0.05$, $L=\log(2/0.05)=\log 40\approx3.6889$. The variance contribution to the radius is

\sqrt{\frac{2(0.04)(3.6889)}{200}} = \sqrt{0.0014756} \approx0.0384.

The boundedness contribution is

\frac{2(1)(3.6889)}{3(200)} \approx0.0123.

Adding the contributions gives a radius of approximately $0.0384+0.0123=0.0507$. Thus

P\!\left(|\bar X_{200}-\mu|<\sqrt{\frac{2(0.04)\log(40)}{200}}+\frac{2\log(40)}{3\cdot200}\right)\ge0.95,

The exact radius is approximately $0.050709$. The result is a guarantee under the stated assumptions; it does not assert that $0.0507$ is the smallest possible radius.

Worked Example: Bernoulli Observations With a Known Variance Bound

Let $X_1,\ldots,X_{1000}$ be independent Bernoulli observations with success probability $p$, where it is known that $p\le0.1$. Bound the probability that the observed success proportion differs from $p$ by at least $0.05$.

A Bernoulli variable takes values 0 and 1, so $|X_i-p|\le1$ and we can use $c=1$. Its variance is $p(1-p)$. Since $p\le0.1$, we have $p(1-p)\le p\le0.1$; more sharply, the function $p(1-p)$ is increasing on $[0,0.1]$, so $p(1-p)\le0.1(0.9)=0.09$. Thus $\nu=0.09$ is a valid known upper bound. The empirical mean is the sample success proportion, and the exponent is

\frac{1000(0.05)^2}{2(0.09+0.05/3)} = \frac{2.5}{2(0.1066667)} = 11.71875.

Therefore,

P(|\bar X_{1000}-p|\ge0.05) \le2e^{-11.71875} \approx1.63\times10^{-5}.

The improvement over using the generic Bernoulli variance bound $1/4$ comes from the additional information $p\le0.1$. The boundedness constant remains 1; the variance input is what has improved.

Common Mistake and Practical Interpretation

A common mistake is to treat a variance bound as though it alone justified Bernstein’s inequality. The centered MGF proof uses $|X_i-\mu|\le c$ to control every higher-order term in the exponential series. A distribution can have finite variance while still having unbounded observations, so a known variance bound without an appropriate tail or boundedness assumption does not imply this Bernstein bound.

Another important distinction is between a known variance upper bound and the sample variance. The theorem assumes a deterministic value $\nu$ for which $\operatorname{Var}(X_i)\le\nu$ is guaranteed. Replacing $\nu$ with the observed sample variance does not follow from the proof: the sample variance is random, and an additional result would be needed to justify a bound based on it.

For independent observations that are not identically distributed, the same MGF argument still applies if each centered observation is bounded in absolute value by $c$, and the sum of their variances has a known upper bound $V$. The resulting sum bound has exponent $x^2/[2(V+cx/3)]$. For an empirical average, the center is then the average of the individual expectations, not necessarily one common mean.

Key takeaway: For bounded independent observations, Bernstein’s inequality combines a known variance upper bound with a maximum centered size. For the empirical mean, this yields an exponential tail with a variance-sensitive term and a correction for boundedness.

Check Your Understanding

Use the assumptions and results above to answer these questions.

If $X_i\in[2,5]$ almost surely, what safe value of $c$ can be used in the centered bound $|X_i-\mu|\le c$? Explain.
For $n$ iid observations with variance at most $\nu$ and centered bound $c$, write the one-sided Bernstein bound for $P(\bar X_n-\mu\ge\varepsilon)$.
Why does the MGF proof require more than a finite variance?
If a Bernoulli success probability is known to be at most $0.2$, what variance upper bound follows from $p(1-p)$?
In the explicit confidence radius, identify which term depends on the variance bound and which term depends on the centered-observation bound.