# Does Hoeffding or Bernstein inequality provide a more accurate bound for this problem?

Let $$X_i$$, $$i=1,\dots, n$$ be independent random variables with $$EX_i = \mu_i$$, $$\operatorname{Var}X_i=\sigma^2$$ and $$|X_i - \mu_i| \leq b$$, $$i=1,\dots,n$$. Let $$X=\sum X_i$$ and $$\mu = \sum \mu_i$$. Let $$\tau>0$$ be a fixed constant. Find $$t$$ such that $$P(|X-\mu|\leq t) \geq 1 - 2n^{-\tau}$$ using the Hoeffding and the Bernstein inequalities. Which of the inequalities provides a more accurate bound?

The Hoeffding inequality states that $$P(\bar{X}-E[\bar{X}] \geq t) \leq e^{-2nt^2}$$ where $$t\geq0$$, and $$\bar{X}$$ denotes the empirical mean of these variables.

Whereas, the Bernstein inequality states that $$P(X-\mu\geq t) \leq \exp\left(\frac{-t^2}{2(\sigma^2+bt)}\right).$$

I am not sure how to proceed with this problem.

• Presumably "more accurate" here means whichever gives the bound with smallest value of $t$. You want $P(|X-\mu|\geq t)\leq 2n^{-\tau}$, so figure out which bound gives you a smaller $t$. Intuitively a smaller $t$ implies the empirical mean is more concentrated around the true mean. Oct 15, 2018 at 23:43

## 1 Answer

I believe you're missing a $$1/b^2$$ in the Hoeffding inequality, which should state: $$P(\bar{X}-E[\bar{X}] \geq t) \leq e^{-2nt^2/b^2}$$ where $$t\geq0$$, and $$\bar{X}$$ denotes the empirical mean of these variables.

Intuitively, Bernstein's inequality uses more information about the distribution of $$X$$ in its bound, specifically, the variance of $$X$$, in addition to the bound on the values of $$X$$. Meanwhile Hoeffding's inequality only relies on the bounds on the values of $$X$$. Thus we would expect Bernstein's inequality to provide a better bound when the variance of $$X$$ is small. However, you can compare the upper bounds and see that in some regimes of large variance, Hoeffding's inequality is actually tighter. The gain is not much though, since the variance can be at most $$b^2$$.

To actually solve the problem, you may want to write Bernstein's inequality in terms of sample means as well: $$P(|\bar(X) - E[\bar(X)]| \geq t) \leq 2 \exp(-\frac{nt^2}{2\sigma^2 + (2/3)bt}).$$ (See e.g., Theorem 2 in these notes.)

Then, compare the exponential terms and the desired form $$2n^{-\tau}$$ and figure out what $$t$$ should be in terms of $$n$$ and $$\tau$$ in order for the desired inequalities to hold.