# Why is the maximum of i.i.d. Gaussians asymptotically $\sqrt{2 \log n}$?

Assuming that $$\xi$$ is bounded (as a function of $$x$$?), the claim is that given the equation:

$$\xi \frac{\sqrt{2\pi}}{n} = \frac{1}{x} e^{-\frac{x^2}{2}} \left( 1 + O\left(\frac{1}{x^2} \right) \right)$$

one can solve ("after some calculation") for $$x$$ to get:

$$x = \sqrt{2 \log n} - \frac{\log \log n + \log 4 \pi}{2 \sqrt{2 \log n}} - \frac{\log \xi}{\sqrt{2 \log n}} + O\left( \frac{1}{\log n} \right) \,.$$

Question: Would it be possible to get some hints about how to solve for $$x$$ in this situation?

There are several issues about this which I don't understand:

• How is the assumption that $$\xi$$ is bounded used or otherwise relevant?
• Why is the "imprecise knowledge of $$x$$ transferred to $$n$$" when solving for $$x$$, and not "transferred" to some other variable? If we require an assumption on $$\xi$$, then why isn't the "imprecise knowledge transferred" to $$\xi$$? (Why don't we get an $$O(f(\xi))$$ term for some $$f$$?
• Do we have to use/calculate some inverse function to $$g(x) := \frac{1}{x} e^{-\frac{x^2}{2}}$$? This function isn't even defined, strictly speaking, at $$x=0$$, but perhaps it has a continuous extension over the entire real line? If it does have a continuous extension over $$\mathbb{R}$$, is that continuous extension even an invertible function, such that talking about $$g^{-1}(x)$$ even makes sense?
• If we do calculate such an inverse function, do we then basically proceed by applying that function to both sides of the equation and ignoring the $$O(x^{-2})$$ term, with the understanding that the "uncertainty" contained within it now needs to be transferred somewhere else? If so, this leads back to the above question about where the $$O((\log n)^{-1})$$ term could come from.

Context: I don't think the context is actually relevant to solving this problem, but for the record this comes up on p. 374 of Cramer's 1946 Mathematical Methods of Statistics where an asymptotic form for the maximum of i.i.d. Gaussian random variables is sought.

• What is $\xi$, and what does any of this have to do with iid gaussians? Nov 26, 2018 at 19:49
• @MikeHawk $\xi$ is a scaled version of the survivor function of the maximum $X$, $n(1 - F(x))$, with $F$ the CDF. The idea is similar to the inverse sampling transform, i.e. $F(X) \sim \operatorname{Uniform}(0,1)$. More specifically, the idea is that $n(1-F(x)) = \xi$ always has a certain relatively simple distribution which is easier to analyze than directly analyzing the distribution of $X$. See p. 370 of the book in question (the notation is really difficult to understand, so you might have to read it multiple times before it starts to make sense, it took me like 10+ times). Nov 29, 2018 at 2:46

You are correct, essentially this is an asymptotic expansion for the inverse of the survival function of the standard normal distribution. The first equation holds for $$x \to \infty$$, we are not concerned with the behavior of $$n(x)$$ around $$x = 0$$. We're looking for an expansion of $$x(n)$$ when $$n \to \infty$$, which can be obtained by applying the method of dominant balance. Taking logarithms gives $$- \ln n + \ln(\xi \sqrt {2 \pi}) \approx -\frac {x^2} 2 - \ln x.$$ Since $$\xi$$ is bounded, the dominant terms are $$-\ln n$$ and $$-x^2/2$$, from which we get the first approximation $$x = \sqrt {2 \ln n}$$. Then we look for the next approximation of the form $$x = \sqrt{2 \ln n} \,(1 + \alpha), \,\alpha = o(1)$$: $$-\ln n + \underbrace {\ln(\xi \sqrt{2 \pi})}_{O(1)} \approx -\underbrace {(1 + \alpha)^2 \ln n}_{(1 + 2 \alpha) \ln n + o(\alpha \ln n)} - \underbrace {\ln \sqrt {2 \ln n}}_{\ln (\ln n)/2 + O(1)} - \underbrace {\ln(1 + \alpha)}_{o(1)}, \\ 0 \approx - 2 \alpha \ln n - \frac {\ln \ln n} 2,$$ which gives $$\alpha = -\ln(\ln n)/(4 \ln n).$$ In the same way, the next step is $$x = \sqrt {2 \ln n} - \frac {\ln \ln n} {2 \sqrt {2 \ln n}} (1 + \alpha), \\ x^2 = 2 \ln n - (1 + \alpha) \ln \ln n + o(1), \quad \ln x = \ln \sqrt {2 \ln n} + o(1), \\ \ln( \xi \sqrt {2 \pi}) \approx \frac {(1 + \alpha) \ln \ln n} 2 - \ln \sqrt {2 \ln n}, \\ \alpha = \frac {\ln 4 \pi \xi^2} {\ln \ln n}.$$
• Great answer! In the second line, underneath the curly brackets, $O(1)$, $(1 + 2 \alpha) \ln n + o(\alpha \ln n)$, $\ln(\ln n)/2 + O(1)$, and $o(1)$ are in the limit as $n \to \infty \iff x \to \infty$? I guess I don't understand which terms aren't negligible which weren't negligible before, since in the first line $\alpha$ itself would have been negligible as it is $o(1)$. And why are the $O(1)$ terms negligible in the second line? Dec 3, 2018 at 0:02
• Correct, everything is for large $n$ and large $x$. Which means that in the line with the curly brackets, after $\ln n$ cancels out, we still have an unbounded term $\ln \ln n$, which dominates the bounded terms. $o(\alpha \ln n)$ is dominated by $\alpha \ln n$. We are left with two dominant terms, which need to be balanced. Dec 3, 2018 at 6:36
• Ah, OK, since $O(1) = o(n)$, and we can't automatically assume that $\alpha \ln n$ is of larger or smaller order than $\ln\ln n$, since $\alpha$ is an "unknown" rate, so we need to balance it instead. So we always look at all of the terms with the unknown and of them discard all but the dominant (leading order) term, look at the terms without the unknown and of them discard all but the dominant term, then "balance" the dominant term with the unknown and the dominant term without the unknown by solving for the unknown? Which is probably why it's called the method of "dominant balance"? Dec 3, 2018 at 16:29
• @hasManyStupidQuestions There might be a simpler way, but if we carry out one more step of the expansion, we'll get that the next term grows as $\ln^2 (\ln n)/\ln^{3/2} n$. Dec 4, 2018 at 10:41