# Big O computation, exponential extreme law

I have a concrete computational problem where I do not really know how to procede , probably since I am not very comfortable with big O notation. The problem is taken from an old exam question - without suggested solutions unfortunately.

I am given an iid sequence, $(X_i)$ of $exp(1)$ random variables, where we define $M_n=\max_{i\leq n} X_i$. I want to show that $M_n/\ln n$ converges to $1$ almost surely. I am given the hints, to show the following identities (from which the result then quite easily follows by Borel-Cantelli)

$$P(M_n \leq (1-\epsilon)\ln n)=\exp(-n^{\epsilon}(1+O(1)),$$ and $$P(M_{2^k} \geq (1-\epsilon)\ln 2^k)=2^{-k\epsilon}(1+O(1)).$$

My attempt is basically to procede by observing that since the $X_i$ are iid we have $$P(M_n\leq (1-\epsilon)\ln x)=(1-e^{-(1-\epsilon)\ln x})^n=\left(1-\frac{1}{x^{1-\epsilon}} \right)^n$$ and fair enough, this sort of looks like it should behave exponentially (since for $\epsilon =0$ the obviously converges $e^{-x}$), but I do not really know how to procede from here.

Edit: To be perfectly clear, I am interested in the proof of the two identities and not really about how to reach the end result (of a.s. convergence), since this follows, as noted, by the two identities.

Any help will be warmly appreciated.

• The a.s. part is a bit trickier, but convergence in probability should be simple: you have $P(M_n \leq x)=P(\cap_{i=1}^n (X_i \leq x))=(1-e^{-x})^n$. Replace $x$ with $x \ln(n)$ and compute the pointwise limit as $n \to \infty$. (It will help to split into the cases $x<1,x=1,x>1$.) That should give you some idea how to proceed to get a.s. convergence.
– Ian
Apr 21 '17 at 13:28
• Thank you, I actually already proved convergence in probability. The question is about almost sure convergence and rather about how to show the identitites above than the actual main result. I clarified the question in an edit above. Note also that the two inequalities actually correspond to $\leq 1, \geq 1$ respectively. Apr 21 '17 at 14:11
• But the identities are proven in just the same way as this pointwise limit is calculated: $(1-n^{-x})^n=e^{n \log(1-n^{-x})}=e^{-n^{1-x}+O(n^{1-2x})}$. Plug in $x=1-\epsilon$ to change to the form you are using.
– Ian
Apr 21 '17 at 14:17
• Oh. Yeah, I did not see the possibility for that rewrite. Thank you! Apr 21 '17 at 14:20
• The point here is that Borel-Cantelli says that if $p_n(\epsilon):=P(|X_n - X| \geq \epsilon)$ is summable for all $\epsilon > 0$ then $X_n \to X$ a.s. This idea is used in a few different places in analysis, for example Royden/Fitzpatrick use it (in a slightly different form) to prove that the $L^p$ spaces are complete.
– Ian
Apr 21 '17 at 14:31

These estimates can be proven by noting that $P(M_n \leq x)=(1-e^{-x})^n$ for $x>0$. Replacing $x$ with $x \ln(n)$ gives $P(M_n/\ln(n) \leq x)=(1-n^{-x})^n=e^{n \log(1-n^{-x})}$. Expanding the logarithm and then the exponential gives the desired estimates.