# Maximum run of zeros in a $n$-bit binary string

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.

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$.
• 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? – Shiva Jul 9 '13 at 18:44