9
$\begingroup$

Given $X_1, \ldots, X_n, \ldots \sim \mathscr{N}(0,1)$ i.i.d., consider the random variables

$$ Z_n := \max_{1 \le i \le n} X_i\,. $$

Question: What is the most "important" result about these random variables?

To clarify "importance", which result has the most other such results as a logical consequence? Which of the results is used most often in practice?

More specifically, it seems to be folklore knowledge among (theoretical) statisticians that the $Z_n$ are "basically the same as" $\sqrt{2 \log n}$, at least asymptotically. (See this related question.)

However, there are many related results of this type, and it seems to be the case that most aren't equivalent, nor imply each other. For example$^*$,

$$ \frac{Z_n}{\sqrt{2 \log n}} \overset{a.s.}{\to} 1 \,, \tag{1}$$

which if nothing else also implies the corresponding results in probability and distribution.

However, it doesn't even imply seemingly also related results (see this other question), like

$$ \lim_{n \to \infty} \frac{\mathbb{E}Z_n}{\sqrt{2 \log n}} =1 \,, \tag{2}$$

(this is exercise 2.17 on p. 49 of $\dagger$), or another folklore result:

$$ \mathbb{E}Z_n = \sqrt{2 \log n} + \Theta(1) \,. \tag{3}$$

Non-asymptotically, it is also known that for each $n$ (see here for a proof),

$$ \sqrt{c \log n} \le \mathbb{E}Z_n \le \sqrt{2 \log n} \tag{4} $$

for some small $c$. Similar results can also be shown for $|Z_n|$, since $Z_n$ is heavily right-skewed.

The proof of this last result is much more straightforward than the proofs of the other results. My hope had been that the first asymptotic result would have implied all of the other asymptotic ones, so that I could feel confident focusing all of my time and energy in understanding that result. But, again, that seemingly is not true, so now it is unclear to me which I should focus on.

$^*$See pp. 265-267 of the second edition of Galambos, The Asymptotic Theory of Extreme Order Statistics, printed in 1987. It is probably also stated somewhere in the first edition.

$\dagger$ Boucheron, Lugosi, Massart, Concentration Inequalities: A Nonasymptotic Theory of Independence. Aside: This book actually cites Galambos for the result in question, but I can't find it mentioned anywhere in Galambos -- only the first result I mentioned.

$\endgroup$
  • 1
    $\begingroup$ Do you know that when you use \dots in MathJax the result sometimes appears as if you'd used \ldots and sometimes as if you'd used \cdots, depending on the context? $$ \begin{align} & \text{X_1, \dots, X_n, \dots \sim \mathscr{N}(0,1)} & & X_1, \dots, X_n, \dots \sim \mathscr{N}(0,1) \\ \\ & \text{X_1, \ldots, X_n, \ldots \sim \mathscr{N}(0,1)} & & X_1, \ldots, X_n, \ldots \sim \mathscr{N}(0,1) \end{align} $$ I replaced \dots with \ldots in this question. $\endgroup$ – Michael Hardy Dec 4 '18 at 22:29
  • $\begingroup$ @MichaelHardy Oh I thought it was always centered. Thanks for the fix! $\endgroup$ – Chill2Macht Dec 4 '18 at 22:33
4
$\begingroup$

In any probabilistic application, the most fundamental object is the distribution, with the moments and limiting properties being derivable from this. Hence, the most "important" result, in the sense you've described, is the full distribution function $F_{Z_n}(z) = \Phi^n(z)$ (equivalently, the corresponding density function). In practice, this distributional result is perhaps less illuminating than some of the more basic asymptotic properties you've already listed. Although it logically implies these asymptotic results, in my view, those results are likely to be more illuminating in understanding the changing nature of the extreme value as we change $n$.

It is clear from your question that you have a good understanding of the extreme value properties in the case of a maximum of IID standard normal random variables. These properties are all logically derivable from the distribution function for $Z_n$, so that is the most fundamental object at work in this problem. As in many cases, the most fundamental object is not necessarily the most illuminating, and so you will probably find that you have to make do with knowing all the results, and knowing that they illuminate different aspects of the problem.

