Central Limit Theorem and Hoeffding's bound yield different conclusions

200 Views Asked by At

Let $X_1,\ldots,X_n$ be i.i.d Bernoulli r.v with parameters $p$. For the sake of the example, say that $p=0.9$. I want to assess $P(\frac 1n \sum_{i=1}^nX_i\leq 0.1).$

By the CLT, $\frac 1n \sum_{i=1}^n (X_i-p)$ converges in distribution to $\mathcal N(0,p(1-p))$, hence $\frac 1n \sum_{i=1}^nX_i$ converges to $\mathcal N(p,p(1-p))$. Thus $\displaystyle \lim_{n\to \infty}P(\frac 1n \sum_{i=1}^nX_i\leq 0.1)= P(Y\leq 0.1)$ where $Y\sim \mathcal N(p,p(1-p))$.

Next, $P(Y\leq 0.1) = P(\frac{Y-p}{\sqrt{p(1-p)}}\leq \frac{0.1-p}{\sqrt{p(1-p)}})\approx 0.0038$. Hence $P(\frac 1n \sum_{i=1}^nX_i\leq 0.1)$ has a non-zero limit.

However, by Hoeffding's bound, $$\begin{align}P(\frac 1n \sum_{i=1}^nX_i\leq 0.1) &= P(\frac 1n \sum_{i=1}^nX_i - p\leq 0.1-p) = P(\frac 1n \sum_{i=1}^nX_i - p\leq -0.8)\\ &\leq P(\left|\frac 1n \sum_{i=1}^nX_i - p\right|\geq 0.8)\\ &\leq e^{-2n0.8^2}\to 0 \end{align}$$ This implies that $P(\frac 1n \sum_{i=1}^nX_i\leq 0.1)$ goes to $0$, a contradiction with the previous conclusion. Where have I gone wrong ?

1

There are 1 best solutions below

2
On BEST ANSWER

Note that $${\rm Var}\left[\frac 1 n \sum_{i=1} (X_i - p)\right] = \frac 1 {n^2} \sum_{i=1}^n {\rm Var}[X_i - p] = \frac 1 {n^2} (n \times p (1-p)) = \frac{p(1-p)}{n}.$$ So $\frac 1 n \sum_{i=1} (X_i - p)$ converges in distribution to $\mathcal N\left(0, \tfrac{p(1-p) }{n}\right)$, which depends non-trivially on $n$.