Probability Theory – Problem 44: Prove that

Let $(X_{i})_{i=1}^{\infty}$ be i.i.d. with $X_{i}\sim N(0,1)$. Define $M_{n}=\operatorname*{max}_{1\leqslant i\leqslant n}\left\{X_{1},\ldots,X_{n}\right\}$. Prove that $\frac{M_{n}}{\sqrt{2\log n}}\stackrel{a.s.}{\rightarrow}1$.

Step 1. To prove that $\frac{M_{n}}{\sqrt{2\log n}}$ converges almost surely to 1, we need to show that for any $\epsilon > 0$, both of the following hold: $\limsup_{n\to\infty} \frac{M_n}{\sqrt{2\log n}} \le 1$ $\liminf_{n\to\infty} \frac{M_n}{\sqrt{2\log n}} \ge 1$ Equivalently, we prove that for any $\epsilon > 0$: $P\left(\frac{M_n}{\sqrt{2\log n}} > 1+\epsilon \quad \text{i.o.}\right) = 0$ $P\left(\frac{M_n}{\sqrt{2\log n}} < 1-\epsilon \quad \text{i.o.}\right) = 0$ where i.o. stands for "infinitely often."

Step 2. Proof that $\limsup_{n\to\infty} \frac{M_n}{\sqrt{2\log n}} \le 1$ a.s. By the Borel--Cantelli lemma, if a sequence of events $A_n$ satisfies $\sum_{n=1}^\infty P(A_n) < \infty$, then $P(A_n \text{ i.o.}) = 0$. Let $A_n = \left\{ \frac{M_n}{\sqrt{2\log n}} > 1+\epsilon \right\}$ for a given $\epsilon > 0$. $P(A_n) = P(M_n > (1+\epsilon)\sqrt{2\log n})$ Since $M_n = \max\{X_1, \dots, X_n\}$, the event $\{M_n > x\}$ equals $\cup_{i=1}^n \{X_i > x\}$. By the union bound: $P(M_n > (1+\epsilon)\sqrt{2\log n}) \le \sum_{i=1}^n P(X_i > (1+\epsilon)\sqrt{2\log n})$ Since the $X_i$ are i.i.d.: $P(A_n) \le n P(X_1 > (1+\epsilon)\sqrt{2\log n})$ Using the standard normal tail probability estimate: for $x>0$, $P(X_1 > x) < \frac{1}{x\sqrt{2\pi}}e^{-x^2/2}$. Let $x_n = (1+\epsilon)\sqrt{2\log n}$. Then $x_n^2 = (1+\epsilon)^2(2\log n)$. $P(X_1 > x_n) < \frac{1}{(1+\epsilon)\sqrt{2\log n}\sqrt{2\pi}} e^{-(1+\epsilon)^2\log n} = \frac{1}{(1+\epsilon)\sqrt{4\pi\log n}} n^{-(1+\epsilon)^2}$ Substituting into the bound on $P(A_n)$: $P(A_n) \le n \cdot \frac{1}{(1+\epsilon)\sqrt{4\pi\log n}} n^{-(1+\epsilon)^2} = \frac{1}{(1+\epsilon)\sqrt{4\pi\log n}} n^{1-(1+\epsilon)^2}$ The exponent is $1-(1+\epsilon)^2 = 1-(1+2\epsilon+\epsilon^2) = -2\epsilon-\epsilon^2$. Since $\epsilon > 0$, the exponent $-2\epsilon-\epsilon^2$ is negative. Therefore, each term of $\sum_{n=1}^\infty P(A_n)$ is bounded by $C \frac{n^{-p}}{\sqrt{\log n}}$ where $p = 2\epsilon+\epsilon^2 > 0$. By comparison with the $p$-series, the sum converges. So $\sum_{n=1}^\infty P(A_n) < \infty$. By the Borel--Cantelli lemma, $P(A_n \text{ i.o.}) = 0$. This means that almost surely, the event $\frac{M_n}{\sqrt{2\log n}} > 1+\epsilon$ occurs only finitely many times. Since this holds for any $\epsilon > 0$, we conclude: $\limsup_{n\to\infty} \frac{M_n}{\sqrt{2\log n}} \le 1$ a.s.