$\endgroup$
  • $\begingroup$ Thanks for this answer -- I appreciate it. Do you know of a reference for how to derive all of these properties from the distribution function for $Z_n$? I've been having extreme difficulty finding anything that explains this, because it's all either "folklore" or "hand-holding". $\endgroup$ – Chill2Macht Sep 25 '18 at 1:09
  • $\begingroup$ For the record, I've read the links and they don't help. That's why I asked the question. $\endgroup$ – Chill2Macht Sep 25 '18 at 4:52
  • 1
    $\begingroup$ I don't have a specific reference to recommend, but I'd think these results would be derived in books on extreme value theory. I'd suggest you start by looking for some graduate-level texts on that subject and see if you can find the derivations there. $\endgroup$ – Ben Dec 11 '18 at 0:17
0
$\begingroup$

W.I.P.: Work in progress

Following p. 370 of Cramer's 1946 Mathematical Methods of Statistics, define $$\Xi_n = n(1 - \Phi(Z_n)) \,. $$ Here $\Phi$ is the cumulative distribution function of the standard normal distribution, $\mathscr{N}(0,1)$. As a consequence of its definition, we are guaranteed that $0\le \Xi_n \le n$ almost surely.

Consider a given realization $\omega \in \Omega$ of our sample space. Then in this sense $Z_n$ is both a function of $n$ and $\omega$, and $\Xi_n$ a function of $Z_n, n$, and $\omega$. For a fixed $\omega$, we can consider $Z_n$ a deterministic function of $n$, and $\Xi_n$ a deterministic function of $Z_n$ and $n$, thereby simplifying the problem. We aim to show results which hold for almost surely all $\omega \in \Omega$, allowing us to transfer our results from a non-deterministic analysis to the non-deterministic setting.

Following p. 374 of Cramer's 1946 Mathematical Methods of Statistics, assume for the moment (I aim to come back and supply a proof later) that we are able to show that (for any given $\omega \in \Omega$) the following asymptotic expansion holds (using integration by parts and the definition of $\Phi$):

$$ \frac{\sqrt{2\pi}}{n}\Xi_n = \frac{1}{Z_n}e^{-\frac{Z_n^2}{2}}\left( 1 + O \left( \frac{1}{Z_n^2} \right) \right) \quad ~~ as ~~ Z_n \to \infty \,. \tag{~}$$

Clearly we have that $Z_{n+1} \ge Z_n$ for any $n$, and $Z_n$ is almost surely an increasing function of $n$ as $n\to \infty$, therefore we claim in what follows throughout that for (almost surely all) fixed $\omega$: $$ Z_n \to \infty \quad \iff \quad n \to \infty \,. $$

Hence it follows that we have (where $\sim$ denotes asymptotic equivalence):

$$ \frac{\sqrt{2\pi}}{n} \Xi_n \sim \frac{1}{Z_n} e^{-\frac{1}{Z_n^2}} \quad ~~ as ~~ Z_n \to \infty \quad n \to \infty \,. $$

How we proceed in what follows amounts essentially to the method of dominant balance, and our manipulations will be formally justified by the following lemma:

Lemma: Assume that $f(n) \sim g(n)$ as $n \to \infty$, and $f(n) \to \infty$ (thus $g(n) \to \infty$). Then given any function $h$ which is formed via compositions, additions, and multiplications of logarithms and power laws (essentially any "polylog" function), we must have also that as $n \to \infty$: $$ h(f(n)) \sim h(g(n)) \,. $$ In other words, such "polylog" functions preserve asymptotic equivalence.

The truth of this lemma is a consequence of Theorem 2.1. as written here. Note also that what follows is mostly an expanded (more details) version of the answer to a similar question found here.

Taking logarithms of both sides, we get that:

