Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
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.
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)
