# Inequality for the maximum of the absolute value of two normal distributed random-variables

I would like to show following statement:

For $M\geq 2,\ X_1,\dots,X_M\sim^{iid}\mathcal{N}(0,1)$ independent, it holds $P(\max_{i=1,\dots,M}\lvert X_i\rvert\geq y)\leq Me^{-y^2/2}$.

I think it is possible to show it via induction, but I have got problems at the start:

So, I want to show $P\left(\max(\lvert X_1\rvert,\lvert X_2\rvert)\geq y \right)\leq 2 e^{-y^2/2}$. One can show $P\left(\max(\lvert X_1\rvert,\lvert X_2\rvert )\geq y\right)=4\Phi(y)(1-\Phi(y))$ where $\Phi$ denotes the distribution function. I know that $1-\Phi(y)\leq e^{-y^2/2}$, so this inequality seems to be a little sharper to me. Maybe someone knows how to prove this or an alternative prooving strategy.

• The statement $\Phi(y)\le e^{-y^2/2}$ does not make sense for a distribution function, which should $\to 1$ as $y \to \infty$. You need to clarify. – herb steinberg Sep 18 '18 at 19:27
• You are absolutely right, I meant $1-\Phi(y)$. – Graf Zahl Sep 18 '18 at 19:30
• I think you are right; I think the constant M should be replaced by 2M on the upper bound (in which case the proof is a simple union bound). – E-A Sep 18 '18 at 20:53
• For $y\ge 1$ the bound on $1-\Phi(y)$ can be improved to the value you need. $1-\Phi(y)=\frac{1}{\sqrt{2\pi}}\int_y^{\infty}e^{-\frac{x^2}{2}}dx\le \frac{1}{ \sqrt{2\pi}}\int_y^{\infty}xe^{-\frac{x^2}{2}}dx = \frac{1}{\sqrt{2\pi}}e^{-\frac{y^2}{2}}$. Since $\sqrt{2\pi}>2$, you have the bound you want. I don't have a good estimate for $0\le y\le 1$ – herb steinberg Sep 18 '18 at 23:51
• I think this should work. For $0\leq y \leq 1$ we have $2e^{-y^2/2}\geq2/\sqrt{e}\geq 1$ and we are done. – Graf Zahl Sep 19 '18 at 7:30

General result: Let $G(y)=P(|X|\le y)=\frac{2}{\sqrt{2\pi}}\int_0^ye^{-\frac{u^2}{2}}du$. $G^2(y)=\frac{2}{\pi}\int_0^y\int_0^ye^{-\frac{u^2+v^2}{2}}dudv$.
Switch to polar coordinates (note) and get $G^2(y)\gt \int_0^ye^{-\frac{r^2}{2}}rdr=1-e^{-\frac{y^2}{2}}$ or $G(y)\gt (1-e^{-\frac{y^2}{2}})^\frac{1}{2}$.

In general $P(max|X_1|,|X_2|,....,|X_M|\le y)=G^M(y)\gt (1-e^{-\frac{y^2}{2}})^\frac{M}{2}$. Therefore $P(max|X_1|,|X_2|,....,|X_M|\gt y)\lt 1-(1-e^{-\frac{y^2}{2}})^\frac{M}{2}=1-1+\frac{M}{2}e^{-\frac{y^2}{2}}-...\lt \frac{M}{2}e^{-\frac{y^2}{2}}$

Note: The domain of integration is a square $y$ by $y$. The switch to polar coordinates is an integration over the maximum sector within the square, radius $=y$ and angle $=\frac{\pi}{2}$.

• This looks right to me, so I will accept your answer since the bound is sharper than the upper bound I found. – Graf Zahl Sep 20 '18 at 11:30
• @Graf Zahl I rewrote the general solution so it holds for all M, not just even M. – herb steinberg Sep 20 '18 at 15:53

So, for matters of completeness: I think I am now able to prove the statement.

Consider $M=2$. For $0\leq y\leq 1$ the statement follows as $2e^{-y^2/2}\geq 2/\sqrt{e} \geq 1$. For $y>1$ use the comment of herb steinberg above.

Now assume the statement holds for $M$. For $0\leq y \leq 1$ there is again nothing to prove. Otherwise use again the argument in the comments: \begin{align} P\left(\max_{i=1\dots,M+1}\lvert X_i \rvert\geq y\right)\leq P\left(\max_{i=1\dots,M}\lvert X_i \rvert\geq y\right)+P\left(\lvert X_{M+1} \rvert\geq y\right)\leq (M+1)e^{-y^2/2}. \end{align}

Direct proof: Let $G(y)=1-4\Phi(y)(1-\Phi(y))=1+4\Phi(y)^2-4\Phi(y)$, the distribution function for $max(|X_1|,|X_2|)$. The density function $g(y)=8\Phi(y)\phi(y)-4\phi(y)$. Now $\Phi(y)=\frac{1}{2}+\frac{1}{\sqrt{2\pi}}\int_0^y e^{-\frac{u^3}{2}}du$, so $g(y)=\frac{4}{\pi}e^{-\frac{y^2}{2}}\int_0^y e^{-\frac{u^2}{2}}du$. Therefore $G(y)=\frac{4}{\pi}\int_0^y\int_0^ve^{-\frac{u^2+v^2}{2}}dudv$. Switching to polar coordinates (note), where $0\le \theta \le \frac{\pi}{4}$, we get $G(y)\gt \int_0^yre^{-\frac{r^2}{2}}dr=1-e^{-\frac{y^2}{2}}$, or $P(max|X_1|,|X_2|)\ge y)\le e^{-\frac{y^2}{2}}$

note: The domain of the double integral is a right triangle in the $(u,v)$ plane with the hypotenuse along the line $u=v$, from $(0,0)$ to $(y,y)$ and base along the $v$ axis. To get the inequality, the integral is over the sector of radius $y$ within the triangle.

• Note that my answer is a factor of 2 better than what was asked for. (I hope I didn't make a mistake). – herb steinberg Sep 19 '18 at 19:48