$$\log ( \sqrt{2\pi} \Xi_n ) - \log n \sim -\log Z_n - \frac{Z_n^2}{2} \,. \tag{1}$$

This is where Cramer is somewhat cagey; he just says "assuming $\Xi_n$ is bounded", we can conclude blah blah blah. But showing that $\Xi_n$ is suitably bounded almost surely seems to be actually somewhat non-trivial. It seems that the proof of this may essentially be part of what's discussed on pp. 265-267 of Galambos, but I am not sure given that I am still working to understand the content of that book.

Anyway, assuming one can show that $\log \Xi_n = o(\log n)$, then it follows (since the $-Z_n^2/2$ term dominates the $-\log Z_n$ term) that:

$$ - \log n \sim - \frac{Z_n^2}{2} \quad \implies \quad Z_n \sim \sqrt{2 \log n} \,. $$

This is somewhat nice, since it is already most of what we want to show, although again it is worthwhile to note that it is essentially only kicking the can down the road, since now we have to show some certain almost surely boundedness of $\Xi_n$. On the other hand, $\Xi_n$ has the same distribution for any maximum of i.i.d. continuous random variables, so this may be tractable.

Anyway, if $Z_n \sim \sqrt{2 \log n}$ a.s., then clearly one can also conclude that $Z_n \sim \sqrt{2 \log n}(1 + \alpha(n))$ for any $\alpha(n)$ which is $o(1)$ as $n \to \infty$. Using our lemma about polylog functions preserving asymptotic equivalence above, we can substitute this expression back into $(1)$ to get:

$$\log(\sqrt{2 \pi} \Xi _n)- \log n \sim -\log (1 + \alpha) - \frac{1}{2}\log 2 - \frac{1}{2}\log \log n - \log n - 2 \alpha \log n - \alpha^2 \log n \,. $$

$$ \implies -\log(\Xi_n \sqrt{2 \pi}) \sim \log(1 + \alpha) + \frac{1}{2} \log 2 + \frac{1}{2} \log \log n + 2\alpha \log n + \alpha^2 \log n \,. $$

Here we have to go even further, and assume that $\log \Xi_n = o( \log \log n) ~~ as ~~ n \to \infty$ almost surely. Again, all Cramer says is "assuming $\Xi_n$ is bounded". But since all one can say a priori about $\Xi_n$ is that $0 \le Xi_n \le n$ a.s., it hardly seems clear that one should have $\Xi_n = O(1)$ almost surely, which seems to be the substance of Cramer's claim.

But anyway, assuming one believes that, then it follows that the dominant term which does not contain $\alpha$ is $\frac{1}{2} \log \log n$. Since $\alpha = o(1)$, it follows that $\alpha^2 = o(\alpha)$, and clearly $\log ( 1 + \alpha) = o (\alpha) = o(o(\alpha \log n))$, so the dominant term containing $\alpha$ is $2 \alpha \log n$. Therefore, we can rearrange and (dividing everything by $\frac{1}{2}\log\log n$ or $2 \alpha \log n$) find that

$$ - \frac{1}{2} \log \log n \sim 2 \alpha \log n \quad \implies \quad \alpha \sim - \frac{\log \log n}{4 \log n} \,. $$

Therefore, substituting this back into the above, we get that:

$$Z_n \sim \sqrt{2 \log n}- \frac{\log\log n}{2 \sqrt{2 \log n}} \,, $$

again, assuming we believe certain things about $\Xi_n$.

We rehash the same technique again; since $Z_n \sim \sqrt{2 \log n} - \frac{\log \log n}{2 \sqrt{2 \log n}}$, then it also follows that

$$ Z_n \sim \sqrt{2 \log n} - \frac{\log \log n}{2 \sqrt{2 \log n}} (1 + \beta(n)) = \sqrt{2 \log n} \left( 1 - \frac{\log \log n}{8 \log n}(1 + \beta(n)) \right) \,,$$

when $\beta(n)=o(1)$. Let's simplify a little before substituting directly back into (1); we get that:

