Jim asks:
<<
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?
>>
I have an idea for a strategy that may result in a solution.
In the cubical torus T^n = R^n/Z^n one may wish to find
a vector v in R^n such that stepping along T^n in equal
steps each equal to [v] (= the image of v in T^n by the
quotient map R^n -> T^n) gets you dense in T^n as fast
as possible.
I.e., define R_v(n) := the radius of the largest open ball in T^n
lying in the complement of {[v], [2v], . . ., [nv]}. We want
to find v such that R_v(n) decreases as fast as possible.
A folk theorem holds that the vector defined by
V_n := (phi,phi^2,...,phi^n),
where p is the golden ratio, can't be beaten, at least in the limit. (This is based on the non-folk theorem that
stepping along the circumference-1 circle T = R/Z in steps of
equal length gets you dense in T as fast as possible by using
steps of length phi.)
THE PRESENT PROBLEM may be thought of as similar to a
series of such torus problems on tori T^n, where a point
[x_1, . . .,x_n] of T^n is mapped to the 0-1 sequence
(*) floor{2*x_1}, . . ., floor{2*x_n}
where {y} denotes the fractional part of y.
The idea being, to get a 0-1 sequence with all the right probabilities
having the least error, PERHAPS it will work to let n = 1, 2, 3, . . .
for L(n) consecutive steps, and stepping through T^n as in the above
paragraph, and *concatenating* all the length-n 0-1 sequences obtained
from each step via (*). I suspect L(n) should be something of the order of
L(n) = 2^n. The step itself, while stepping through T^n, should perhaps
be the vector V_n as above.
QUESTION: What if this whole thing were collapsed down to the 1-dimensional
version of just stepping through T = R/Z with a constant steplength = phi,
and writing down the sequence e_n = floor(2*n*phi)
--Dan
