Problem
Let $X_1, ..., X_n$ be iid, with mean $\mu$, $\text{Var}(X_i) = \sigma^2$ and $|X_i| \leq c$. Bernstein’s inequality says that
$$ P(|\overline{X_n} - \mu| > t) \leq 2 e^{-\frac{nt^2}{2 \sigma^2 + 2ct/3}} $$
Suppose that $X_i$ has a bounded density $p$ supported on $[-1, 1]$. Let $A_n = [-\frac{1}{n^2}, \frac{1}{n^2}]$. Let $Y_i = I(X_i \in A_n)$. ($I$ is the indicator function). Use both Hoeffding’s inequality and Bernstein’s inequality to get bounds on
$$ P(\overline{Y_n} - \theta_n > t) $$
where $\theta_n = P(X_i \in A_n)$. Which bound is tighter?
Solution
Sources
- 36-705 hw2 problem 2