1 6 6 Concentration Of The Square Norm Of A Gaussian Random

A)

1) Assume $\epsilon=(\epsilon_1,...,\epsilon_n)\hookrightarrow N(0,I_n)$ then using lemma A1 page 213 we have: $\forall i \in [1,n], \epsilon_i\hookrightarrow N(0,1)$

Computing the density of $\epsilon_i^2$ we obtain that: $\forall x\in (0,\infty)$ we have

$$f_{\epsilon_i^2}(x)=\displaystyle\frac{1}{\sqrt{2\pi}\sqrt{x}}exp\left(-\displaystyle\frac{x}{2}\right)$$

where we recognize the gamma density so we conclude that $\epsilon_i^2\hookrightarrow \Gamma\left(\displaystyle\frac{1}{2},2\right)$.

We remind that:

$$ X\hookrightarrow \Gamma(k,\theta) : f_X(x)=\displaystyle\frac{x^{k-1}exp\left(-\frac{x}{\theta}\right)}{\Gamma(k)\theta^k}$$
Using the well known additive propriety of the gamma distribution we finally get:

$$\lVert\epsilon\rVert^2\hookrightarrow \Gamma\left(\displaystyle\frac{n}{2},2\right)$$

Then:

(1)

\begin{align} E\left[exp\left(s\lVert\epsilon\rVert^2\right)\right]&=\displaystyle\int_{\mathbb{R}}exp(sx) \displaystyle\frac{\left(\displaystyle\frac{1}{2}\right)^{\frac{n}{2}}}{\Gamma(\frac{n}{2})}x^{\frac{n}{2}-1}exp\left(-\displaystyle\frac{x}{2}\right)dx \\ &=\displaystyle\int_{\mathbb{R}}\displaystyle\frac{\left(\displaystyle\frac{1}{2}\right)^{\frac{n}{2}}}{\Gamma(\frac{n}{2})}x^{\frac{n}{2}-1}exp\left(-\displaystyle\frac{x}{2}(1-2s)\right)dx \\ &=\displaystyle\int_{\mathbb{R}}\displaystyle\frac{\left(\displaystyle\frac{1}{2}\right)^{k}}{\Gamma(k)}x^{k-1}exp\left(-\displaystyle\frac{x}{\theta}\right)dx \end{align}

with $k=\displaystyle\frac{n}{2}$ and $\theta=\displaystyle\frac{2}{1-2s}$ using that $0<s<\displaystyle\frac{1}{2}$.

Finally we get:

(2)

\begin{align} E\left[exp\left(s\lVert\epsilon\rVert^2\right)\right]&=\theta^k \left(\displaystyle\frac{1}{2}\right)^{k}\\ &=\left(1-2s\right)^{-k}\\ &=\left(1-2s\right)^{-\frac{n}{2}}\\ \newline \newline \end{align}

N.B: this solution is for gamma distribution lovers but chi-square fan must have recognized the characteristic function of their beloved distribution.

2) Using Lemma B1 (page 297):$\forall \lambda>0, \forall t \in\mathbb{R}$

$$P\left[X\geq t \right]\leq exp(-\lambda t) E\left[exp(\lambda X)\right]$$

we get:$\forall 0<s<\displaystyle\frac{1}{2}, \forall t >0,$

$$ P\left[\lVert\epsilon\rVert^2>n+t \right]\leq exp\left(-s(n+t)\right)\left(1-2s\right)^{\frac{-n}{2}} $$

3) We want to minimize the above bound, so we want to minimize on $\left(0,\displaystyle\frac{1}{2}\right)$ the following function:
$$ f(s)=exp\left(-s(n+t)\right)\left(1-2s\right)^{\frac{-n}{2}} $$

which is equivalent to minimize $g(s)=ln\left(f(s)\right)=-s(n+t)-\displaystyle\frac{n}{2}log(1-2s)$

An easy computation give us:

$$ g'(s)=-(n+t)+\displaystyle\frac{n}{1-2s}$$

then g(s) and f(s) reach their minimum on $\left(0,\displaystyle\frac{1}{2}\right)$ for $s=\displaystyle\frac{t}{2(n+t)}$

since g is convex: $$g''(s)=\displaystyle\frac{2n}{(1-2s)^2}>0.$$

then we have to check :

$$\left( \frac{1}{1 - \frac{t}{n+t}}\right)^{n/2} \le \left(1 + \frac{t}{n}\right)^{n/2}$$

which is true because of $$\frac{1 + \frac{t}{n}}{1 - \frac{t}{n+t}} = \left( \frac{n+t}{n} \right)^2 > 1$$

Then:

$$ P\left[\lVert\epsilon\rVert^2>n+t \right]\leq exp\left(-\displaystyle\frac{t}{2}\right)\left(1+\displaystyle\frac{t}{n}\right)^{\frac{n}{2}} $$

4) We write $g(u)=log(1+u)-u+\displaystyle\frac{u^2}{2+2u}$ so deriving we obtain:

(3)

\begin{align} g'(u)&=\displaystyle\frac{1}{1+u}-1+\displaystyle\frac{4u+2u^2}{(2+2u)^2} \\ &=\displaystyle\frac{-u^2}{2(1+u)^2}\leq 0. \end{align}

Hence, as $g(0)=0$ we conclude that $\forall u \geq 0$ we have:

$$ log(1+u)\leq u-\displaystyle\frac{u^2}{2+2u} $$

Using this inequality we obtain:

