# Asymptotic probability concerning the largest absolute value in an iid Gaussian sample

Let $v[n]$ be a vector $N$ $iid$ gaussian samples, of ~$N(0,\sigma^2)$ Also, let $v_{max}$ denote the maximum absolute value of all the samples given. (That is, if I took the absolute value of all the $N$ random samples given, and picked the max, that would be $v_{max}$).

I am trying to ascertain why this statement is true:

In English:

"The probability of $v_{max}$ exceeding $\sigma \sqrt{2log_e N}$ approaches $0$, as the sample size $N$ approaches infinity."

In mathematical terms:

$$\lim_{N \to \infty} P \left( v_{max} > \sigma \sqrt{2log_e{N}} \right) = 0$$

I am not even sure where to start on this. Intuitively, I am not even sure why the sample size $N$ should matter, so I do not even have a starting intuitive traction for this particular problem. Would appreciate any insights.

TLDR: How is the $\sigma \sqrt{2log_e{N}}$ derived exactly?

Edit, what I have tried so far:

Thanks to the comments, I have managed to piece together something, but it still seems I am a ways away.

I want to show that $\lim_{N \to \infty} P(v_{max} > z) = 0$ becomes true when $z=\sigma \sqrt{2log_eN})$. Based on the $iid$ assumption, we can say then say that

$$P(v_{max} > z) = P(|v_1|, |v_2|, |v_3| ... |v_N| > z) = \left [2 - 2\Phi_{\sigma}(z) \right]^N$$

, where $\Phi_{\sigma}$ is the CDF the common gaussian distribution, given by:

$$\Phi_{\sigma}(z) = \frac{1}{2} + \frac{1}{2} erf \left [\frac{z}{\sigma \sqrt{2}} \right]$$

Then this means, that by simple substitution,

$$P(v_{max} > z) = \left[1 - erf \left( \frac{z}{\sigma \sqrt{2}}\right) \right]^N$$

And thus,

$$\lim_{N \to \infty} P(v_{max} > z) = \lim_{N \to \infty} \left[1 - erf \left( \frac{z}{\sigma \sqrt{2}}\right) \right]^N = 0$$

Here however I am stuck. How does one show from here that $z=\sigma \sqrt{2log_eN})$?...

Thanks

• For intuition on why the sample size matters, take it to the extreme. Imagine a sample of size 1. Now think about a much larger sample, maybe 1000. What do you think happens to $v_{max}$? – soakley May 6 '13 at 16:07
• @soakley I think as N increases, you are more and more likely to see every possible sample that can be rendered given a gaussian PDF with whatever $\sigma$ characterizes it... so I guess that would mean this limit is just another way of saying 'worst case'. I suppose that makes sense. The main question now becomes how is this $T$ derived in this case? – Spacey May 6 '13 at 16:22
• The chance that $v_{\max}$ does not exceed any fixed value $z$ is the chance that all the $v[n]$ do not exceed $z$. The independence assumption implies the latter equals $\Phi_\sigma(z)^N$ where $\Phi_\sigma$ is the CDF of the common distribution. The dependence on $N$ is clear and shows that this problem amounts to an analysis of the behavior of the right tail of the Normal CDF. – whuber May 6 '13 at 17:04
• @whuber I think the following minor correction applies to your comment because $v_\max$ is the maximum absolute value, not the maximum value: $$P\{v_\max < z\} = \prod_{i=1}^N P\{-z < v_i < z\} = [2\Phi_\sigma(z) - 1]^N$$ – Dilip Sarwate May 6 '13 at 17:18
• @whuber Sorry, I am not seeing the connection... – Spacey May 6 '13 at 19:59

Expanding on whuber's comment and my minor emendation of it, we have that for $z \geq 0$, $$P\{v_\max < z\} = [2\Phi(z/\sigma)-1]^N = [1-2Q(z/\sigma)]^N$$ where $\Phi(x)$ is the standard normal distribution function and $Q(x)=1-\Phi(x)$ is its complement. Now, since $1-2Q(z) < 1$ for $z > 0$, if $z$ and $\sigma$ were constants, that is, not functions of $N$, then as we raised a quantity less than $1$ to ever higher powers $N$, the result would tend to $0$ as $N \to \infty$. On the other hand, if $z/\sigma$ were such that $2Q(z/\sigma)=aN^{-1}$, then we could use the standard result $$\lim_{N\to \infty}\left(1-\frac{a}{N}\right)^N = e^{-a}$$ to deduce that $P\{v_\max < z\}$ converges to a positive constant (smaller than $1$) as $N \to \infty$ and so $P\{v_\max > z\}$ converges to a constant greater than $0$. This is not quite good enough; we need to have $2Q(z/\sigma)$ go to $0$ slightly faster than as $N^{-1}$. What will work? Well, a standard but weak bound on $Q(x)$ is $$Q(x) < \frac{1}{2}e^{-x^2/2} ~~ \text{for} ~x > 0$$ and so if we choose $z = \sigma\sqrt{2\ln N}$, we get $2Q(z/\sigma) < e^{-\ln N} = N^{-1}$ which we just said is not a fast enough decay with increasing $N$, but if we use the tighter bound $$Q(x) < \frac{1}{x\sqrt{2\pi}}e^{-x^2/2},$$ with the same choice $z = \sigma\sqrt{2\ln N}$, that extra $x$ in the denominator is giving us an $\sqrt{\ln N}$ faster decay that suffices to allow us to conclude that $$P\{v_\max > \sigma\sqrt{2\ln N}\,\} \to 0~~ \text{as}~ N \to \infty.$$
• (+1) Thank you @Dilip, I am unpacking and digesting what you wrote, though I believe I understand it. I upvoted this post and the one you linked to on math.se. However, i) I now understand how the selection of $z = \sigma \sqrt{2 log N}$, will make the above limit go to 1. But why the 2 inside or the sqrt? Anything particularly unique about them besides their nice/required behavior in the limit? ii) Is there a particular name for the tight bound that you derived/referenced? Thank you so much! – Spacey May 7 '13 at 19:34
• @Tarantula The exact value of $2Q(z/\sigma)$ is not known, but we do know that $2Q(z/\sigma) < e^{-z^2/2\sigma^2}$. We want $2Q(z/\sigma)$ to approach $0$ slightly faster than $N^{-1}$, and so we try to choose the value of $z$ such that $-z^2/2\sigma^2 = \ln N$ thus ensuring that the upper bound is going to $0$ as $N^{-1}$ and so $2Q(z/\sigma)$ is decaying away at least as fast, and hopefully slightly faster. As it turns out, this is good enough. A much harder question would be what is the slowest growing function of $N$ that will make $2Q(z/\sigma)$ decay away faster than $N^{-1}$ ... – Dilip Sarwate May 7 '13 at 19:52
• That makes sense. I have accepted your answer. One last question, any reason for why you started the analysis with $P(v_{max} < z)$ instead of $P(v_{max} > z)$? I realize one gives you the other, but was wondering if there was a reason you chose the opposite of what was in the question initially. – Spacey May 7 '13 at 21:06
• @Tarantula Thanks. Glad to have been of help. With regard to your last query, I just followed up on Moderator whuber's comment which was there already and had been emended slightly by me. I could have used $\{v_\max > z\}$ from the beginning, and that would have been my inclination if I had been answering ab initio, but I wanted to link up matters to what had been said before. – Dilip Sarwate May 7 '13 at 21:19