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).
Jim Propp
Even if the following were to work, it would hardly qualify as an "explicit" construction: but for what it's worth, suppose we have already to hand a (cyclic) deBruijn sequence S_n in which every binary word of length n occurs as a factor exactly once. It's easily seen to be impossible to extend this to an S_{n+1}, for the relatively trivial reason that S_n must contain 01^n0 and 10^n1, whereas S_{n+1} may not contain either. However, 0^n and 1^n are the only nodes on the associated graph having 2 rather than 4 neighbours. Now suppose we manage to arrange S_n with these awkward factors 0^n1^n adjacent at the far end: we hack them off, then hopefully extend the remainder of S_n to a S_{n+1} which likewise terminates in 0^{n+1}1^{n+1}. Continuing, we get an infinitely distributed sequence which I think has to satisfy Jim's optimal distribution constraint ... Lest this all seem absurdly half-baked, here's an example: n = 4: 00101101 00001111 n = 5: 00101101 11010100010011 0000011111 Fred Lunnon