The Chaos Game

The Chaos Game is played by specifying a number of vertices (a₁, b₁), (a₂, b₂), ..., and (a_N, b_N), and a scaling factor r < 1. To play the game, start with the point (x₀, y₀) = (1/2, 1/2) and pick one of the vertices, say (a_i, b_i), randomly. The point (x₁, y₁) is the fraction r of the distance between (a_i, b_i) and (x₀, y₀). That is,

(x₁, x₁) = r*(x₀, y₀) + (1 - r)*(a_i, b_i)

Now pick another vertex, (a_j, b_j), randomly. The point (x₂, y₂) is given by

(x₂, x₂) = r*(x₁, y₁) + (1 - r)*(a_j, b_j)

and so on. For example, take four vertices,

(a3, b3) = (0, 1)		(a4, b4) = (1, 1)
(a1, b1) = (0, 0)		(a2, b2) = (1, 0)

the corners of the unit square, and take r = 1/2.

Suppose the random number generator begins by selecting the vertices in this order: 1, 3, 4, 3, 2. Here are the first five points generated by this run of the chaos game. If we continue, the points will fill in the square. This should be plausible: we start with a point inside the unit square, and each move is half-way between where we are and a corner of the square, so we never leave the square. Because we select the corners randomly, no part of the square is preferred over any other. So since some parts of the square fill in, all parts must fill in.

What would happen if we used just three vertices (a₁, b₁), (a₂, b₂), and (a₃, b₃)? As with the square, we start with a point in the triangle. (In this example, it's on the edge of the triangle, but that's still in the triangle.) Each move is half-way between where we are and a corner of the triangle, so we never leave the triangle. Because we select the corners randomly, no part of the triangle is preferred over any other. So since some parts of the triangle fill in, all parts must fill in. Thus played with three vertices of a triangle, the chaos game should fill in the triangle. Right? Try it here Here is the answer. Perhaps we should rethink the "reasons" just given.

Here are four more Chaos Game examples. Try to determine the shape before running the program or looking at the answer.

Example 1: vertices the corners of a square, r = 1/3.

Example 2: move the top right vertex to the left, r = 1/2.

Example 3: five vertices, four the corners of a square, one at the center of the square, r = 1/2.

Example 4: five vertices, four the corners of a square, one at the center of the square, r = 1/3.