# Central Limit Theorem and Hoeffding's bound yield different conclusions

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 ?

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$$.
• I forgot the $\sqrt n$ part when applying the CLT, how silly of me ! Btw I cannot upvote your post because my rep is too low. – Issou Chankla Oct 28 '18 at 17:54