The length of the longest consecutive string of heads or tails that occur asymptotically almost surely when a unbiased coin is flipped repeatedly

Question

Consider an unbiased coin being flipped $n$ times, and suppose we label the outcomes as Heads = 0, and Tails = 1. Then the result of the flipping is a finite binary sequence of length $n$. Let us denote by $a_n$ the length of the longest consecutive string of 0's or 1's (whichever is longer).

Clearly, the probability that $a_n = 1$ (alternate heads and tails) equals $\frac{1}{2^{n - 1}}$, which goes to 0 as $n \to \infty$. On the other extreme, the probability that $a_n = n$ also goes to $0$ as $n \to \infty$. I was wondering if there is some function $f(n) $ such that the probability of $a_n$ being close to $f(n) $ is non-zero. One can even ask a stronger question if there is a $f(n )$ such that the probability of $a_n$ being close to $f(n) $ goes to $1$ as $n \to \infty$. In other words, if a coin is flipped $n$ times (where $n$ is very large), with high probability (or least with non-zero probability) one can get a string of $f(n )$ consecutive heads or tails. Naively, one could predict that $f(n )$ could be $\sim \log n$, but I am nowhere near sure, and have no idea how to prove such a thing.

I am somewhat sure that this problem has been looked at before. If yes, this is mainly a reference request. Thanks for your help!

Answer 1

The Erdos-Renyi law of large numbers answers this, in a strong sense and even in a more generalized fashion. More recent work in this direction includes papers by Arratia, Gordon, Waterman (see here) and others.

Let $X_1,X_2,\ldots$ be binary i.i.d. with $Pr[X_i=1]=p.$ Define $$ L_n(\theta)=\max\left\{t:\exists i \in \{0,1,\ldots,n-t\},\theta \leq \frac{1}{t}\sum_{k=1}^t X_{i+k}\right\}. $$ Note that this is the density of $1$'s along sequence windows of length $t$ and you are asking about $L_n(\theta)$ for $\theta=1.$

Then for all $\theta \in (p,1]$ we have $$ L_n(\theta)\rightarrow \frac{\log n}{H(\theta,p)} $$ where the binary relative entropy is given by $$ H(\theta,p)=\theta \log(\theta/p)+(1-\theta)\log((1-\theta)/(1-p)), $$ with $H(1,p)=\log(1/p).$ If you put $\theta=1$ and $p=1/2,$ the denominator is $\log(2)$ and you recover $\log_2 n$ as you surmised.

References:

Erdos, Renyi: On a New Law of Large Numbers. J. Analyse Math. 22, 103–111 (1970)