James Propp wrote:
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. ... Oops: make that "|d(N)| < C (log N)"!
[I think it was right the first time, but never mind --- I'll run with the definition below!]
(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...
Sadly, in spite of the promising full-block frequencies, Gray-Champernowne examined under this microscope appears to better original Champernowne by only by a constant factor --- and in particular to be noticeably worse(ly?) distributed on a local basis than random. Sorry about that, everybody. Time to go away and crawl back under my stone, I reckon! Fred Lunnon