Consider an infinite Bernoulli process with \(p=0.5\), that is, an infinite sequence of random variables \(\left\{Y_{i}, i \in \mathbb{Z}\right\}\) with \(\mathbf{P}\left(Y_{i}=0\right)=\mathbf{P}\left(Y_{i}=1\right)=0.5\), for all \(i \in \mathbb{Z}\). We would like to study the length of the maximum sequence of 1's. Let

\[l_{m}=\max \left\{i \geq 1: X_{m-i+1}=\cdots=X_{m}=1\right\}\]

be the length of the run of 1's up to the \(m\)-th toss and including it. Obviously, \(l_{m}\) will be 0 if the \(m\)-th toss is a tail. We are interested in the asymptotic behavior of the longest run from 1 to \(n\) for large \(n\).

That is we are interested in the behavior of \(L_{n}\) where

\[\begin{aligned}L_{n} & =\max _{m \in\{1, \ldots, n\}} l_{m} \\& =\max \left\{i \geq 1: X_{m-i+1}=\cdots=X_{m}=1, \text { for some } m \in\{1, \ldots, n\}\right\}\end{aligned}\]

(a) Explain why \(\mathbf{P}\left(l_{m}=i\right)=2^{-(i+1)}\), for \(i=0,1,2, \ldots\) and for any \(m\).

(b) Apply the first Borel-Cantelli lemma to the events

\[A_{n}=\left\{l_{n}>(1+\varepsilon) \log _{2} n\right\}\]

Conclude that for each \(\varepsilon>0\), with probability one, \(l_{n} \leq(1+\varepsilon)\log _{2} n\) for all \(n\) large enough.
Taking a countable sequence \(\varepsilon_{k} \downarrow 0\) deduce that \[\limsup _{n \rightarrow \infty} \frac{L_{n}}{\log _{2} n} \leq 1, \quad \text { a.s. }\]

(c) Fixing \(\varepsilon>0\) and letting \(A_{n}=\left\{L_{n}A_{n} \subseteq \bigcap_{i=1}^{m_{n}} B_{i}^{c}\]
where \(m_{n}=\left[n / k_{n}\right]\) (integer part) and \(B_{i}=\left\{X_{(i-1) k_{n}+1}=\ldots=X_{i k_{n}}=1\right\}\) are independent events.
Deduce that \(\mathbf{P}\left(A_{n}\right) \leq \mathbf{P}\left(B_{i}^{c}\right)^{m_{n}} \leq \exp \left(-n^{\varepsilon} /\left(2 \log _{2} n\right)\right)\), for all \(n\) large enough.

(d) Apply the first Borel-Cantelli for the events \(A_{n}\) defined in problem 6(c), followed by \(\varepsilon \downarrow 0\), to conclude that \[\liminf _{n \rightarrow \infty} \frac{L_{n}}{\log _{2} n} \geq 1 \quad \text { a.s. }\]

(e) Combine problems 6 (b) and 6 (d) together to conclude that \[\frac{L_{n}}{\log _{2} n} \rightarrow 1 \quad \text { a.s. }\]
Therefore the length of the maximum sequence of heads is approximately equal to \(\log _{2} n\) when the number of tosses \(n\) is large enough.