I wrote:
Can anyone find an explicit construction of an infinite sequence S of 0's and 1's with the property that for any finite bit-string s, the relative frequency with which s occurs in the first N bits of S converges to (1/2)^(length of s) with error that falls like (log N)/N?
Dan Asimov asked:
May I ask for a clarification of exactly what "error that falls like (log N)/N" means?
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. Note that I used (N-k+1)/2^k instead of N/2^k since a bit string of length k only gets N-k+1 chances to occur in a bit string of length N. Incidentally, that was a fun problem about the 3-torus, Dan! Jim