Source: IBM Ponder This - May 2011 Problem

Problem:
A barcode is composed of a series of variable-width white and black bars.
One of the important features of the barcode is that no bar be too wide; otherwise, the reader might get out of synchronization. Suppose we use the following barcode system, where we take a completely random sequence of bits and use it to build the bars. For example, the 7-bit-long sequence 0111001 will generate four bars of varying lengths: white(1), black(3), white(2), black(1). Such a system will generate, every once in a while, bars that are too wide. Let's call any black bar whose width is 20 bits or more a "bad bar".
What is the expected number of bits in the bars that are between two adjacent bad bars?

Other IBM Ponder This Problems on the blog:
http://pratikpoddarcse.blogspot.com/2010/01/ibm-ponder-this-january-2010-puzzle.html
http://pratikpoddarcse.blogspot.com/2009/11/ibm-ponder-this-november-challenge.html
http://pratikpoddarcse.blogspot.com/2009/10/ibm-ponder-this-puzzle.html

Update (29-05-2011)
Solution:
Posted by me in comments! (This solution was accepted by IBM Research as a correct solution).

1. Does blogspot support LaTeX? I couldn't find it.
Use http://www.codecogs.com/latex/eqneditor.php to view the math part.

Constants assumed :
n = Length of bar code.
b = Minimum length of a bad bar.

Suppose two consecutive bars are as follows :
Bar_1 starts at i, ends at j,
Bar_2 starts at k, ends at l.

Thus,
size of gap in between = k-j+1
Combined length of these two bars combined with the gap in between = l-i+1 = y (say)
number of bar codes in which this particular bad bar configuration occurs
= 2^{n-y-2} -- if y < n and the configuration is not at the ends.
= 2^{n-y-1} -- if y < n and the configuration is one of the ends.
= 1 -- if y = n

For a combined length of y, the number of white blocks in between can be anything from 1 to y-2b (let y-2b = z),
then the expected value of the number of white space in between
= \frac{\sum_{k=1}^{z} (z-k+1)*k}{\sum_{k=1}^{z} (z-k+1)}
= \frac{z+2}{3}

The number of two consecutive bars with combined length (with the gap in between) of y
= 2*2^{n-y-1} + (n-y-1)*2^{n-y-2} = (n-y+3)*2^{n-y-2} -- if n > y
= 1 -- if n = y

Thus, the expected value of the number of gaps
= \frac{[(n-2b+2)/3] + \sum_{y=2b+1}^{n-1} [(y-2b+2)/3]*[(n-y+3)*2^{n-y-2}]}{1 + \sum_{y=2b+1}^{n-1} [(n-y+3)*2^{n-y-2}]}

Now, I am too lazy to evaluate this complicated thing, but that should be fairly straightforward, but nevertheless pretty tedious. :(

2. @Pritish.. I too did not try to evaluate your expression. Although the solution looks correct, we cannot be sure until the numbers match.

I am sure this is not true in research, but for fun problem solving, if you are not getting a simple expression, then probably you are not doing it the right way :)

3. Solution I sent to IBM:

Let the expected number of bits in the bars that are between two

Consider the state that I have just got a bad bar and a white bit. The

expected number of bits to get the next bad bar is x.

This can be seen in two cases.
E(next bad bar | first new bit is white i.e. 0) = x+1
E(next bad bar | first 2 new bits are 10) = x+2
E(next bad bar | first 3 new bits are 110) = x+3
E(next bad bar | first 4 new bits are 1110) = x+4
E(next bad bar | first 5 new bits are 11110) = x+5
E(next bad bar | first 6 new bits are 111110) = x+6
and so on upto
E(next bad bar | first 20 new bits are [{1}^19]{0}) = x+20

One case is left
E(next bad bar | first 20 new bits are [{1}^20]) = 0

Hence,
x= (1/2)^1*(x+1) + (1/2)^2*(x+2) + (1/2)^3*(x+3) + (1/2)^4*(x+4)..
+(1/2)^20*(x+20)
Rearranging terms, we get
x/(2^20) = 1/2 + 2/4 + 3/8 + 4/16 + 5/32 .. 20/(2^20)
Calculating RHS,
2*(1/2+1/4+1/8+1/16+... 1/2^20 - 20/2^21) = 2*(1-22/2^21)

x = (2^21)-22

4. @pratik, if n is the limit for bad bar, ur solution gives 2^(n+1)-(n+1).

if we put n=1, then we get 2^2-2=2, but we should get 0.

if we put n=2, ur solution gives 2^3-3=5, but we should get 1.

answer i got is 2^n-(n+1) based on ur solution only.

5. assume wlog that after a bad bar, the next bar starts with a 1.

look at next n-1 bits for first occurrence of 0.

following cases arise:

10: probab= 1/2
110: probab=1/2^2
.
.
1^(n-1)0: probab=1/2^(n-1)
1^n: probab=1/2^(n-1)

if y is the required answer,
we get recurrence euqation,

y=1/2(1+y)+...1/2^(n-1)[n-1+y].

above simplifies to y= 2^n-(n+1).

if n=20, y= 2^20-21

6. My solution generalized for length of black bar = n (here n = 20) is as follows:

x/(2^n) = i from 1 to n (i/2^i)
x/(2^n) = 2 - (n+2)/2^n
x = 2^(n+1) - (n+2)

Answer = x+1 = 2^(n+1) - (n+1)

For n = 1,

Expected gap between two black bars = Expected number of whites between two blacks given that there is atleast one white is definitely greater than 1.

7. thanx pratik, agree with u.

i misread the problem. in the problem, actually only black bars are bad, i thought white bars can also be bad.

8. Not a problem. :)

9. Yes, I also find 2^(n+1) - (n+1).
For n=20, that is 2097131.
I submitted that solution. They didn't put my name on the solver's list. So they must have a different interpretation of the problem.

10. I found the same thing: 2^(n+1) - (n+1).

A bad bar appears every 2^(n+1) bits, and it is (n+1) bits long on average. For n=20, it gives 2097131.

But I submitted that answer and they did not credit me in the solver's list. So they must have a different interpretation of the problem.

11. @Florian,
Possible reasons:
1) You need to wait. They update it in 3-4 days.

I have been an IBM Research Ponder This Fan since last 18 months now and I don`t think they have made a mistake even once.

Cheers!

12. Consider the event that after a bad bar, we get one white and then a bad bar again be event 'a'. P(a)= 0.5^21.
So expected no of bits to achieve this =1/P(a)=2^21. But last 20 bits will be forming a bad bar. This gives 2^21 -20 bars . Where am I wrong?