Written By: Qingyang Xu (website)
Date Created: June 12, 2022
Last Modified: January 1, 2024
Date: June 12, 2022
Goal: prove finite-sample concentration bounds $\mathbb{P}(|\frac{1}{N}\sum_i X_i-\mu|>t)$ of independent RV
Proposition 2.1.2 (Tails of normal distribution). Let $g \sim N(0, 1)$. Then for all $t>0$, we have
$$ \Big(\frac{1}{t} -\frac{1}{t^3} \Big) \phi(t) \le \mathbb{P}(g \ge t) \le \frac{1}{t} \phi(t) $$
Issue: approximating the tail probability using CLT yields exponential tail $\mathcal{O}(e^{-cN})$ but the approximation error $\mathcal{O}(1/\sqrt{N})$ is very large, due to the Berry-Esseen CLT
$$ |\mathbb{P}(Z_N \ge t)-\mathbb{P}(Z \ge t)| \le \frac{\rho}{\sqrt{N}} $$
Solution: use techniques (Hoeffding, Bernstein inequalities) which bypass CLT approximation for special distributions (sub-Gaussian, sub-exponential) which capture a large class of RV