Head runs, a question on Probability Theory and Examples by Rick Durrett The model is the following. Let $X_n, n \in \mathbb{Z}$ be i.i.d with $P(X_n = 1) = P(X_n = -1) = 1/2$. Let $l_n = \max\{m : X_{n-m+1} = ... = X_n = 1\}$, and let $L_n = \max_{1 \leq m \leq n} l_m$.
If we consider two-sided sequence so that for all $n$, $P(l_n = k) = (1/2)^{k+1}$ for $k \geq 0$.
My question is about the sentence "Since $l_1 < \infty$, the result we are going to prove $L_n/\log_2 n \to 1 \ a.s.$ is also true for a one-sided sequence. "

*

*Why $l_1 < \infty$? I think the reason is $P(l_1 = k) = (1/2)^k \to 0, k \to \infty$. I want to clarify this point.

*Why $l_1 < \infty$ means that the conclusion is also true for the one-sided sequence? In other words, I don't know the effect of $l_1 < \infty$ in this proof.

The following is the proof in the book. This's on the book, Probability Theory and Examples Version 5 by Rick Durrett. It's on P63, Example 2.3.12.

 A: *

*Imagine positioning yourself at time 1, and starting to flip coins backwards in time (with the first flip at time 1). Observe that the number of flips until the first tails is observed is exactly the same as the distribution of $\ell_1$. Thus, $\ell_1$ has a Geometric(1/2) distribution, and indeed $\ell_1 < \infty$ almost surely, pretty much because of the reason you suggested. (To prove it, note that $\{ X = \infty \} = \bigcap_{k \geq 1} \{ X > k \}$, so $\mathbb{P}(\ell_1 = \infty) = \lim_{k \to \infty} \mathbb{P}(X > k) = 0$ for any random variable $X$ with a non-degenerate CDF.)


*Suppose that $\tilde{L}_n$ is the length of the longest head run for the one-sided sequence (i.e. we start flipping from time 1 going forwards in time). Note that $\tilde{L}_n$ and $L_n$ are essentially the same, with the difference possible being caused by a longer head run due to a sequence of heads before time 1 in the two-sided sequence. By adjusting for this and then dividing by $\log_2 n$, we obtain the inequalities
$$
\frac{L_n - \ell_1}{\log_2 n} \leq \frac{\tilde{L}_n}{\log_2 n} \leq \frac{L_n}{\log_2 n} .
$$
Since $\ell_1 < \infty$ almost surely, we have $\frac{\ell_1}{\log_2 n} \to 0$ almost surely (i.e. for every $\omega$ in this event, $\ell_1 \leq K < \infty$ for some number $K = K(\omega)$ and $\frac{K}{\log_2 n} \to 0$). Therefore, on the additional almost sure event $\frac{L_n}{\log_2 n} \to 1$, both sides of the inequality tend to one, and by sandwiching we deduce that $\frac{\tilde{L}_n}{\log_2 n} \to 1$ almost surely as well.
