Probability Theory – Problem 19: Prove that: (1)

Let $X_{1},\cdot\cdot\cdot X_{n}$ be i.i.d. random variables satisfying $\mathbb{P}(X_{i}\;>\;x)\;=\;e^{-x}$, and let $M_{n}\;=$$\operatorname*{max}_{1\leq m\leq n}X_{m}$. Prove that: (1) $\operatorname*{lim}_{n\to\infty}\operatorname*{sup}_{M_{n}}\frac{X_{n}}{\log n}=1\quad\mathrm{~a.s.}$ (2) $\operatorname*{lim}_{n\to\infty}\frac{M_{n}}{\log n}=1\quad\mathrm{~a.s.}$

(1) Proof that $\limsup_{n \to \infty} \frac{X_n}{\log n} = 1 \quad \text{a.s.}$

Step 1. Prove that $\limsup_{n \to \infty} \frac{X_n}{\log n} \le 1$ a.s. By the definition of the limit superior, it suffices to show that for every $\epsilon > 0$, the event $\left\{ \frac{X_n}{\log n} > 1 + \epsilon \right\}$ can occur only finitely many times (almost surely). By the first Borel–Cantelli lemma, it suffices to show that the series $\sum_{n=1}^\infty P\left(\frac{X_n}{\log n} > 1 + \epsilon\right)$ converges. Using the given condition $P(X_i > x) = e^{-x}$, we compute the probability: $P\left(\frac{X_n}{\log n} > 1 + \epsilon\right) = P(X_n > (1+\epsilon)\log n)$ Setting $x = (1+\epsilon)\log n$ and substituting into the tail probability formula: $P(X_n > (1+\epsilon)\log n) = e^{-(1+\epsilon)\log n} = (e^{\log n})^{-(1+\epsilon)} = n^{-(1+\epsilon)}$ Consider the series $\sum_{n=1}^\infty n^{-(1+\epsilon)}$. Since $\epsilon > 0$, we have $1+\epsilon > 1$. This is a $p$-series with $p = 1+\epsilon > 1$, and therefore it converges. By the first Borel–Cantelli lemma, the probability that the event $\left\{ \frac{X_n}{\log n} > 1 + \epsilon \right\}$ occurs infinitely often is zero. That is, almost surely, for every $\epsilon > 0$, $\limsup_{n \to \infty} \frac{X_n}{\log n} \le 1 + \epsilon$. Since $\epsilon$ can be taken arbitrarily small, we conclude that $\limsup_{n \to \infty} \frac{X_n}{\log n} \le 1$ a.s.

Step 2. Prove that $\limsup_{n \to \infty} \frac{X_n}{\log n} \ge 1$ a.s. It suffices to show that for every $0 < \epsilon < 1$, the event $\left\{ \frac{X_n}{\log n} > 1 - \epsilon \right\}$ occurs infinitely often (almost surely). Since the $X_n$ are i.i.d., the events $A_n = \left\{ \frac{X_n}{\log n} > 1 - \epsilon \right\}$ are mutually independent. By the second Borel–Cantelli lemma, if $\sum_{n=1}^\infty P(A_n)$ diverges, then $P(A_n \text{ i.o.}) = 1$. We compute $P(A_n)$: $P(A_n) = P\left(\frac{X_n}{\log n} > 1 - \epsilon\right) = P(X_n > (1-\epsilon)\log n)$ $= e^{-(1-\epsilon)\log n} = n^{-(1-\epsilon)}$ Consider the series $\sum_{n=1}^\infty n^{-(1-\epsilon)}$. Since $0 < \epsilon < 1$, we have $1-\epsilon < 1$. This is a $p$-series with $p = 1-\epsilon < 1$, and therefore it diverges. By the second Borel–Cantelli lemma, the probability that the event $A_n$ occurs infinitely often is $1$. That is, almost surely, for every $0 < \epsilon < 1$, $\limsup_{n \to \infty} \frac{X_n}{\log n} \ge 1 - \epsilon$. Since $\epsilon$ can be taken arbitrarily small, we conclude that $\limsup_{n \to \infty} \frac{X_n}{\log n} \ge 1$ a.s.

Step 3. Combining the conclusions of Step 1 and Step 2, namely $\limsup_{n \to \infty} \frac{X_n}{\log n} \le 1$ a.s. and $\limsup_{n \to \infty} \frac{X_n}{\log n} \ge 1$ a.s.

(2) Proof that $\lim_{n \to \infty} \frac{M_n}{\log n} = 1 \quad \text{a.s.}$ To show that the limit exists and equals $1$, we must prove separately that the limit superior is at most $1$ and the limit inferior is at least $1$.

