Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Maximum length sequences (MLS) are a type of pseudorandom binary sequences with specific properties (see Wikipedia: Maximum length sequence, or m linear feedback shift register. Properties that hold include

  • Window property: A sliding window of length m, passed along an m-sequence for 2m-1 positions, will span every possible m-bit number, except all zeros, once and only once. That is, every state of an m-bit state register will be encountered, with the exception of all zeros.
  • Balance property: The number of "1"s in the sequence is one greater than the number of "0"s.

Is there a similar type of pseudorandom binary sequences known/constructible for which

  • the "Window property" holds, but
  • which are unbalanced, i.e. having p % ones and (100-p)% zeros ?
share|improve this question
Doesn't the fact that each m-bit number appear exactly once forces the sequence to be balanced? (just take the frequency of ones in all non-zero m-bit numbers) –  Or Zuk May 13 '11 at 16:11
The name De Bruijn comes to mind. Gerhard "Ask Me About System Design" Paseman, 2011.05.13 –  Gerhard Paseman May 13 '11 at 17:01
Could you please explain what "passed along an m-sequence for 2m-1 positions" means? Even if 2m-1 should be $2^m-1$, I am still not totally sure about the meaning. As far as I understand, if this is really just the de Bruijn cycle question up to replacing Euler cycles by Euler walks (because you exclude 0000...0 and do not require the path to be a cycle), I wouldn't be surprised if you get slightly unbalanced strings, but they should not be too far from 50-50 for asymptotical counting reasons. –  darij grinberg May 13 '11 at 17:56

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.