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 F_A, F_B, F_C, with fixed points at the vertices of a given triangle ABC and coefficient 1/2. (I shall use F_A, F_B, F_C and F₁, F₂, F₃ 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:

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

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

Fs2(Fs1(T0)) = Fs2(Ts1) Fs2(T0) = Ts2.

In other words, the image of T₀ after two steps (first applying F_s1 and then F_s2) is inside T_s2 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 s₁. In our addressing notations, this is triangle T_s2s1:

Similarly, for a third application, we get

We see (and this can be shown rigorously by induction) that the triangle T_s1s2...sn that corresponds to a finite address s₁s₂...s_n is the image of n applications of the functions F_A, F_B, F_C with indices read in the reverse order:

The sequence of triangles T_sn, ..., T_s2...sn, T_s1s2...sn thus obtained differs from the nested sequence T_s1, T_s1s2, ..., T_s1s2...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.

Since, for any transformation F, x T implies F(x) F(T), then, regardless of the selection of x₀, the n^th iteration F_s1(F_s2(...(F_sn(x₀)...)) will lie inside T_s1s2...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 s₁s₂...s_n, (at least) one of the iterations falls into the triangle T_s1s2...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 F_AF_A, F_AF_B, ..., F_CF_C that consists of 9 contractions each with coefficient 1/4, has exactly the same attractor as the system of three functions F_A, F_B, F_C. For a demonstration, see the applet at the Collage Theorem and IFS page and play with the Iterate button.

• Dot Patterns and Sierpinski Gasket
• Sierpinski Gasket By Common Trema Removal
• Sierpinski Gasket Via Chaos Game
• Sierpinski Gasket By Trema Removal
• The Chaos Game: Address Space vs IFS
• Sierpinski's Gasket and Dihedral Symmetry
• Collage Theorem And Iterated Function Systems
• Sierpinski Gasket and Tower of Hanoi
• Variations on the Theme of Tremas
• Variations on the Theme of Tremas II
• Barycentric Coordinates
  • Three glasses puzzle
  • Barycentric Coordinates and Geometric Probability
  • Van Obel Theorem and Barycentric Coordinates
• Similarity Dimension
• Iterations and the Mandelbrot Set
• Mandelbrot and Julia sets
• Emergence of Chaos