$$ \log Z_n \sim \log(\sqrt{2 \log n}) + \underbrace{\log \left(1 - \frac{\log \log n}{8 \log n}(1 + \beta(n)) \right) }_{\log(O(1)) = o(\log n)} \sim \log (\sqrt{2 \log n}) \,.$$

$$ \frac{Z_n^2}{2} \sim \log n - \frac{1}{2} \log \log n (1 + \beta) + \underbrace{\frac{(\log \log n)^2}{8 \log n} ( 1 \beta)^2}_{o((1+ \beta) \log \log n)} \sim \log n - \frac{1}{2} (1 + \beta) \log \log n \,. $$

Substituting this back into (1), we find that:

$$ \log ( \sqrt{2 \pi} \Xi_n) - \log n \sim - \log(\sqrt{2 \log n}) - \log n + \frac{1}{2}(1 + \beta) \log \log n \quad \implies \quad \beta \sim \frac{\log (4 \pi \Xi_n^2)}{\log \log n} \,. $$

Therefore, we conclude that almost surely

$$Z_n \sim \sqrt{2 \log n} - \frac{\log \log n}{2 \sqrt{2 \log n}} \left(1 + \frac{\log(4 \pi) + 2 \log( \Xi_n)}{\log \log n} \right)\\ = \sqrt{2 \log n} - \frac{\log \log n + \log (4 \pi)}{ 2 \sqrt{2 \log n} } - \frac{\log (\Xi_n)}{\sqrt{2 \log n}} \,. $$

This corresponds to the final result on p.374 of Cramer's 1946 Mathematical Methods of Statistics except that here the exact order of the error term isn't given. Apparently applying this one more term gives the exact order of the error term, but anyway it doesn't seem necessary to prove the results about the maxima of i.i.d. standard normals in which we are interested.


Given the result of the above, namely that almost surely:

$$Z_n \sim \sqrt{2 \log n} - \frac{\log \log n + \log (4 \pi)}{2 \sqrt{2 \log n}} - \frac{\log (\Xi_n)}{\sqrt{2 \log n}} \quad \implies \\ Z_n = \sqrt{2 \log n} - \frac{\log \log n + \log (4 \pi)}{2 \sqrt{2 \log n}} - \frac{\log (\Xi_n)}{\sqrt{2 \log n}} + o(1)\,. \tag{$\dagger$}$$

2. Then by linearity of expectation it follows that:

$$ \mathbb{E}Z_n = \sqrt{2 \log n} - \frac{\log \log n + \log (4 \pi)}{2 \sqrt{2 \log n}} - \frac{\mathbb{E}[\log (\Xi_n)]}{\sqrt{2 \log n}} + o(1) \quad \implies \\ \frac{\mathbb{E}Z_n}{\sqrt{2 \log n}} = 1 - \frac{\mathbb{E}[\log \Xi_n]}{2 \log n} + o(1) \,. $$

Therefore, we have shown that

$$ \lim_{n \to \infty } \frac{\mathbb{E} Z_n}{\sqrt{2 \log n}} = 1 \,,$$

as long as we can also show that

$$ \mathbb{E}[\log \Xi_n] = o(\log n) \,. $$

This might not be too difficult to show since again $\Xi_n$ has the same distribution for every continuous random variable. Thus we have the second result from above.

1. Similarly, we also have from the above that almost surely:

$$\frac{Z_n}{\sqrt{2 \log n}} = 1 - \frac{\log(\Xi_n)}{2 \log n} +o(1),.$$

Therefore, if we can show that:

$$ \log(\Xi_n) = o(\log n) \text{ almost surely}, \tag{*}$$

then we will have shown the first result from above. Result (*) would also clearly imply a fortiori that $\mathbb{E}[\log (\Xi_n)] = o(\log n)$, thereby also giving us the first result from above.