Step 4. Prove that $\limsup_{n \to \infty} \frac{M_n}{\log n} \le 1$ a.s. $M_n = \max_{1 \le m \le n} X_m$ is a non-decreasing sequence. From the proof of part (1), we know that $\limsup_{n \to \infty} \frac{X_n}{\log n} = 1$ a.s. This means that for almost every sample point, for any given $\delta > 0$, there exists a positive integer $N$ such that $X_n < (1+\delta)\log n$ for all $n > N$. For any $n > N$, we can decompose $M_n$ as: $M_n = \max(X_1, \ldots, X_N, X_{N+1}, \ldots, X_n)$ $M_n \le \max(\max(X_1, \ldots, X_N), \max(X_{N+1}, \ldots, X_n))$ Let $C = \max(X_1, \ldots, X_N)$, which is a finite random variable. For $m > N$, we have $X_m < (1+\delta)\log m \le (1+\delta)\log n$. Therefore, $\max(X_{N+1}, \ldots, X_n) < (1+\delta)\log n$. Hence, for $n > N$, $M_n < \max(C, (1+\delta)\log n)$. Dividing both sides by $\log n$: $\frac{M_n}{\log n} < \frac{\max(C, (1+\delta)\log n)}{\log n} = \max\left(\frac{C}{\log n}, 1+\delta\right)$ As $n \to \infty$, $\frac{C}{\log n} \to 0$. Therefore, for all sufficiently large $n$, $\frac{M_n}{\log n} < 1+\delta$. This implies $\limsup_{n \to \infty} \frac{M_n}{\log n} \le 1+\delta$. Since $\delta$ is an arbitrary positive number, we conclude that $\limsup_{n \to \infty} \frac{M_n}{\log n} \le 1$ a.s.

Step 5. Prove that $\liminf_{n \to \infty} \frac{M_n}{\log n} \ge 1$ a.s. It suffices to show that for every $0 < \epsilon < 1$, the event $\left\{ \frac{M_n}{\log n} < 1 - \epsilon \right\}$ can occur only finitely many times (almost surely). By the first Borel–Cantelli lemma, it suffices to show that the series $\sum_{n=1}^\infty P\left(\frac{M_n}{\log n} < 1 - \epsilon\right)$ converges. We compute the probability: $P\left(\frac{M_n}{\log n} < 1 - \epsilon\right) = P(M_n < (1-\epsilon)\log n)$ $= P(\max(X_1, \ldots, X_n) < (1-\epsilon)\log n)$ Since the $X_i$ are i.i.d., this equals: $= P(X_1 < (1-\epsilon)\log n, \ldots, X_n < (1-\epsilon)\log n)$ $= [P(X_1 < (1-\epsilon)\log n)]^n$ Since $P(X_1 < x) = 1 - P(X_1 > x) = 1 - e^{-x}$, the probability becomes: $= [1 - e^{-(1-\epsilon)\log n}]^n = [1 - n^{-(1-\epsilon)}]^n$ As $n \to \infty$, let $u_n = n^{-(1-\epsilon)}$, so that $u_n \to 0$. Using the limit $(1-x)^{1/x} \to e^{-1}$, we obtain: $[1 - n^{-(1-\epsilon)}]^n = \left( [1 - n^{-(1-\epsilon)}]^{\frac{1}{n^{-(1-\epsilon)}}} \right)^{n \cdot n^{-(1-\epsilon)}} \approx (e^{-1})^{n^\epsilon} = e^{-n^\epsilon}$ Consider the series $\sum_{n=1}^\infty e^{-n^\epsilon}$. Since $\epsilon > 0$, $n^\epsilon$ grows with $n$, so $e^{-n^\epsilon}$ tends to zero extremely rapidly, faster than any polynomial $n^{-p}$ ($p>1$). For example, comparing with the convergent series $\sum \frac{1}{n^2}$, we have $\lim_{n\to\infty} \frac{e^{-n^\epsilon}}{1/n^2} = \lim_{n\to\infty} \frac{n^2}{e^{n^\epsilon}} = 0$. Therefore, the series $\sum_{n=1}^\infty e^{-n^\epsilon}$ converges. By the first Borel–Cantelli lemma, the probability that the event $\left\{ \frac{M_n}{\log n} < 1 - \epsilon \right\}$ occurs infinitely often is zero. That is, almost surely, for every $0 < \epsilon < 1$, $\liminf_{n \to \infty} \frac{M_n}{\log n} \ge 1 - \epsilon$. Since $\epsilon$ can be taken arbitrarily small, we conclude that $\liminf_{n \to \infty} \frac{M_n}{\log n} \ge 1$ a.s.

Step 6. Combining the conclusions of Step 4 and Step 5, namely $\limsup_{n \to \infty} \frac{M_n}{\log n} \le 1$ a.s. and $\liminf_{n \to \infty} \frac{M_n}{\log n} \ge 1$ a.s., we obtain the final conclusion.

QED.