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