9
$\begingroup$

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!

$\endgroup$
0

1 Answer 1

12
$\begingroup$

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)

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.