1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – herb steinberg Sep 18 '18 at 19:27
  • $\begingroup$ You are absolutely right, I meant $1-\Phi(y)$. $\endgroup$ – Graf Zahl Sep 18 '18 at 19:30
  • $\begingroup$ 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). $\endgroup$ – E-A Sep 18 '18 at 20:53
  • 1
    $\begingroup$ 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$ $\endgroup$ – herb steinberg Sep 18 '18 at 23:51
  • $\begingroup$ 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. $\endgroup$ – Graf Zahl Sep 19 '18 at 7:30
0
$\begingroup$

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}$.

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

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}

$\endgroup$
0
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.