On 4/16/07, James Propp <propp@math.wisc.edu> wrote:
This topic provides me with a good opportunity to raise a question that has been on my mind for a year or two:
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?
Note that the Champernowne sequence A030190 has error 1/(log N). An explicit construction of Alon, Kohayakawa, Mauduit, Moreira and R\"odl allows one to achieve error 1/N^c for any exponent c greater than 2/3 (which beats what one would get from a random sequence of bits). [*Less than* 2/3? Gareth McCaughan]
Jim Propp
Please elaborate on why you propose the error term (log N)/N. WFL