Bad BarCode


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).




Comments

  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. :(

    ReplyDelete
  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 :)

    ReplyDelete
  3. Solution I sent to IBM:
    Answer: (2^21) - 21

    Let the expected number of bits in the bars that are between two
    adjacent bad bars be x+1.

    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.

    E(next bad bar)=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
    Answer = x+1 = (2^21)-21

    ReplyDelete
  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.

    ReplyDelete
  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

    ReplyDelete
  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.

    ReplyDelete
  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.

    ReplyDelete
  8. 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.

    ReplyDelete
  9. 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.

    ReplyDelete
  10. @Florian,
    Possible reasons:
    1) You need to wait. They update it in 3-4 days.
    2) Your answer is correct but your solution might be wrong.

    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!

    ReplyDelete

Post a Comment