Also note that in the proof above of ($\dagger$) we needed to assume anyway that $\Xi_n = o(\log n)$ almost surely (or at least something similar), so that if we are able to show ($\dagger$) then we will most likely also have in the process needed to show $\Xi_n = o(\log n)$ almost surely, and therefore if we can prove $(\dagger)$ we will most likely be able to immediately reach all of the following conclusions.

3. However, if we have this result, then I don't understand how one would also have that $\mathbb{E}Z_n = \sqrt{2 \log n} + \Theta(1)$, since $o(1) \not= \Theta(1)$. But at the very least it would seem to be true that $$\mathbb{E}Z_n = \sqrt{2 \log n} + O(1) \,.$$


So then it seems that we can focus on answering the question of how to show that $$ \Xi_n = o(\log n) \text{ almost surely.} $$

We will also need to do the grunt work of providing a proof for (~), but to the best of my knowledge that is just calculus and involves no probability theory, although I have yet to sit down and try it yet.

First let's go through a chain of trivialities in order to rephrase the problem in a way which makes it easier to solve (note that by definition $\Xi_n \ge 0$):

$$\Xi_n = o(\log n) \quad \iff \quad \lim_{n \to \infty} \frac{\Xi_n}{\log n} = 0 \quad \iff \quad \\ \forall \varepsilon > 0, \frac{\Xi_n}{\log n} > \varepsilon \text{ only finitely many times} \quad \iff \\ \forall \varepsilon >0, \quad \Xi_n > \varepsilon \log n \text{ only finitely many times} \,.$$

One also has that:

$$\Xi_n > \varepsilon \log n \quad \iff \quad n(1 - F(Z_n)) > \varepsilon \log n \quad \iff \quad 1 - F(Z_n) > \frac{\varepsilon \log n}{n} \\ \iff \quad F(Z_n) < 1 - \frac{\varepsilon \log n}{n} \quad \iff \quad Z_n \le \inf \left\{ y: F(y) \ge 1 - \frac{\varepsilon \log n}{n} \right\} \,. $$

Correspondingly, define for all $n$:

$$ u_n^{(\varepsilon)} = \inf \left\{ y: F(y) \ge 1 - \frac{\varepsilon \log n}{n} \right\} \,. $$

Therefore the above steps show us that:

$$\Xi_n = o(\log n) \text{ a.s.} \quad \iff \quad \mathbb{P}(\Xi_n = o(\log n)) = 1 \quad \iff \quad \\ \mathbb{P}(\forall \varepsilon > 0 , \Xi_n > \varepsilon \log n \text{ only finitely many times}) = 1 \\ \iff \mathbb{P}(\forall \varepsilon > 0, Z_n \le u_n^{(\varepsilon)} \text{ only finitely many times}) = 1 \\ \iff \mathbb{P}(\forall \varepsilon >0, Z_n \le u_n^{(\varepsilon)} \text{ infinitely often}) =0 \,. $$

Notice that we can write:

$$ \{ \forall \varepsilon >0, Z_n \le u_n^{(\varepsilon)} \text{ infinitely often} \} = \bigcap_{\varepsilon > 0} \{ Z_n \le u_n^{(\varepsilon)} \text{ infinitely often} \} \,.$$

The sequences $u_n^{(\varepsilon)}$ become uniformly larger as $\varepsilon$ decreases, so we can conclude that the events $$\{ Z_n \le u_n^{(\varepsilon)} \text{ infinitely often} \} $$ are decreasing (or at least somehow monotonic) as $\varepsilon$ goes to $0$. Therefore the probability axiom regarding monotonic sequences of events allows us to conclude that:

$$\mathbb{P}(\forall \varepsilon >0, Z_n \le u_n^{(\varepsilon)} \text{ infinitely often}) = \\ \mathbb{P} \left( \bigcap_{\varepsilon > 0} \{ Z_n \le u_n^{(\varepsilon)} \text{ infinitely often} \} \right) = \\ \mathbb{P} \left( \lim_{\varepsilon \downarrow 0} \{ Z_n \le u_n^{(\varepsilon)} \text{ infinitely often} \} \right) = \\ \lim_{\varepsilon \downarrow 0} \mathbb{P}(Z_n \le u_n^{(\varepsilon)} \text{ infinitely often}) \,.$$

