Given i.i.d. with . Let . Prove that .

Probability Theory Solution – Problem 72: Prove that

Question

Given $(X_{i})_{i=1}^{\infty}$ i.i.d. with $X_{i}\sim N(0,1)$ . Let $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-by-step solution

Step 1. To prove that $\frac{M_{n}}{\sqrt{2\log n}}$ converges almost surely to 1, we need to show that for every $\epsilon > 0$ , both of the following hold: $\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. Equivalently, for every $\epsilon > 0$ , the following events have probability zero: $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. Prove $\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 bound: 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 for $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 the series $\sum_{n=1}^\infty P(A_n)$ converges by comparison with a $p$ -series. By the Borel--Cantelli lemma, $P(A_n \text{ i.o.}) = 0$ . Since this holds for every $\epsilon > 0$ : $\limsup_{n\to\infty} \frac{M_n}{\sqrt{2\log n}} \le 1$ a.s.

Step 3. Prove $\liminf_{n\to\infty} \frac{M_n}{\sqrt{2\log n}} \ge 1$ a.s. For $0 < \epsilon < 1$ , consider an exponentially growing subsequence $n_k = \lfloor \alpha^k \rfloor$ where $\alpha > 1$ . Let $d_n = (1-\epsilon)\sqrt{2\log n}$ . First show $P(M_{n_k} < d_{n_k} \text{ i.o.}) = 0$ . $P(M_{n_k} < d_{n_k}) = (P(X_1 < d_{n_k}))^{n_k} = (1 - P(X_1 > d_{n_k}))^{n_k}$ Using $1-x \le e^{-x}$ : $P(M_{n_k} < d_{n_k}) \le \exp(-n_k P(X_1 > d_{n_k}))$ Using the normal tail lower bound and setting $x_k = d_{n_k} = (1-\epsilon)\sqrt{2\log n_k}$ : $n_k P(X_1 > d_{n_k}) \sim \frac{n_k^{2\epsilon-\epsilon^2}}{(1-\epsilon)\sqrt{4\pi\log n_k}}$ Since $2\epsilon-\epsilon^2 = \epsilon(2-\epsilon) > 0$ , we have $n_k P(X_1 > d_{n_k}) \to \infty$ . Thus $P(M_{n_k} < d_{n_k})$ decays faster than any geometric series, so $\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$ .

Step 4. Extend from the subsequence to the full sequence. For any integer $n$ , find $k$ such that $n_k \le n < n_{k+1}$ . Since $M_n$ is nondecreasing, $M_n \ge M_{n_k}$ . For sufficiently large $n$ (hence $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}} = (1-\epsilon)\sqrt{\frac{\log n_k}{\log n}}$ Since $\frac{\log n_k}{\log n_{k+1}} \to 1$ as $k \to \infty$ , by the squeeze theorem $\frac{\log n_k}{\log n} \to 1$ . Therefore $\liminf_{n\to\infty} \frac{M_n}{\sqrt{2\log n}} \ge (1-\epsilon)$ . Since this holds for every $0 < \epsilon < 1$ : $\liminf_{n\to\infty} \frac{M_n}{\sqrt{2\log n}} \ge 1$ a.s.

Step 5. Combining 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. Both inequalities hold simultaneously, so the limit exists and equals 1, almost surely. $\lim_{n\to\infty} \frac{M_n}{\sqrt{2\log n}} = 1$ a.s.

Final answer

QED.

Marking scheme

The following is the marking rubric based on the official solution. Please follow this rubric strictly.

1. Checkpoints (Total 7 pts)

Divide the proof into the following three logical modules. Points within each module are additive, and points across modules are also additive.

Part 1: Upper bound estimate ( $\limsup_{n\to\infty} \frac{M_n}{\sqrt{2\log n}} \le 1$ a.s.) [Max 3]

Constructing the probability upper bound: Use the union bound $P(M_n > x) \le nP(X_1 > x)$ combined with the normal tail estimate ( $P(X>x) \le e^{-x^2/2}/x$ or similar form) to establish an inequality for $P(M_n > (1+\epsilon)\sqrt{2\log n})$ . [1 pt]
Series convergence analysis: Substitute $x_n = (1+\epsilon)\sqrt{2\log n}$ , and through algebraic manipulation show that the probability term decays at rate $n^{-p}$ (or similar form), then argue that $\sum P(A_n)$ converges. [1 pt]
Borel--Cantelli conclusion: Invoke the first part of the Borel--Cantelli lemma to conclude that for every $\epsilon>0$ , $\limsup \le 1+\epsilon$ holds almost surely. [1 pt]
*Note: If the student uses a subsequence method to prove the upper bound and the logic is correct, full credit is also awarded.*

Part 2: Lower bound subsequence estimate ( $\liminf_{n\to\infty} \frac{M_n}{\sqrt{2\log n}} \ge 1$ a.s.) [Max 2]

Subsequence and probability bounding: Choose an exponentially growing subsequence $n_k$ (e.g., $\alpha^k$ ), and use the independence formula $(1-p)^n \le e^{-np}$ to bound the event $\{M_{n_k} < (1-\epsilon)\sqrt{2\log n_k}\}$ . [1 pt]
Subsequence convergence conclusion: Prove that the corresponding probability series converges, and by the Borel--Cantelli lemma assert that $M_{n_k} \ge (1-\epsilon)\sqrt{2\log n_k}$ eventually holds almost surely. [1 pt]

Part 3: Density extension and combined conclusion (Extension to full sequence) [Max 2]

Using monotonicity to fill gaps: Use the nondecreasing property of $M_n$ to state that for $n_k \le n < n_{k+1}$ , we have $M_n \ge M_{n_k}$ . [1 pt]
Squeeze limit argument: By arguing that $\frac{\sqrt{\log n_k}}{\sqrt{\log n_{k+1}}} \to 1$ (or a similar ratio limit), extend the subsequence lower bound to the full sequence, and combine with Part 1 to state the final conclusion. [1 pt]

Total (max 7)

2. Zero-credit items

Merely copying the problem statement or listing the given conditions ( $X_i \sim N(0,1)$ ).
Only computing the limit of $E[M_n]$ or $\text{Var}(M_n)$ without addressing the probability series criterion for almost sure convergence.
Only citing the name "extreme value theory" or "Gumbel distribution" without any concrete series convergence proof.
Incorrectly asserting $X_n \to \infty$ or $X_n \to 0$ almost surely.

3. Deductions

For clear logical gaps or writing errors, apply the following single maximum deduction:

Missing logical quantifiers: The proof does not reflect "for every $\epsilon > 0$ " or fails to let $\epsilon \to 0$ at the end, making the conclusion imprecise. (-1 pt)
Confusing convergence types: Proves convergence in probability ( $P(|\dots|>\epsilon) \to 0$ ) but does not verify series convergence (i.e., does not sufficiently prove almost sure convergence). (cap at 4/7)
Skipping the subsequence step: In the lower bound proof, directly applies the Borel--Cantelli lemma to all $n$ (which typically causes the series to diverge, a logical error) without using a subsequence. (-2 pts)
Missing monotonicity: When extending from the subsequence to the full sequence, fails to mention the monotonicity of $M_n$ and directly assumes the limit exists. (-1 pt)

Probability Theory – Problem 72: Prove that