The Chaos Game: Address Space vs IFS

Manifesto | Index | What's new | rss feed

| Bookmark |

| Follow us

| Recommend | Contact |

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:

T₁ = F₁(T₀), T₂ = F₂(T₀), T₃ = F₃(T₀),

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

(1)	T_σ₁ = F_σ₁(T₀),

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

F_σ₂(F_σ₁(T₀)) = F_σ₂(T_σ₁) ⊂ F_σ₂(T₀) = T_σ₂.

In other words, the image of T₀ after two steps (first applying F_σ₁ and then F_σ₂) is inside T_σ₂ 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_σ₂σ₁:

(2)	F_σ₂(F_σ₁(T₀)) = T_σ₂σ₁.

Similarly, for a third application, we get

(3)	F_σ₃(F_σ₂(F_σ₁(T₀))) = T_{σ₃σ₂σ₁}.

We see (and this can be shown rigorously by induction) that the triangle T_{s₁s₂...s_n} 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:

(n)	T_{s₁s₂...s_n} = F_s₁(F_s₂(...(F_{s_n}(T₀)...)).

The sequence of triangles T_{s_n}, ..., T_{s₂...s_n}, T_{s₁s₂...s_n} thus obtained differs from the nested sequence T_s₁, T_s₁s₂, ..., T_{s₁s₂...s_n} 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.

This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at http://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

Buy this applet
What if applet does not run?

Since, for any transformation F, x ∈ T implies F(x) ∈ F(T), then, regardless of the selection of x₀, the n^th iteration F_s₁(F_s₂(...(F_{s_n}(x₀)...)) will lie inside T_{s₁s₂...s_n}. 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_{s₁s₂...s_n}. 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

M. Barnsley, Fractals Everywhere, Academic Press, 1988
The Science of Fractal Images, H.-O.Peitgen and D.Daupe (eds), Springer-Verlag, 1988
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.

About Fractals

40620250