The Chaos Game, math that surprises you lesson

Mark the three corners of a triangle and pick any starting point. Choose a corner at random, for example by rolling a die and letting 1 or 2 mean the first corner, 3 or 4 the second and 5 or 6 the third. Move halfway from the current point toward that corner, mark the new point, and repeat. Nothing in the rule mentions holes and every choice is left to chance, yet after a few thousand moves the marks show Sierpinski’s triangle with clear holes at several scales. How can random choices produce a precise shape? This page shows that each move is one of the three halving maps that build the triangle, that the influence of the starting point halves at every move, and that the shape the points settle on, the attractor, does not depend on luck.

Key terms

Chaos game

Definition The chaos game is played with three fixed points $A$ , $B$ and $C$ , the corners of a triangle, and a starting point $p_0$ , which may be anywhere in the plane. At every move one corner is chosen at random, each with probability $1/3$ and independently of all earlier choices, and the current point is replaced by the midpoint between it and the chosen corner. Each new point $p_1, p_2, p_3, \ldots$ is marked. The marks close in on the Sierpinski triangle with corners $A$ , $B$ and $C$ . Whatever the choices, every move at least halves the distance from the current point to that set, and if the start lies in the filled triangle, the point after $n$ moves lies in stage $n$ of the construction. Moreover, with probability $1$ the marks come within any chosen distance of every point of the Sierpinski triangle, again and again. A finite run still marks only finitely many points, so it never shows the whole set, and its marks may lie in holes, very close to the set but not in it. With corners that do not form an equilateral triangle the game draws a slanted Sierpinski triangle, built in the same way from the midpoints of that triangle. The word chaos in the name refers only to the random choices, which are an input to the game, and not to chaos in the mathematical sense described under random iteration below.

In plain words The random choices decide only which corner comes next. The halfway rule decides where the points can end up, so chance changes the order in which the parts of the Sierpinski triangle are visited, but not the shape that appears.

Example Take $A = (0, 0)$ , $B = (1, 0)$ and $C = (\tfrac12, \tfrac{\sqrt3}{2})$ , so the side is $1$ , and start at the center $G = (\tfrac12, \tfrac{\sqrt3}{6})$ , which is also the center of the first hole. Suppose the first three choices are $C$ , then $A$ , then $B$ . The marks are

\begin{aligned} p_1 &= \left(\tfrac12, \tfrac{\sqrt3}{3}\right), \\[0.4em] p_2 &= \left(\tfrac14, \tfrac{\sqrt3}{6}\right), \\[0.4em] p_3 &= \left(\tfrac58, \tfrac{\sqrt3}{12}\right). \end{aligned}

The move toward $C$ shrinks the whole picture, holes included, to half size in the top corner, so $p_1$ is the center of the hole of side $\tfrac14$ in the top corner triangle. In the same way each later mark is the center of a hole half as large as the one before, and $p_n$ is the center of a hole of side $2^{-(n+1)}$ , whatever the choices are. So no mark from this start ever lies in the Sierpinski triangle. Still, the distance from $p_n$ to it is the distance from the center of that hole to its edges,

\frac{\sqrt3}{12} \cdot 2^{-n},

which after 20 moves is less than one millionth of the side, far too small to see. A start at a corner behaves differently, since every mark is then a corner of some stage triangle and lies in the Sierpinski triangle itself.

Random iteration

Definition Random iteration applies maps chosen at random from a fixed list, one after another, each time to the latest point. With maps $f_1, \ldots, f_N$ of the plane and the choice $c_n$ at move $n$ , the points are

\begin{gathered} p_n = f_{c_n}(p_{n-1}) \\[0.4em] \text{for } n = 1, 2, 3, \ldots \end{gathered}

In the chaos game the list is $f_A$ , $f_B$ and $f_C$ , where $f_v$ moves a point halfway toward the corner $v$ , and the choices are independent with probability $1/3$ each. Each of these maps halves every distance, since

