Let (s) be a sequence of length n. What are the expected linear complexities of (s) and $(s)^{\infty}$ (meaning that the periodic version of s)?

I have no idea of the answer to this question? What does it mean when it say: "expected linear complexity"? Does anyone have any ideas on this issue?

Note that: for sequences which satisfy Golomb's Randomness Postulates, we calculate the "Linear Complexity Profile" of the sequence and for such sequences it is proved that the Linear Complexity at each step is approximately equal to n/2. Actually the LC values are in the +(-)5/18 neigbourhood of n/2 line. But in the above question there is no specification on the randomness of the sequence.


It means (usually) averaged over all sequences of a given length. Rueppel computes this in his book.

It's for an i.i.d. uniform sequence, Proposition 4.6. As $n$ goes to infinity by the law of large numbers this sample mean approaches the actual mean.

This was rigorously proved by Meidl and Niederreiter much later. Behind a paywall but you can see the abstract below:


The answer is nearly $n$ for $n$-periodic sequences.

  • $\begingroup$ does he compute it for a pseudo-random sequence satisfying Golomb's Postulates? Or just for an ordinary sequence? $\endgroup$
    – esra
    Aug 19 '18 at 14:22
  • $\begingroup$ i could not find it in rueppels book which section is it in please? Thanks by the way $\endgroup$
    – esra
    Aug 19 '18 at 14:55
  • $\begingroup$ See my update. If it's satisfactory you can accept and/or upvote the answer. $\endgroup$
    – kodlu
    Aug 19 '18 at 23:47

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.