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.
The Sierpinski Gasket
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)).

Fix three points in the plane, C_{1}, C_{2} and C_{3}. For definiteness, we take the points C_{1} = (0, 0), C_{2} = (1, 0) and C_{3} = (0.5, √3/2), the corners of an equilateral triangle.

Pick any point P_{0} and draw a dot there. This is our starting point. At each stage, we denote the current point by P_{k} and call it the game point.

Roll the dice. If n comes up, draw a point half way between P_{k} and C_{n}. For example, if we roll a 2, we pick the point half way between the current point Pk and C_{2}. This is the new game point.

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.
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).
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:
Since, at each stage, the area is reduced by a factor ¾, the remaining area must converge to zero. Moreover, taking the bottomleft section (one third of the total) and doubling its length in each direction gives us three copies of the bottomleft section, so the fractal dimension d is given by 2^{d }= 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.
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 (x_{k}, y_{k}) in the plane, the next point is f_{r}(x_{k}, y_{k}), where f_{r} is a member of the IFS, chosen with a specified probability p_{r} . In the simplest cases, the maps f_{r} are linear or affine transformations.
Probably the most famous is the socalled 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:
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:
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 = W_{1}(A) U W_{2}(A) where W_{1} and W_{2} are contractions, we can show that A is selfsimilar: it looks similar at all scales. Iteration of the mappings produces the fractal set.
Sources
[1] Barnsley, Michael, 1993: Fractals Everywhere. Academic Press, ISBN 0120790629. Second Edition, Dover (2012). 560 pp. ISBN: 9780486488707
[2] Hutchinson, John, 1980: Fractals and selfsimilarity. PDF
[3] Wikipedia article: The Chaos Game.
[4] Wikipedia article: Barnsley Fern.