随机序列的线性复杂度

随机序列的线性复杂度尽管也具有随机性,但它们的期望值却约为其长度的一半。并且对任意随机序列,可至多改变一位使其线性复杂度达到长度的一半。Rueppel证明了长为n的二元随机序列线性复杂度的期望值为