Therefore it suffices to show that for all $\varepsilon >0$,

$$\mathbb{P}(Z_n \le u_n^{(\varepsilon)} \text{ infinitely often}) = 0 $$

because of course the limit of any constant sequence is the constant.

Here is somewhat of a sledgehammer result:

Theorem 4.3.1., p. 252 of Galambos, The Asymptotic Theory of Extreme Order Statistics, 2nd edition. Let $X_1, X_2, \dots$ be i.i.d. variables with common nondegenerate and continuous distribution function $F(x)$, and let $u_n$ be a nondecreasing sequence such that $n(1 - F(u_n))$ is also nondecreasing. Then, for $u_n < \sup \{ x: F(x) <1 \}$, $$\mathbb{P}(Z_n \le u_n \text{ infinitely often}) =0 \text{ or }1 $$ according as $$\sum_{j=1}^{+\infty}[1 - F(u_j)]\exp(-j[1-F(u_j)]) < +\infty \text{ or }=+\infty \,. $$

The proof is technical and takes around five pages, but ultimately it turns out to be a corollary of one of the Borel-Cantelli lemmas. I may get around to trying to condense the proof to only use the part required for this analysis as well as only the assumptions which hold in the Gaussian case, which may be shorter (but maybe it isn't) and type it up here, but holding your breath is not recommended. Note that in this case $\omega(F)=+\infty$, so that condition is vacuous, and $n(1-F(n))$ is $\varepsilon \log n$ thus clearly non-decreasing.

Anyway the point being that, appealing to this theorem, if we can show that:

$$\sum_{j=1}^{+\infty}[1 - F(u_j^{(\varepsilon)})]\exp(-j[1-F(u_j^{(\varepsilon)})]) = \sum_{j=1}^{+\infty}\left[ \frac{\varepsilon \log j}{j} \right]\exp(-\varepsilon \log j) = \varepsilon \sum_{j=1}^{+\infty} \frac{ \log j}{j^{1 + \varepsilon}} < + \infty \,. $$

Note that since logarithmic growth is slower than any power law growth for any positive power law exponent (logarithms and exponentials are monotonicity preserving, so $\log \log n \le \alpha \log n \iff \log n \le n^{\alpha}$ and the former inequality can always be seen to hold for all $n$ large enough due to the fact that $\log n \le n$ and a change of variables), we have that:

$$ \sum_{j=1}^{+\infty} \frac{\log j}{j^{1 + \varepsilon}} \le \sum_{j=1}^{+\infty} \frac{j^{\varepsilon/2}}{j^{1 + \varepsilon}} = \sum_{j=1}^{+\infty} \frac{1}{j^{1 + \varepsilon/2}} < +\infty \,,$$

since the p-series is known to converge for all $p>1$, and $\varepsilon >0$ of course implies $1 + \varepsilon/2 > 1$.

Thus using the above theorem we have shown that for all $\varepsilon >0$, $\mathbb{P}(Z_n \le u_n^{(\varepsilon)} \text{ i.o.}) = 0$, which to recapitulate should mean that $\Xi_n = o(\log n)$ almost surely.

We need to show still that $\log \Xi_n = o(\log \log n)$. This doesn't follow from the above, since, e.g.,

$$ \frac{1}{n} \log n = o(\log n) \,, - \log n + \log \log n \not= o(\log n) \,. $$

However, given a sequence $x_n$, if one can show that $x_n = o( (\log n)^{\delta})$ for arbitrary $\delta >0$, then it does follow that $\log(x_n) = o(\log \log n)$. Ideally I would like to be able to show this for $\Xi_n$ using the above lemma (assuming it's even true), but am not able to (as of yet).

$\endgroup$

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.