$$-\displaystyle\frac{t}{2}+\displaystyle\frac{n}{2}log\left(1+\displaystyle\frac{t}{n}\right)\leq -\displaystyle\frac{t}{2}+\displaystyle\frac{n}{2}\left(\displaystyle\frac{t}{n}-\displaystyle\frac{t^2/n^2}{2+2t/n}\right)=\displaystyle\frac{-t^2}{4n+4t}$$

then taking the exponential in the above inequality and using question 3) we have: $\forall t>0$

$$ P\left[\lVert\epsilon\rVert^2>n+t \right]\leq exp\left(-\displaystyle\frac{t}{2}\right)\left(1+\displaystyle\frac{t}{n}\right)^{\frac{n}{2}} \leq exp\left(-\displaystyle\frac{t^2}{4(n+t)}\right)$$

5) We deduce from 4):

$$ P\left[\lVert\epsilon\rVert^2 \leq n+t \right]\geq 1-exp\left(-\displaystyle\frac{t^2}{4(n+t)}\right) $$

With $t=2\sqrt{2nx}+2x$, $0<x\leq n$ we have:

$$ 1-exp\left(-\displaystyle\frac{t^2}{4(n+t)}\right)=1-exp\left(\displaystyle\frac{-x(2n+x+2\sqrt{2nx})}{n+2\sqrt{2nx}+2x}\right)\geq 1-exp(-x) $$

since $$\displaystyle\frac{\left(2n+x+2\sqrt{2nx}\right)}{n+2\sqrt{2nx}+2x}\geq 1 \Leftrightarrow n-x \geq 0$$

so for $0<x\leq n$, $$ P\left[\lVert\epsilon\rVert^2 \leq n+2\sqrt{2nx}+2x \right]\geq 1-exp\left(-x \right) $$

6) It is easy to show that $log(1+u) \leq \sqrt{u}$ for $u \geq 0$.

Indeed, we write $g(u)=log(1+u)-\sqrt{u}$ and deriving we obtain

$$g'(u)=\displaystyle\frac{2\sqrt{u}-1-u}{2\sqrt{u}(1+u)}=\displaystyle\frac{-(\sqrt{u}-1)^2}{2\sqrt{u}(1+u)}\leq 0$$

and as $g(0)=0$ we have proved the inequality.

We use it for $u=\displaystyle\frac{2\sqrt{2nx}+2x}{n}$:

$$\displaystyle\frac{n}{2}ln\left(1+\displaystyle\frac{2\sqrt{2nx}+2x}{n}\right)\leq \displaystyle\frac{n}{2}\sqrt{\displaystyle\frac{2\sqrt{2nx}+2x}{n}}$$

and $$\displaystyle\frac{n}{2}\sqrt{\displaystyle\frac{2\sqrt{2nx}+2x}{n}}\leq \sqrt{2nx} \Leftrightarrow 2n\leq 9x$$ wich is true for $x\geq n$.

7) We want to show that for $n \leq x$, $$ P\left[\lVert\epsilon\rVert^2 \leq n+2\sqrt{2nx}+2x \right]\geq 1-exp\left(-x \right) $$

Using (3) we know that $$ P\left[\lVert\epsilon\rVert^2 \leq n+t \right]\geq 1-exp\left(-\frac{t}{2} \right)\left(1+\displaystyle\frac{t}{n}\right)^{\frac{n}{2}} $$

so we just have to prove that $$ exp\left(-\frac{t}{2} \right)\left(1+\displaystyle\frac{t}{n}\right)^{\frac{n}{2}}\leq exp(-x)\Leftrightarrow -\displaystyle\frac{t}{2}+\displaystyle\frac{n}{2}ln\left(1+\displaystyle\frac{t}{n}\right)\leq -x$$
with $t=2\sqrt{2nx}+2x$

We can check the last inequality using (6).

B

1) The solution here is very close to the one seen in A 1), but here is another way to approach it.
We distinguish two cases:

- $s \neq 0$ :

We use the same tools as in Hoeffding’s inequalities:

(4)

\begin{align} \mathbb{P}(n - || \epsilon || ^2 \ge t) &= \mathbb{P}( e^{s || \epsilon ||^2} \ge e^{s (t-n)} ) \end{align}

Using Markov’s inequality, we obtain:

(5)

\begin{align} \mathbb{P}(n - || \epsilon || ^2 \ge t) \le e^{s (n-t)}\mathbb{E}( e^{s || \epsilon ||^2}) \end{align}

By independence:

(6)

\begin{align} \mathbb{E}( e^{s || \epsilon ||^2}) = \mathbb{E}( e^{s \sum_{i=1}^n \epsilon_i^2}) = \prod_{i=1}^{n}\mathbb{E}( e^{s \epsilon_i^2}) = \mathbb{E}( e^{s \epsilon_1^2})^n \end{align}

With the change of variable $u = (1+2s)x$, we get $\mathbb{E}( e^{s \epsilon_1^2}) = \frac{1}{\sqrt{1+2s}}$.

- $s = 0$ :

This case holds as it is the limit of the previous one, and the bound remains unchanged since the normal distribution does not assign mass to singletons.

2) and 3) can be solved in the same way as in part A.

4) We need to consider separately the cases $2\sqrt(nx) > n$ and $2\sqrt(nx) \le n$.

In the first case, given that $|| \epsilon || \ge 0$ :

(7)

\begin{align} \mathbb{P}(|| \epsilon || \ge n - 2\sqrt(nx)) = \mathbb{P}(|| \epsilon || \ge 0) = 1 \ge 1 - e^{-x} \end{align}

The conclusion in the second case follows directly from 3), as in the previous answers.