There is nothing about the desired output of the chaos game that
requires a random sequence. The property of ``filling out'' a fractal
to some arbitrary resolution
simply means
that all addresses in
to some depth
(
is a
function of
and the contractions defining
) 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 , considerably shorter than the random
sequence that is guaranteed to contain all such substrings. For
addresses of length
over
digits, this sequence has length
. 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 strings of length
that do not contain ``12''?
Certainly you can do no better than length
(the
th
-string
ends at position
), 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 but not ``12''?