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).
Does blogspot support LaTeX? I couldn't find it.
ReplyDeleteUse 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. :(
@Pritish.. I too did not try to evaluate your expression. Although the solution looks correct, we cannot be sure until the numbers match.
ReplyDeleteI 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 :)
Solution I sent to IBM:
ReplyDeleteAnswer: (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
@pratik, if n is the limit for bad bar, ur solution gives 2^(n+1)-(n+1).
ReplyDeleteif 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.
assume wlog that after a bad bar, the next bar starts with a 1.
ReplyDeletelook 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
My solution generalized for length of black bar = n (here n = 20) is as follows:
ReplyDeletex/(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.
thanx pratik, agree with u.
ReplyDeletei misread the problem. in the problem, actually only black bars are bad, i thought white bars can also be bad.
Not a problem. :)
ReplyDeleteYes, I also find 2^(n+1) - (n+1).
ReplyDeleteFor 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.
I found the same thing: 2^(n+1) - (n+1).
ReplyDeleteA 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.
@Florian,
ReplyDeletePossible 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!
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.
ReplyDeleteSo 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?