Probability of $\limsup_n\left\{|\frac{\max_{1\leq k \leq n}X_k}{\ln(n)}-1| >\epsilon\right\}$

Question

Let $(X_n)_n$ be a sequence of independent random variables and identically distributed, following the exponential distribution with parameter 1.

Let $0<\epsilon<1.$ I want to compute $P\left(\limsup_n\left\{\left|\frac{\max_{1\leq k \leq n}X_k}{\ln(n)}-1\right| >\epsilon\right\}\right)$

I am thankful for any idea.

Answer 1

Claim

Let $\{X_k\}_{k=1}^{\infty}$ be i.i.d. exponentially distributed random variables with parameter $\lambda=1$. Define $M_n = \max_{\{k : 1 \leq k \leq n\}}X_k$. Then: $$\lim_{n\rightarrow\infty} \frac{M_n}{\log(n)} = 1 \quad \mbox{(with prob 1)} $$

Derivation

Fix $\epsilon>0$. Then $$ \{|M_n/\log(n) - 1| > \epsilon\} = \underbrace{\{\{M_n < \log(n^{1-\epsilon})\}}_{\mbox{type 1}} \cup \underbrace{\{M_n> \log(n^{1+\epsilon})\}}_{\mbox{type 2}} $$

Set Type 1:

Indeed $P[M_n < \log(n^{1-\epsilon})]= (1-\frac{1}{n^{1-\epsilon}})^n \approx exp(-n^\epsilon)$. This is summable (as Clement C notes above) and so by Borel-Cantelli we can conclude that, with prob 1, at most finitely many of the events $\{M_n < \log(n^{1-\epsilon})\}$ occur.

Set Type 2:

Indeed $P[M_n > \log(n^{1+\epsilon})] = 1-(1-\frac{1}{n^{1+\epsilon}})^n$. This case is more tricky since indeed these are not summable over all $n$. Nevertheless there is a nice technique of summing over the sparse subsequence of indices of the form $2^k$:

$$ \sum_{k=1}^{\infty} P\left[M_{2^k}>\log\left((2^k)^{1+\epsilon}\right)\right] = \sum_{k=1}^{\infty}\left[1 - \left(1 - \frac{1}{(2^k)^{1+\epsilon}}\right)^{2^k}\right] $$ This sum is not trivial to evaluate, but indeed it is finite.

Wait a minute, you say, what about the $M_n$ values for indices $n$ that are not powers of 2? Well, for any $n$ that satisfies $2^k \leq n \leq 2^{k+1}$ we can say: $$ \frac{M_n}{\log(n)} \leq \frac{M_{2^{k+1}}}{\log(2^k)}$$ So $$ \cup_{\{n : 2^k\leq n \leq 2^{k+1}\}}\left\{\frac{M_n}{\log(n)}>1+\epsilon\right\} \subseteq \left\{ \frac{M_{2^{k+1}}}{\log(2^k)} > 1+\epsilon\right\} $$ so it remains to compute $$ \sum_{k=1}^{\infty} P\left[\frac{M_{2^{k+1}}}{\log(2^k)}>1+\epsilon \right] = \sum_{k=1}^{\infty} \left[1 - \left(1-\frac{1}{2^{k(1+\epsilon)}}\right)^{2^{k+1}} \right]$$ This sum is similar to the previous one and is also finite.

So, with prob 1, at most finitely many type 2 events occur.