Skip to main content
Became Hot Network Question
Source Link

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!