## The Chaos Game: Address Space vs IFS

The Chaos Game is a way of constructing a deterministic object, like Sierpinski's gasket, by a random process in which a pattern emerges out of an apparently chaotic distribution of points. The chaos game applies to the attractor, a fixed point, of any iterated function system. Sierpinski's gasket is an easiest example.

The simplest(*) iterated function system whose attractor is the Sierpinski gasket consists of three contractions FA, FB, FC, with fixed points at the vertices of a given triangle ABC and coefficient 1/2. (I shall use FA, FB, FC and F1, F2, F3 interchangeably, depending as to what notation is more convenient at the instance.)

Why does the chaos game work? First of all, let's observe that the three triangles obtained on the first step of the trema removal procedure are the images of the three contractions:

T1 = F1(T0), T2 = F2(T0), T3 = F3(T0),

where T0 is the triangle ABC. In a concise form we can write

 (1) Tσ1 = Fσ1(T0),

where s1 is one of the symbols 1, 2, 3. For a second application,

Fσ2(Fσ1(T0)) = Fσ2(Tσ1) ⊂ Fσ2(T0) = Tσ2.

In other words, the image of T0 after two steps (first applying Fσ1 and then Fσ2) is inside Tσ2 and is obviously one of the three triangles into which the latter is split on the second construction step, viz., the triangle corresponding to the index s1. In our addressing notations, this is triangle Tσ2σ1:

 (2) Fσ2(Fσ1(T0)) = Tσ2σ1.

Similarly, for a third application, we get

 (3) Fσ3(Fσ2(Fσ1(T0))) = Tσ3σ2σ1.

We see (and this can be shown rigorously by induction) that the triangle Ts1s2...sn that corresponds to a finite address s1s2...sn is the image of n applications of the functions FA, FB, FC with indices read in the reverse order:

 (n) Ts1s2...sn = Fs1(Fs2(...(Fsn(T0)...)).

The sequence of triangles Tsn, ..., Ts2...sn, Ts1s2...sn thus obtained differs from the nested sequence Ts1, Ts1s2, ..., Ts1s2...sn in the trema removal procedure, but, however surprisingly, the final triangle is the same.

This fact is illustrated by the applet below. By pressing buttons A, B, C you execute an application of the corresponding contractions. The applet can display the sequence of triangles obtained by successive application of these transforms, or those coming from the addressing scheme.

### If you are reading this, your browser is not set to run Java applets. Try IE11 or Safari and declare the site https://www.cut-the-knot.org as trusted in the Java setup. What if applet does not run?

Since, for any transformation F, x ∈ T implies F(x) ∈ F(T), then, regardless of the selection of x0, the nth iteration Fs1(Fs2(...(Fsn(x0)...)) will lie inside Ts1s2...sn. We can go further and observe that in a randomly generated sequence of symbols 1, 2, 3, each of the symbols must appear at least once with the probability of 1. The same holds for any combination of two, three or more symbols. Whenever in a sequence of indices appears a combination s1s2...sn, (at least) one of the iterations falls into the triangle Ts1s2...sn. This observation shades light on why the chaos game works: any iteration can be considered as the starting point, and the addressing scheme assures us that, if the steps in the game are indeed uniformly random and do not discriminate against any particular contraction, the iterations will come sufficiently close to any point of the Sierpinski gasket with probability of 1.

### References

1. M. Barnsley, Fractals Everywhere, Academic Press, 1988
2. The Science of Fractal Images, H.-O.Peitgen and D.Daupe (eds), Springer-Verlag, 1988
3. H.-O. Peitgen, H. Jürgens, D. Saupe, Chaos and Fractals: New Frontiers of Science, Springer-Verlag, 1992 (*) As an example, the iterated system FAFA, FAFB, ..., FCFC that consists of 9 contractions each with coefficient 1/4, has exactly the same attractor as the system of three functions FA, FB, FC. For a demonstration, see the applet at the Collage Theorem and IFS page and play with the Iterate button.  