Where is the error in this argument on sub-gaussian concentration inequalities?

39 Views Asked by At

Suppose $X_1,\dots,X_n$ are i.i.d. with $E\,X = 0$ and $\sigma^2$-subgaussian, i.e. $E\, e^{\lambda X}\leq e^{\lambda^2\sigma^2/2}$ for every $\lambda \in \mathbb R$. (For the purposes of this question, you can just take $X_1,\dots,X_n \sim \mathcal N(0,\sigma^2)$ if you wish). I am trying to show that for $\delta\geq 0$, the following bound holds: $$P\left(\sum X_i^2 \leq n E\, X_i^2 - n\sigma^2 \delta\right) = P\left(\sum E\, X_i^2 - X_i^2\geq n\sigma^2\delta\right) \leq e^{-n\delta^2/16}$$ It can be shown that $E\,X^2 = \text{Var}\, X \leq \sigma^2$. Using this and applying the Chernoff strategy, we are led to $$ P\left(\sum E\, X_i^2 - X_i^2\geq n\sigma^2\delta\right) \leq \inf_{\lambda >0} \frac{E \,e^{\lambda \sum(E\, X_i^2 - X_i^2)}}{e^{\lambda n \sigma^2\delta}} \leq \inf_{\lambda >0}e^{\lambda^2n\sigma^2(1-\delta)}E\,e^{-n\lambda X^2}\overset{\text{def}}{=}\inf_{\lambda>0}h(\lambda)$$ But this cannot be correct because as soon as $\delta\geq 1$, we let $\lambda\to \infty$ and get $\inf h(\lambda) = 0$, but the event in question need not be null. For example, taking $X_i\sim \mathcal N(0,\sigma^2)$,while the event in question would be very unlikely for $\delta$ large, it still wouldn't be zero. But I cannot see where I went wrong.

1

There are 1 best solutions below

0
On BEST ANSWER

For $\delta \ge 1$, we're computing the probability $P\left(\sum_iX_i^2 \le c\right),$ for some $c \le 0$. This probability actually is zero, so the bound is fine.