### The Chaos Game

The term “Chaos Game” was coined by Michael Barnsley [1], who developed this ingenious technique for generating mathematical objects called fractals. We have discussed a particular fractal set on this blog: see Cantor’s Ternary Set.

The Chaos Game is a simple algorithm that identifies one point in the plane at each stage. The sets of points that ultimately emerge from the procedure are remarkable for their intricate structure. The relationship between the algorithm and fractal sets is not at all obvious, as there is no evident connection between them. This element of surprise is of one of the delights of mathematics.

Let’s specify the algorithm in a simple case. We need a dice (I should say die but that feels awkward) with three numbers. We can use a standard dice and identify 6 with 1, 5 with 2 and 4 with 3; that is, for face n we call it min(n, 7 – n)).

1. Fix three points in the plane, C1, C2 and C3. For definiteness, we take the points C1 = (0, 0), C2 = (1, 0) and C3 = (0.5, 3/2), the corners of an equilateral triangle.

1. Pick any point P0 and draw a dot there. This is our starting point. At each stage, we denote the current point by Pk and call it the game point.

1. Roll the dice. If n comes up, draw a point half way between Pk and Cn. For example, if we roll a 2, we pick the point half way between the current point Pk and C2. This is the new game point.

1. Repeat this procedure many times, drawing a new point at each step.

We seek the attractor of the mapping, so we eliminate the initial points, let’s say, the first one hundred points. It is difficult to anticipate the outcome of this algorithm, but the figures below reveal all. We plot the results at several stages of the procedure, with k = 500, 1000, and 2000. We can see a structure forming. It is the famed Sierpinski Gasket.

The Chaos Game for three points at the vertices of an equilateral triangle. Output after 500, 1000 and 2000 steps.

More details of this Chaos Game can be found in Barnsley’s book [1] and on Wikipedia [3]. We show the results of the algorithm for one million iterations (omitting the initial 100 points).

Sierpinski Gasket constructed with the Chaos Game. One million iterations, first 100 points omitted.

The Sierpinski Gasket is usually formed in a manner analogous to the Cantor set. We start with the entire (solid) equilateral triangle. At each stage, we divide each solid triangular portion into four similar triangles and remove the central one. This procedure is continued indefinitely:

Sierpinski Gasket: usual construction by trisection.

Since, at each stage, the area is reduced by a factor ¾, the remaining area must converge to zero. Moreover, taking the bottom-left section (one third of the total) and doubling its length in each direction gives us three copies of the bottom-left section, so the fractal dimension d is given by 2d = 3 or d = log3/log2 1.585.

There is yet another way to generate the Sierpinski Gasket. The even entries in Pascal’s Triangle are arranged in triangular groups, like the white portions of the figure above. If all even numbers are eliminated, what remains in the limit has the structure of the gasket. The figure below is obtained by plotting a small triangle at each of the odd entries for the first 64 rows of Pascal’s Triangle.

Sierpinski Gasket constructed by marking only the odd entries in the first 64 rows of Pascal’s Triangle.

Barnsley Ferns.

Barnsley generalized the Chaos Game to produce a wide range of fractal sets. He based it on an Iterated Function System (IFS) (details in [1]). Starting with a point (xk, yk) in the plane, the next point is fr(xk, yk), where fr is a member of the IFS, chosen with a specified probability pr . In the simplest cases, the maps fr are linear or affine transformations.

Probably the most famous is the so-called Barnsley Fern. The algorithm or procedure is very similar to that described for the Sierpinski Gasket, but now four different linear maps are used in the IFS instead of one, and the choices between them are made on the basis of random numbers, with prescribed probability for each map (see Wikipedia article [4] for full details). The algorithm can be coded in a few lines of MatLab or Mathematica. We show the results at several stages below:

Barnsley Fern generated by Chaos Game. Left to right: 1000, 10 000 and 100 000 points.

The final result is a set of considerably beauty. The structure of the set built up by the Chaos Game bears a remarkable similarity to a real fern:

Barnsley Fern after one million iterations.

The Chaos Game algorithm had a practical application in image compression. All the images in the online encyclopaedia Encarta were compressed using this algorithm. The mathematics behind the Chaos Game depend on a result proved by Hutchinson [2] that shows that a finite set of contraction mappings determine a unique attractor. In simple terms, if we can split a set A = W1(A) U W2(A) where W1 and W2 are contractions, we can show that A is self-similar: it looks similar at all scales. Iteration of the mappings produces the fractal set.

Sources

[1] Barnsley, Michael, 1993: Fractals Everywhere. Academic Press, ISBN 0-12-079062-9. Second Edition, Dover (2012). 560 pp. ISBN: 978-0486488707

[2] Hutchinson, John, 1980: Fractals and self-similarity. PDF

[3] Wikipedia article: The Chaos Game.

[4] Wikipedia article: Barnsley Fern.