The problem of tail approximation using CLT

info

Reference textbook High-Dimensional Statistics: A Non-Asymptotic Viewpoint, Martin J. Wainwright

The tail of standard normal distribution $t>0$:

$$\left( \frac { 1 } { t } - \frac { 1 } { t^{ 3 } } \right) \cdot \frac { 1 } { \sqrt { 2 \pi } } e^{ - t^{ 2 } / 2 } \leq P \{ g \geq t \} \leq \frac { 1 } { t } \cdot \frac { 1 } { \sqrt { 2 \pi } } e^{ - t^{ 2 } / 2 }$$

$$P \{ g \geq t \} \leq \frac { 1 } { \sqrt { 2 \pi } } e^{ - t^{ 2 } / 2 }\text{ when } t \geq 1$$

Tail Approximation for $S_N$: B(N,1/2)

By Chebyshev

$$P \left\{ S_{ N } \geq \frac { 3 } { 4 } N \right\} \leq P \left\{ \left| S_{ N } - \frac { N } { 2 } \right| \geq \frac { N } { 4 } \right\} \leq \frac { 4 } { N }$$

By CLT

$$\mathbb { P } \left\{ S_{ N } \geq \frac { 3 } { 4 } N \right\} = \mathbb { P } \left\{ Z_{ N } = \frac { S_{ N } - N / 2 } { \sqrt { N / 4 } } \geq \sqrt { N / 4 } \right\} \approx \mathbb { P } \{ g \geq \sqrt { N / 4 } \} \leq \frac { 1 } { \sqrt { 2 \pi } } e^{ - N / 8 }$$

Berry-Essen CLT, $\rho = \mathbb { E } \left| X_{ 1 } - \mu \right|^{ 3 } / \sigma^{ 3 }$

$$\left| \mathbb { P } \left\{ Z_{ N } \geq t \right\} - \mathbb { P } \{ g \geq t \} \right| \leq \frac { \rho } { \sqrt { N } }$$

Thus the approximation error is of order $\frac{1}{\sqrt{N}}$, which ruins the desired exponential decay.