# Why does "Hoeffding's bound greatly overestimates the probability of large deviations for distributions of small variance"?

I've read in a paper using Hoeffding's inequality to derive a bound on the probability of the difference of means of two samples being larger than a threshold that "Hoeffding's bound greatly overestimates the probability of large deviations for distributions of small variance; in fact, it is equivalent to assuming always the worst-case variance $$\sigma ^{2}=\frac{1}{4}$$" but I'm having a tough time figuring out why it is the case.

Thank you in advance for any help.

• It wouldn't be a bound if the worst-case variance caused the probability to exceed the bound. Apr 13, 2022 at 2:06

I would have said that was true for moderate deviations rather than large deviations. One way to look at it is to compare Hoeffding's inequality, which only uses the upper and lower bounds, with Bernstein's inequality, which uses explicit variances.

Hoeffding's inequality says $$P( |\bar X_n-\mu_n|>t)\leq 2\exp\left(-\frac{2nt^2}{(b-a)^2}\right)$$ Bernstein's inequality says $$P(|\bar X_n-\mu_n|>t)\leq 2\exp\left(-\frac{nt^2}{2\sigma^2+2ct/3} \right)$$ where $$\sigma^2=\frac{1}{n}\sum_{i=1}^n\mathrm{var}[X_i]$$ and $$c$$ is a bound on $$|X|$$. We can reasonably compare these by taking $$2c=(b-a)$$

When $$t$$ is small (so $$\bar X_n$$ is o(\sqrt{n}) standard errors away from its expectation), the second term in the denominator of Bernstein's inequality is small. Bernstein's inequality then has $$nt^2$$ scaled by $$1/(2\sigma^2)$$ and Hoeffding's has it scaled by $$2/(b-a)^2$$. These are the same if $$\sigma^2=(b-a)^2/4$$, which is the largest value it can possibly have for a variable restricted to $$[a,b]$$ -- the value it would have for a binary variable that's equal to each endpoint 50% of the time.

For any other bounded variable (and small $$t$$), you gain by using the actual variance $$\sigma^2$$ rather than the upper bound. For large $$t$$ it's not so simple: the second term in the denominator of Bernstein's inequality dominates, and the bound is much weaker than the Hoeffding one.

You can also see that as $$n\to\infty$$, the Bernstein bound gets relatively close to the Normal tail probability from the Central Limit Theorem. It doesn't reach the Normal tail probability -- it shouldn't, it's an upper bound -- but the normal density $$\phi(t)$$ is larger than the tail probability $$\Phi(t)$$, only by a factor of about $$1/t$$, not an exponential.

(note: there are lots of ways to write these two inequalities, I used the forms from here)

• Thank you for your answer, it helped a lot. So it's better to use Hoeffding's inequality when $t$ is small or when $n \rightarrow \infty$. Can I ask you why $\bar{X_{n}}$ is $o(\sqrt{n})$ corresponds to a small $t$ please? Apr 14, 2022 at 5:48
• It's not $\bar X_n=o(\sqrt{n}$, it's $(\bar X_n-\mu)/se =o(\sqrt{n})$. The standard error of $\bar X_n$ is $o(1/\sqrt{n})$, so a constant $t$ is some multiple of $\sqrt{n}$ times the standard error. A small $t$ is of smaller order than that. Apr 14, 2022 at 6:33
• I see, right, many thanks for the answers. Apr 14, 2022 at 17:54
• Also, on your first comment: it's better to use Hoeffding's inequality when $t$ is large or $X_i$ are binary (so $\sigma^2$ is that large), or, importantly, when you don't know a bound on $\sigma^2$. Apr 14, 2022 at 20:01
• I understand better why the authors of the paper I was reading used the Hoeffding's now, their main use-cases were on binary $X_{i}$ variables. Thanks a lot ! ^^ Apr 16, 2022 at 20:00