\lvert f_v(p) - f_v(q) \rvert = \tfrac12 \lvert p - q \rvert

for all points $p$ and $q$ . So two runs that start at different points but receive the same choices come together. After $n$ shared moves the segment between them points in the same direction as at the start and has $2^{-n}$ times its length. The gap never becomes exactly zero, but it becomes smaller than any given positive number. The same maps explain the holes. If the start lies in the filled triangle, then after $n \ge k$ moves the point lies in the stage $k$ triangle obtained by applying the last $k$ maps to the filled triangle. The last choice picks one of the three half-size triangles, the choice before it picks one of the three quarter-size triangles inside that one, and so on, while the earliest choices only matter at scales too small to see. The randomness here is an input from outside. In deterministic chaos the rule involves no random choice at all, yet two starting points that are very close can end up far apart. Random iteration of halving maps does the opposite and brings any two starting points together.

In plain words Every move squeezes the whole plane by half toward one corner. Two starting points that share the same choices are squeezed together, so their gap halves at every move, and after enough moves the two runs cannot be told apart on a screen of any fixed resolution, even though they never become exactly equal.

Example Start one run at the corner $A$ and another at the center $G$ , a distance $\tfrac{\sqrt3}{3} \approx 0.577$ apart when the side is $1$ , and give both runs the same ten choices. Whatever those choices are, after ten moves the two points are

\frac{\sqrt3 / 3}{1024} \approx 0.00056

apart, about half a pixel in a picture in which the side of the triangle is 1000 pixels long. The run from $A$ marks only points of the Sierpinski triangle and the run from $G$ marks only centers of holes, yet from then on the two runs look the same.

Attractor

Definition Take a finite list of maps of the plane, each of which shrinks distances by a fixed factor. That is, for each map $f$ there is a number $r < 1$ with $\lvert f(p) - f(q) \rvert \le r \lvert p - q \rvert$ for all points $p$ and $q$ . Call a set closed if it contains every point that its points come arbitrarily close to, and bounded if it fits inside some circle. The attractor of the list is the only closed and bounded set $K$ , other than the empty set, that is the union of its images under the maps. For the chaos game the maps are $f_A$ , $f_B$ and $f_C$ , and the attractor is the Sierpinski triangle $S$ with corners $A$ , $B$ and $C$ , since

\begin{aligned} S &= f_A(S) \cup f_B(S) \\[0.4em] &\quad \cup f_C(S). \end{aligned}

Random iteration is drawn to $K$ in two ways. First, measure the distance from a point to $K$ as the smallest distance from the point to a point of $K$ . At every move this distance becomes at most $r$ times what it was, where $r$ is the factor of the chosen map, so it goes to zero from any start, whatever the choices. In the chaos game each move at least halves it. Second, if every map is chosen with a fixed positive probability, independently at every move, then with probability $1$ the points come within any chosen distance of every point of $K$ , again and again. The attractor depends only on the maps. Changing the probabilities, as long as each stays positive, changes how often each part is visited but not the set. A map with probability zero is never used, and the maps that remain can have a much smaller attractor.

In plain words The attractor is the set where random iteration settles. The points may start far away and arrive in any order, but they are pulled toward one fixed set, and over a long run they visit every part of it. A picture made from finitely many marks shows the attractor only down to the scale that the run has had time to fill in.

Example Start the chaos game at $G$ again, so that no mark ever lies on an edge. From the first move on, a mark lies in the top half-size triangle exactly when the last choice was $C$ , which has probability $1/3$ . From the second move on, it lies in the top quarter-size triangle exactly when the last two choices were both $C$ , with probability $1/9$ . In the same way, from move $k$ on, each of the $3^k$ triangles of stage $k$ holds the current mark with probability $1/3^k$ . Among $30{,}000$ marks made after the first few moves, a triangle of stage 5, with side $1/32$ , therefore receives about $123$ marks on average, while a triangle of stage 9, with side $1/512$ , receives only about $1.5$ . In computer runs of that length, about one stage 9 triangle in five receives no mark at all. A gap at that scale in such a picture says only that the run has not reached that part yet, since every small triangle of every stage contains points of the attractor, its corners for example.

