The following problem comes from an old exam (introduction to probability). I have seen that there are similar questions on the forum, but most of them seem to be a bit more advanced and none of the answers I have found is truly elementary and short (and it should be the case, as this is an exam problem).
Let $X_n$ be the length of the longest run of heads in $n$ coin tosses. For example, if we obtain $$\textbf{HHTTHTHHHTH},$$ then $X_{11}=3.$ Prove that:
- $\mathbb{P}(X_n\ge \lambda\log_{2}n)\longrightarrow 0$ $\ \ \text{for} \ \lambda>1,$
- $\mathbb{P}(X_n\ge \lambda\log_{2}n)\longrightarrow 1$ $\ \ \text{for} \ 0<\lambda<1.$
I have failed in solving this exercise (after a long try). My first impression was that this is an exercise for the Borel-Cantelli lemma (but I am not so sure anymore). Do You know how to do this in an efficient way? Is this exercise rally about the $\textbf{B-C}$ $\textit{lemma}$ or something different? I will be glad for any insight or help.