Other sequences

There is nothing about the desired output of the chaos game that requires a random sequence. The property of ``filling out'' a fractal $\mathcal{F}$ to some arbitrary resolution $N\times N$ simply means that all addresses in $\mathcal{F}$ to some depth $k$ ($k$ is a function of $N$ and the contractions defining $\mathcal{F}$) must be present in the sequence. A random sequence (with appropriate probabilities for each digit) may do a reasonable job, but will other sequences work?

It turns out that for ``nice'' fractals (all addresses are present) there is a best sequence: the shortest sequence that will include all substrings of length $n$, considerably shorter than the random sequence that is guaranteed to contain all such substrings. For addresses of length $k$ over $j$ digits, this sequence has length $j^k+k-1$. In A Probabilist Looks at the Chaos Game Goodman mentions an algorithm (Rees and Good) that will generate a best sequence over all digits.

What happens for our fractal-like object in Section 3? For example, how long is the best sequence to generate all $15$ strings of length $2$ that do not contain ``12''? Certainly you can do no better than length $16$ (the $15$th $2$-string ends at position $16$), but perhaps you cannot do that well. What about for longer strings?

Further work might extend the Fractal Sequence applet to use a best sequence driver, perhaps composed with substring filters. Is it possible to create optimal sequences that contain all substrings of length $k$ but not ``12''?