Step 3. Proof that $\liminf_{n\to\infty} \frac{M_n}{\sqrt{2\log n}} \ge 1$ a.s. We need to show that for any $0 < \epsilon < 1$, $P\left(\frac{M_n}{\sqrt{2\log n}} < 1-\epsilon \quad \text{i.o.}\right) = 0$. Equivalently, almost surely, for all sufficiently large $n$, $\frac{M_n}{\sqrt{2\log n}} \ge 1-\epsilon$. Consider an exponentially growing subsequence $n_k = \lfloor \alpha^k \rfloor$, where $\alpha > 1$ is a constant to be determined. Let $d_n = (1-\epsilon)\sqrt{2\log n}$. We first prove $P(M_{n_k} < d_{n_k} \text{ i.o.}) = 0$. $P(M_{n_k} < d_{n_k}) = P(X_1 < d_{n_k}, \dots, X_{n_k} < d_{n_k}) = (P(X_1 < d_{n_k}))^{n_k} = (1 - P(X_1 > d_{n_k}))^{n_k}$ Using the inequality $1-x \le e^{-x}$: $P(M_{n_k} < d_{n_k}) \le \exp(-n_k P(X_1 > d_{n_k}))$ Using the lower bound for the standard normal tail probability: for $x>0$, $P(X_1 > x) > (\frac{1}{x}-\frac{1}{x^3})\frac{1}{\sqrt{2\pi}}e^{-x^2/2}$. For sufficiently large $x$, $P(X_1 > x) \sim \frac{1}{x\sqrt{2\pi}}e^{-x^2/2}$. Let $x_k = d_{n_k} = (1-\epsilon)\sqrt{2\log n_k}$. $n_k P(X_1 > d_{n_k}) \sim n_k \frac{1}{(1-\epsilon)\sqrt{4\pi\log n_k}} e^{-(1-\epsilon)^2\log n_k} = \frac{n_k}{(1-\epsilon)\sqrt{4\pi\log n_k}} n_k^{-(1-\epsilon)^2}$ $= \frac{1}{(1-\epsilon)\sqrt{4\pi\log n_k}} n_k^{1-(1-2\epsilon+\epsilon^2)} = \frac{n_k^{2\epsilon-\epsilon^2}}{(1-\epsilon)\sqrt{4\pi\log n_k}}$ Since $0 < \epsilon < 1$, the exponent $2\epsilon-\epsilon^2 = \epsilon(2-\epsilon) > 0$. Therefore, as $k \to \infty$, $n_k P(X_1 > d_{n_k}) \to \infty$. Hence $P(M_{n_k} < d_{n_k})$ decays faster than any geometric series. Therefore, the series $\sum_{k=1}^\infty P(M_{n_k} < d_{n_k})$ converges. By the Borel--Cantelli lemma, $P(M_{n_k} < d_{n_k} \text{ i.o.}) = 0$. That is, almost surely, there exists $K(\omega)$ such that for all $k > K(\omega)$, $M_{n_k} \ge d_{n_k}$.

Step 4. Extension from the subsequence to the full sequence. For any integer $n$, there exists $k$ such that $n_k \le n < n_{k+1}$. Since $M_n$ is non-decreasing, $M_n \ge M_{n_k}$. For sufficiently large $n$ (so that $k > K(\omega)$): $\frac{M_n}{\sqrt{2\log n}} \ge \frac{M_{n_k}}{\sqrt{2\log n}} \ge \frac{d_{n_k}}{\sqrt{2\log n}} = \frac{(1-\epsilon)\sqrt{2\log n_k}}{\sqrt{2\log n}} = (1-\epsilon)\sqrt{\frac{\log n_k}{\log n}}$ Since $n_k \le n < n_{k+1}$, we have $\log n_k \le \log n < \log n_{k+1}$. Therefore $\frac{\log n_k}{\log n_{k+1}} < \frac{\log n_k}{\log n} \le 1$. As $k \to \infty$, $\frac{\log n_k}{\log n_{k+1}} = \frac{\log \lfloor \alpha^k \rfloor}{\log \lfloor \alpha^{k+1} \rfloor} \approx \frac{k\log\alpha}{(k+1)\log\alpha} \to 1$. By the squeeze theorem, as $n \to \infty$, $\frac{\log n_k}{\log n} \to 1$. So for any $\delta > 0$, when $n$ is sufficiently large, $\sqrt{\frac{\log n_k}{\log n}} > 1-\delta$. Therefore, $\liminf_{n\to\infty} \frac{M_n}{\sqrt{2\log n}} \ge (1-\epsilon)(1-\delta)$. Since $\delta$ can be arbitrarily small, $\liminf_{n\to\infty} \frac{M_n}{\sqrt{2\log n}} \ge 1-\epsilon$. Since this holds for any $0 < \epsilon < 1$, we conclude: $\liminf_{n\to\infty} \frac{M_n}{\sqrt{2\log n}} \ge 1$ a.s.

Step 5. Combined conclusion. Combining the results of Steps 2 and 4: $\limsup_{n\to\infty} \frac{M_n}{\sqrt{2\log n}} \le 1$ a.s. $\liminf_{n\to\infty} \frac{M_n}{\sqrt{2\log n}} \ge 1$ a.s. These two inequalities together imply that the limit exists and equals 1, almost surely. $\lim_{n\to\infty} \frac{M_n}{\sqrt{2\log n}} = 1$ a.s.

QED.