4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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}$? $\endgroup$ – soakley May 6 '13 at 16:07
  • $\begingroup$ @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? $\endgroup$ – Spacey May 6 '13 at 16:22
  • 1
    $\begingroup$ 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. $\endgroup$ – whuber May 6 '13 at 17:04
  • 1
    $\begingroup$ @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$$ $\endgroup$ – Dilip Sarwate May 6 '13 at 17:18
  • 1
    $\begingroup$ @whuber Sorry, I am not seeing the connection... $\endgroup$ – Spacey May 6 '13 at 19:59
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ (+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! $\endgroup$ – Spacey May 7 '13 at 19:34
  • $\begingroup$ @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}$ ... $\endgroup$ – Dilip Sarwate May 7 '13 at 19:52
  • $\begingroup$ @Tarantula (continued) and to that question I have no answer. Perhaps people interested in large deviations theory might be able to help. $\endgroup$ – Dilip Sarwate May 7 '13 at 19:54
  • $\begingroup$ 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. $\endgroup$ – Spacey May 7 '13 at 21:06
  • $\begingroup$ @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. $\endgroup$ – Dilip Sarwate May 7 '13 at 21:19

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.