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

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!

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)

• "If you put $\theta = p$" --> $\theta = 1$?
– usul
May 29 at 22:50