1
$\begingroup$

I have a question which has been a little stumped. I'm pretty sure I know the answer, but don't know how to prove it to be true. Here it is:

"Given an infinite length random binary string, what is the expected length between consecutive blocks of at least 20 $1$'s?"

I managed to come up with a recurrence relation for the number of strings of a certain length that ended with 20 $1$'s (with no internal blocks of 20+ $1$'s). With that, I could come up with an infinite series get the expected length. But I hit a roadblock as I didn't know how to simplify the recurrence (for a specific length) and then incorporate it into an infinite series (to calculate the expected length).

Anyway, having hit that roadblock, I took a different approach. I figured out the question for expected length between blocks of at least 1 $1$, 2 $1$'s, 3 $1$'s

For example, the expected size for between for at least 1 1's (1(1)*01, 1(1)*001, 1(1)*0001,...) is 2 (easy to prove $1 + 1/2 + 1/4...$)

I proved this expected length $E(k)$ for a few values of block size at least k

$E(1) = 2$ $E(2) = 5$ $E(3) = 12$ $E(4) = 27$ $E(5) = 58$

I want to know $E(20)$ which due to my proof method I am not able to do

However, I noticed a pattern for $E(k)$

$E(k) = 2E(k-1) + k - 1$ which I'm pretty confident is correct (per computer assisted evidence...not proof)

My question is, why is this recurrence true? It must be based on the way block's of $k$ $1$'s can be built from smaller blocks, but I cannot figure it out.

$\endgroup$
0
$\begingroup$

If the binary string is truly random, then this question is about counting infinities, tread carefully!

For example if the block sizes are exactly 20, then two consecutive blocks separated by say four digits (the gap) will occur infinitely often. The four digit number cannot end or start with a 1, as this would make the blocks closer than four digits. That leaves 2^2 possibly combinations for a four digit gap. In general for a gap of N digits there are 2^(N-2) possible representations, that can fit in that gap.

Because the binary string is infinite, then for example the sequence 01 appears as equally likely as 1101 or indeed any other finite sequence.

So for a contradiction not to occur, larger gaps must occur more often than smaller gaps. How much more often? That depends on the number of representations for each gap. A gap of 10 (256 representations) must occur twice as often as a gap of 9 (128 representations).

$\endgroup$

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.