The theory in the previous section described the deterministic
approach to computing the attractor of an IFS. Namely, we start with
any compact nonempty set K and compute the sequence of iterates
. The m-th iterate consists of the union of all
pieces of the form
where each 
ranges over 
. Altogether there are
pieces in . These pieces are all decreasing in diameter
at least as fast as the power 
, where s is a contractivity
factor for this IFS. Therefore, for m sufficiently large,
should be a close approximation of the attractor A. Moreover, each
sequence 
in the code-space of 
corresponds to a single point 
. To find 
,
start with any seed point 
and compute a sequence
Then 
. In addition, if
and 
are very close in code-space,
meaning that 
for 
, for some large value of
N, then and 
are close. We can even give a
detailed estimate. Let D be the diameter of A (maximum distance
between two points of A). Let s be a contractivity factor of this
IFS. Then 
contains both , and
and it has diameter 
.
In general, given a transformation 
, it's a lot
easier to compute the image w(x) of a single point x than it is to
compute the image w(K) of a whole set K. Also, note that in
computing the sequence 
above, approaching a
limit point , we must extend the word 
on the right end and then apply it to .
This is rather awkward to do.
There is a faster method for filling out the shape of the attractor A based on a statistical approach, called the random iteration method. Barnsley has also christened it the ``Chaos Game.'' Here we generate an orbit as follows
Here we are applying a single transformation at each stage to get the
next point in the orbit. The truly important change is that the words
are being extended on the left end. The statistical aspect
comes from the need to choose 
to get the next
point.
We suppose there is a means for making a random choice with certain
probabilities of the outcome. That is, we assign a positive
probability 
to each affine map 
. This probability is a
number 
representing the chance that will be selected.
For instance, 
means will be selected 50% of the time,
means 75%, etc. The sum of the probabilities should be 1,
meaning that one of the 's is certainly selected. That is,
Now, here is the amazing part. If we were to always choose
at every stage, the sequence 
rapidly converges
to the unique fixed point of 
. This sequence of choices has
probability
The much more likely outcome is that will come arbitrarily
close to every point in A. Thus, the sequence fills out
the attractor A (the technical saying is that 
is dense in
A).
A point in A is associated to a code-sequence
Two code-sequences correspond to near-by points if they agree for a large number of terms. The sequence
has a small but positive probability of occurring:
assuming each term is independently chosen. Consider our orbit
. Since we are choosing infinitely many
consecutive strings of N terms, we have a probability of 1
of eventually choosing 
, 
, ..., 
.
It follows that
is in the part of A corresponding to code-sequences beginning
with 
. This justifies why the sequence
comes arbitrarily close to every point in A. Just such a method as
this is the basis of FRACTINT's programs for computing the attractor
of an IFS. We turn next to these computations.
For the Sierpiński triangle, the IFS has a particularly nice
dynamical interpretation. Let the three vertices of the original
triangle be 
, 
, and 
. Consider a very uncertain
traveller starting at our seed point . On each day, the traveller
picks one of the destinations , 
, and and moves
halfway on the straight line to the chosen 
. If the traveller's
position on day m is , and the next destination is , then
the position on day m+1 is 
. Unfortunately, the
traveller randomly chooses the destination from day to day with equal
probabilities for all three. Does the traveller ever get to one of the
's? Our analysis above indicates that the traveller wanders
chaotically around the Sierpiński triangle forever.
A team of students led by R. Devaney at Boston University has written
a wonderful program (for Macintosh) implementing several variations of
this algorithm. For instance, an arbitrary number and arrangement of
destinations can be picked, instead of just the three vertices of a
triangle. Moreover, the scaling factor 
can be chosen
arbitrarily (still less than 1) for each destination, and the
probabilities can be varied as well. Here are a few places
on the Web where you can learn about this project: