3
$\begingroup$

I came to know that, in a random string, one expects the longest sequence of zeros to be roughly of length $\log n$. I want to be able to prove this. For this I need to know the probability that the longest sequence of zeros in a random $n$-bit string is of length $k$. Basically I need a good counting strategy to count the number of such $n$-bit strings i.e., where maximum run of zeros is of length $k$.

Can somebody give a hint on how to proceed? I don't want a full answer.

$\endgroup$
2
$\begingroup$

See The Longest Run of Heads by Mark F. Schilling.

$\endgroup$
1
$\begingroup$

The number of $n$-bit strings with fewer than $k$ consecutive zeros is essentially a $k$-nacci number.

So (starting from $n=0$), the number of $n$-bit strings with fewer than $2$ consecutive zeros gives the sequence $1,2,3,5,8,13,21,34,\ldots$ which should be familiar, while the number of $n$-bit strings with fewer than $5$ consecutive zeros gives the sequence $1,2,4,8,16,31,61,120,\ldots$ which are essentially OEIS A001591, the pentanacci numbers (i.e. $120=61+31+16+8+4$).

Take differences and divide by $2^n$ to get the probability that the longest sequence of zeros in a random $n$-bit string is of length $k$.

I am not sure this will help in your proof.

$\endgroup$
  • $\begingroup$ Yea, knowing the probability doesn't help in my proof, as I am not able to find a simple expression for $n^{th}$ $k$-nacci number. How else can I go about the proof? $\endgroup$ – Shiva Jul 9 '13 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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