David Wilson wrote:
Suppose there is a man standing on a random square of a random polyomino. At regular intervals, we may instruct the man to move in one of the directions north, south, east or west. If the adjacent square in the specified direction is part of the polyomino, the man will move to that square, otherwise he will stay on his current square.
Is there a single infinite sequence of directions we can give to the man that guarantees he will eventually visit every square of the polyomino, regardless of its shape or size or of the man's initial square?
Here's another solution: Generate a random string of instructions. With probability 1, it will have the property you desire, since it will contain every finite sequence of instructions. Of course, randomness plays no essential role here, as other people's solutions to David's question have made clear. 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
On Monday 16 April 2007 16:55, James Propp 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?
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? -- g
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
On 4/17/07, Fred lunnon <fred.lunnon@gmail.com> wrote:
Please elaborate on why you propose the error term (log N)/N. WFL
Ah yes, I see the point now: all strings of length up to n = log_2(N) should occur among the first N bits, so for example the count of the string "1" will not change while the sequence appends "0^n". Hence the best we can expect is that the relative frequency varies by log(N)/N. WFL
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
participants (3)
-
Fred lunnon -
Gareth McCaughan -
James Propp