Check yourself

Two starting points are 3 units apart, and both runs receive the same choices. After how many moves are the two points first less than 0.001 apart? Do they ever land on exactly the same point?

Show the answer

Each shared move halves the gap, so after $n$ moves it is $3/2^n$ . After 11 moves the gap is

\frac{3}{2048} \approx 0.00146,

still more than 0.001, and after 12 moves it is $3/4096 \approx 0.00073$ . So 12 moves are needed. The gap is exactly $3/2^n$ , which is positive for every $n$ , so the two points never coincide, although they come as close together as you like.

Change the probabilities. Choose $A$ and $B$ with probability $1/2$ each and never choose $C$ . Where do the marks go? What changes if $C$ is chosen with probability $1/100$ instead, and $A$ and $B$ each with probability $99/200$ ?

Show the answer

Put $A = (0, 0)$ and $B = (1, 0)$ . Both $f_A$ and $f_B$ halve the second coordinate, whose size is the distance from the point to the line through $A$ and $B$ . So after $n$ moves that distance is $2^{-n}$ times the starting distance, and the marks approach the side $AB$ . The two maps send the segment $AB$ onto its left half and its right half, so the segment is the union of its two images and is the attractor of these two maps. Writing $b_n = 0$ for a move toward $A$ and $b_n = 1$ for a move toward $B$ , the first coordinate follows

x_n = \frac{x_{n-1} + b_n}{2},

so for a start in the filled triangle the first coordinate stays between $0$ and $1$ , and the last $k$ choices pin it down to one of the $2^k$ equal pieces of that interval. With probability $1$ every pattern of choices turns up, so the marks come close to every point of the segment. The game draws a line, with no triangle and no holes.

With probability $1/100$ for $C$ , all three maps have positive probability, so the attractor is the whole Sierpinski triangle again, and in the long run the marks come close to every point of it. Only the frequencies change. Starting from $G$ , a mark lies in the top half-size triangle exactly when the last choice was $C$ , so only about one mark in 100 lands there instead of one in three, and the top corner fills in far more slowly than the two bottom corners.

Play with the four corners of a square instead, each chosen with probability $1/4$ . First move halfway toward the chosen corner each time. Then change the rule and move two thirds of the way toward it. What does each game draw?

Show the answer

Use the square with corners $(0, 0)$ , $(1, 0)$ , $(0, 1)$ and $(1, 1)$ . Moving halfway toward a corner shrinks the square to the quarter-size square in that corner, and the four quarter-size squares fill the whole square exactly. So the filled square is the union of its four images, and it is the attractor. With probability $1$ the marks come close to every point of the square, and no holes appear. The chaos game draws a fractal only when the shrunken copies leave gaps.

Moving two thirds of the way toward a corner $(a, b)$ leaves the point at one third of its former distance from that corner,

(x, y) \mapsto \left(\frac{x + 2a}{3}, \frac{y + 2b}{3}\right).

Now the four images of the square are the corner squares of side $1/3$ , which leave a cross-shaped gap, and each later stage cuts a cross out of every kept square. Each coordinate follows the rule $x \mapsto x/3$ or $x \mapsto (x + 2)/3$ , the rule that builds the Cantor set. The attractor is the set of points whose two coordinates both lie in the Cantor set, often called Cantor dust. Each stage keeps $4/9$ of the area, so its area is zero, since $(4/9)^n$ goes to zero. Unlike the Sierpinski triangle it does not hold together, because no two of its points can be joined by a path inside it.

The Chaos Game

Key terms

Chaos game

Random iteration

Attractor

Check yourself

How this lesson connects

Builds on

Used later in