I wrote:
Good question! What I think I mean is that if we let k denote the length of s and define f(N) as the number of occurrences of s in the first N bits of S, then the discrepancy d(N) = f(N) - (N-k+1)/2^k satisfies |d(N)| < C (log N) / N for some constant C, when N is sufficiently large.
Oops: make that "|d(N)| < C (log N)"! (Note that the difference between (N-k+1)/2^k and N/2^k is constant and hence less than log N for N sufficiently large; so another way to state the desired inequality is |f(N)/N - 1/2^k| < C (log N) / N.) I hope I have that right now... Fred Lunnon wrote:
Perhaps it's worth mentioning a bomb-proof but clumsier alternative. deBruijn sequences --- (k!)^k^(n-1)/k^n disitnct ones, modulo cyclic shift --- exist for every span n and base k (with k = 2 here). So at each iteration pick any one with span n' = 2^n, then shift it until the previous one with span n appears at the front.
Can you explain in more detail how this works? I'm not seeing it. Jim