Prove average converges with diminishing $\epsilon$ How can one prove this claim?
Seems like neither Chernoff nor Hoeffding bounds work.
Chernoff bound is not additive. And since it must be that $\epsilon$<$1/n$, Hoeffding bound will not go to zero.

 A: You are right — neither Chernoff nor Hoeffding bounds will provide you with such a strong result. Actually, this appears (conditioned on my making no stupid error in the process) to be because, as stated, the claim does not hold:
Counterexample: Let the $X_i$'s be i.i.d. Bernoulli random variables with parameter $\frac{1}{2}$, and $X^{(n)}\sim\operatorname{Bin}(n,\frac{1}{2})$ their sum; what you want to prove amounts, in this particular case, to showing that there exists a positive sequence $(\epsilon_n)_{n\in\mathbb n}$ such that


*

*$n\epsilon_n \xrightarrow[n\to\infty]{} 0$

*and $p_n\stackrel{\rm{}def}{=}\mathbb P\left\{ \left|X^{(n)}-\frac n2 \right| > n\epsilon_n \right\}\xrightarrow[n\to\infty]{} 0 $


is that right?
If so, since for any $n$ greater than some $N$ you have $n\epsilon_n < 9/10$, it is the case that for $n\geq N$
$$
\begin{align*}
p_n &\geq \mathbb{P}\left\{ \left|X^{(n)}-\frac n2 \right| > \frac{9}{10} \right\} = \mathbb{P}\left\{ \left|X^{(n)}-\frac n2 \right| \geq 1 \right\}
= 1 - \mathbb{P}\left\{ X^{(n)} = \frac n2 \right\} \\
&= 1 - {n \choose n/2}2^{-n} \xrightarrow[n\to\infty]{} 1
\end{align*}
$$
since ${n \choose n/2}2^{-n}\sim \sqrt{\frac{2}{\pi n}}$.
This shows — again, provided I made no mistake — that the claim is false.
