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.

  • $\begingroup$ 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. $\endgroup$ – Alex R. Oct 15 '18 at 23:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.