Mark three corners. Put a dot anywhere. Roll a die, move the dot halfway toward the corner it names, and mark it again. Do that a few thousand times and a perfect Sierpinski triangle appears, every hole in place. This chapter explains why chance can draw something exact, and how four small maps draw a fern.
Common mix-up: the randomness does not make the picture random. The shape is fixed entirely by the maps; the dice only decide the order in which its points get visited. Change the probabilities and the fern fills in faster here and slower there, but it is the same fern, point for point.
Here are the rules in full. Draw three points that make a triangle and call them corners. Pick any starting point at all; it can even be outside the triangle. Roll an ordinary die. On a one or a two, look at the top corner; on three or four, the bottom left; on five or six, the bottom right. Move halfway from where you are to that corner and make a dot. Now roll again, starting from the new dot. Keep going.
Most people, asked to guess the result, expect a fuzzy cloud filling the triangle, maybe thicker in the middle. That is not what happens. After a hundred dots you can see gaps. After a few thousand you are looking at the Sierpinski triangle from Chapter 3: one big empty triangle in the middle, three smaller ones in the corner triangles, nine smaller still, all the way down to the size of a dot. No dot ever lands in a hole, except for the first handful while the game is getting away from wherever you started.
Michael Barnsley gave this procedure its name, the chaos game, and it is the most direct way to meet an idea that runs under a whole family of fractals: an iterated function system, or IFS. "Jump halfway to the top corner" is a function. It takes a point and returns a point. So does "halfway to the bottom left". The game is a few functions, applied over and over in a random order. Swap in different functions and the same game draws a fern, a tree, a spiral or a dragon.
The surprise is worth taking seriously, because the explanation is the heart of the chapter. The dice are unpredictable. The shape is not. Something about these particular moves forces every point into the same set, no matter what order you apply them in.
This plays the game for you, from two dots a second up to about a million. Slow it right down to watch single jumps: the dashed line runs to the chosen corner and the dot stops partway. Then change the number of corners, the jump fraction, or add a rule about which corner may come next. Every recipe chip is a real, well-known variant. The dimension button counts boxes on the picture you have made and fits the slope, the method from Chapter 2.
Start with the shape and ask what the three moves do to it. Take the whole Sierpinski triangle and apply "halfway to the top corner" to every one of its points. You get a copy of the triangle, half the size, sitting in the top corner. The other two moves give half-size copies in the other two corners. Put the three copies together and you have the whole triangle again, exactly. That is what self-similar means here: the shape is the union of three shrunken copies of itself, and the three moves are precisely the shrinkings.
So if a dot is on the triangle, every move keeps it on the triangle. That explains why dots never land in holes once they arrive. It doesn't yet explain why they arrive, or why they eventually cover every part. For that, notice what each move does to distances. Halfway to a corner halves the distance between any two points. Two dots that start a meter apart are half a meter apart after one shared move, a quarter after two, a thousandth after ten. Wherever you started, after ten moves you are within a thousandth of where a dot that started on the triangle would be. The starting point is forgotten. Only the recent rolls matter.
That last sentence is also why the whole triangle gets filled. Name each small triangle by the moves that lead into it: the top corner's copy is "T", the top corner's copy's bottom-left copy is "TL", and so on. After any run of rolls ending in, say, L, R, T, the dot is in the tiny triangle whose address is TRL, read backward. A fair die, rolled long enough, produces every finite sequence somewhere, so every tiny triangle gets visited. The dice are a way of touring every address.
The general version was proved by the Australian mathematician John Hutchinson in 1981. Take any finite collection of maps of the plane, each of which shrinks every distance by at least some fixed factor. Such a map is called a contraction. Then there is exactly one nonempty, closed, bounded set that equals the union of its own images, and it is called the attractor of the system. Apply all the maps to any starting shape, collect the results, and repeat: the shapes converge to the attractor. Run the chaos game with any probabilities that are all above zero, and the dots converge onto it too.
The word "attractor" is earned. Start from a square, a circle, a single dot or a picture of a cat. Apply the three maps and you get three smaller squares, circles or cats. Apply them again: nine. Six rounds later there are 729 tiny copies of whatever you started with, arranged in the Sierpinski pattern, and from a distance you can no longer tell what the original was. The walkthrough above shows it with a circle.
The proof rests on Stefan Banach's fixed-point theorem from 1922: a contraction of a complete metric space has exactly one fixed point, and iterating the map from any start converges to it. The trick in Hutchinson's paper is choosing the right space. Its "points" are not points in the plane but whole shapes: nonempty compact sets.
The distance between two shapes is the Hausdorff distance: the smallest ε such that each shape lies within ε of the other. Two shapes are close if every point of one is near some point of the other, and vice versa. With that distance, the space of compact sets is complete.
Now define the Hutchinson operator H(S) = f₁(S) ∪ … ∪ fₙ(S). If each map shrinks distances by at least a factor s < 1, then H shrinks Hausdorff distances by the same factor. So H is a contraction on the space of shapes, Banach's theorem applies, and H has exactly one fixed shape: the attractor. The error after k rounds shrinks like sᵏ, which is why six or seven rounds already look finished at screen resolution.
The chaos game is the random, one-point-at-a-time version of the same thing. Each dot follows one branch of the tree of compositions instead of all of them at once. That it fills the attractor with probability one, and that the fraction of time it spends in each region settles down, follows from the theory of random iteration: John Elton proved an ergodic theorem for it in 1987, and Hutchinson's paper already constructs the invariant measure that describes the density.
The starting dot is almost certainly not on the attractor. After k jumps of a game whose maps all shrink by a factor s, its distance from the attractor is at most sᵏ times where it began. For halfway jumps on a canvas a thousand pixels across, about ten jumps put it within one pixel, and from then on it can only be within a pixel of the shape. Programs simply throw away the first twenty or so dots. The instrument above keeps them, because watching them stray and then fall into line is half the lesson.
Try the game with a square and halfway jumps and you get a disappointment: the square fills in evenly. Four half-size copies of a square, one at each corner, tile the square exactly, with no room left for holes. The attractor of that system is the solid square, and the chaos game draws it faithfully.
Two changes bring the holes back. The first is a shorter or longer jump. Jumping a fraction r of the way toward a corner means each copy is scaled by 1 − r. For a pentagon, five copies scaled by about 0.382 just touch each other, and the game draws a pentagonal snowflake of pentagons. For a hexagon the touching scale is 1/3, and for an octagon about 0.293. The pattern has a formula, and the instrument's "best fit" button uses it.
| Corners | Touching scale s | Jump fraction | Copies | Dimension log n / log(1/s) |
|---|---|---|---|---|
| 3 | 0.5 | 0.5 | 3 | 1.585 (Sierpinski triangle) |
| 4 | 0.5 | 0.5 | 4 | 2 (the filled square) |
| 5 | 0.382 | 0.618 | 5 | 1.672 (pentaflake-like) |
| 6 | 0.333 | 0.667 | 6 | 1.631 |
| 8 | 0.293 | 0.707 | 8 | 1.693 |
| 4 + center | 0.333 | 0.667 | 5 | 1.465 (Vicsek fractal) |
The second change is a rule about which corner may come next. Forbid the square game from choosing the same corner twice in a row and a lacy pattern appears. Forbid the corner one place clockwise from the last, and you get a different one. These restricted games are no longer plain iterated function systems, because the allowed move now depends on the previous move. They are IFS with memory: a graph of which maps may follow which. Mathematicians call them graph-directed systems, and the same contraction argument still guarantees a single limiting shape.
The 0.618 in the pentagon row is not a coincidence, by the way: it is 1/φ, where φ is the golden ratio, and 0.382 is 1/φ². Pentagons are full of φ.
In the square game, the dot's position after a run of moves lies in a small square whose address is the run, read backward, just as with the triangle. With no rule, every address is possible, so every small square is visited and the whole square fills. A rule like "never the same corner twice" bans every address containing a repeated letter. Whole families of small squares are now unreachable, at every scale, and those are the holes you see.
Counting the surviving addresses gives the dimension. With four corners and no repeats, each move after the first has three choices instead of four, so the number of reachable squares of side 2⁻ᵏ grows like 3ᵏ, and the dimension is log 3 / log 2 ≈ 1.585, the same as the Sierpinski triangle, although the shape looks nothing like it. Press "Estimate" on that recipe and the box counter should land near 1.58.
"Halfway to a corner" is a special case of a much richer kind of move. An affine map takes every point (x, y) to a new point using six numbers. Four of them, usually called a, b, c and d, mix the coordinates: they can shrink, stretch, rotate, shear and mirror. The last two, e and f, slide the result somewhere. Every straight line stays straight, parallel lines stay parallel, and a square always becomes a parallelogram.
A few combinations are worth knowing by sight. With b = c = 0, a and d scale the two axes separately; a = d = 0.5 halves everything. With a = d = s·cos θ and c = −b = s·sin θ, the map rotates by θ and scales by s, keeping shapes similar; this is called a similarity. A nonzero b on its own slides the top of a square sideways, a shear. A negative a flips left and right.
Two numbers summarize what a map does to size. The determinant, ad − bc, is the factor by which it multiplies areas, and a negative determinant means the map mirrors. The contraction factor is the most any distance can be stretched, which for a 2×2 matrix is its largest singular value. If that factor is below 1 for every map, Hutchinson's theorem applies and the system has an attractor. The editor below shows both numbers for every map and warns you if one stops being a contraction.
For the matrix [a b; c d], let T = a² + b² + c² + d² and D = ad − bc. The two singular values are √((T ± √(T² − 4D²)) / 2). The larger one is the contraction factor: no distance grows by more than it, and some distance grows by exactly that much. The smaller one is the least any distance is scaled. Their product is |D|, the area factor.
A map can shrink area while still stretching some direction. A shear such as [1 1; 0 0.5] halves areas, yet it stretches some vectors by more than 1. Such a map is not a contraction in the ordinary sense, and a system containing it may have no attractor at all; the points can drift off to infinity. (There are subtler theorems for systems that contract "on average", but the editor sticks to the plain rule.)
In his 1988 book Fractals Everywhere, Michael Barnsley showed four affine maps whose attractor looks like a black spleenwort fern, close enough to fool a botanist at a glance. It has become the standard example, the picture on a thousand textbook pages, and it rewards a careful look because every one of the four maps has a job.
Because map 2 makes the fern out of a slightly smaller fern, the bottom pair of fronds repeats all the way up, shrinking toward the tip. Because maps 3 and 4 make each frond out of a whole fern, every frond has its own leaflets, which have their own leaflets. That is the recursion a real fern only approximates for three or four levels before it runs out of cells.
| Map | a | b | c | d | e | f | p | Job |
|---|---|---|---|---|---|---|---|---|
| f₁ | 0 | 0 | 0 | 0.16 | 0 | 0 | 0.01 | Stem |
| f₂ | 0.85 | 0.04 | −0.04 | 0.85 | 0 | 1.60 | 0.85 | Successively smaller fronds |
| f₃ | 0.20 | −0.26 | 0.23 | 0.22 | 0 | 1.60 | 0.07 | Largest left frond |
| f₄ | −0.15 | 0.28 | 0.26 | 0.24 | 0 | 0.44 | 0.07 | Largest right frond |
Convention: x′ = a·x + b·y + e, y′ = c·x + d·y + f, with p the probability of choosing that map. The fern then fits in roughly −2.18 ≤ x ≤ 2.66 and 0 ≤ y ≤ 10.
The probabilities need explaining, because they are the most misunderstood part. They do not change the shape. Hutchinson's attractor is defined by the maps alone, and any choice of probabilities that are all greater than zero draws the same set. What the probabilities change is how quickly each part fills in. Map 2's copy covers most of the fern's area, so it should be chosen most often; the stem is a sliver of zero area, so it needs only one roll in a hundred. A good rule of thumb is to make each probability roughly proportional to the area its map covers, which is the map's determinant, with a small floor for squashed maps like the stem. With equal probabilities of a quarter each, the stem is drawn twenty-five times more often than it needs to be, and the tip of the fern stays sparse for a long time.
Barnsley's fern is part of the reason fractal ferns and flames turn up in so much generative art. J's JellyDazzle app has a growing fern, a Sierpinski rain and a flame IFS among its fractal patterns; the ideas in this chapter are the ones behind them, and Chapter 6 takes the flame version much further.
Run the chaos game long enough and count how often each pixel is hit. The counts settle into a stable pattern, a probability distribution on the attractor called the invariant measure. It depends on the probabilities even though the attractor doesn't. Shade pixels by their hit counts and the fern gets texture: the midrib of each frond, where many copies overlap, glows brighter than the leaflet tips.
That is the seed of the fractal flame algorithm: plot a histogram, not a set, and the shading comes free. It is also why the instruments here shade each pixel by how often it has been hit rather than painting it solid on the first visit.
Each colored parallelogram is one map: it is where the dashed reference box lands when that map is applied. Drag a parallelogram to move it, drag its round handles to stretch, rotate, shear or flip it, and the attractor redraws from scratch as you go. The thicker edge shows which way is "up" for that copy. Load a preset to start from something known. Tap a row in the table to select its map. Keep every map smaller than the reference box, or the points fly away.
| Map | a | b | c | d | e | f | p | det | contraction |
|---|
Similarity dimension is the D that solves Σ rᵢᴰ = 1, where rᵢ is each map's scale. It equals the true dimension only when every map is a similarity (no shear, no unequal stretch) and the copies don't overlap.
Going from maps to a picture is easy: run the game. Going from a picture to maps, the inverse problem, is hard. Given a photograph of a leaf, which handful of affine maps has that leaf as its attractor? There is usually no exact answer, and searching directly would mean running the game for every candidate and comparing the result.
Barnsley's collage theorem offers a shortcut. You don't need to run the game at all to judge a guess. Take the target shape, apply each of your candidate maps to it, and look at the union of the copies: the collage. If the collage covers the target closely, with few gaps and little spilling over, then the attractor of those maps is guaranteed to be close to the target too. How close depends on how hard the maps contract.
This is exactly how you use the editor above. To make an IFS for a maple leaf, you don't think about dynamics at all. You lay shrunken, tilted copies of a maple leaf over a maple leaf, like pasting cut-out photos onto a poster, until the copies cover it. The theorem promises that the attractor of those placements is a maple leaf. The fern's four maps are exactly such a collage: stem, rest of the fern, and two bottom fronds cover the fern with almost no overlap.
Write H for the Hutchinson operator, so the collage is H(T) and the attractor satisfies H(A) = A. By the triangle inequality, h(T, A) ≤ h(T, H(T)) + h(H(T), H(A)). The second term is at most s · h(T, A), because H shrinks Hausdorff distances by s. Move it to the left side and divide by 1 − s. That's the whole proof, and it is a general fact about any contraction: how far a point is from the fixed point is controlled by how far the map moves it.
If four maps can store a fern, could a few thousand maps store a photograph? That was the hope in the late 1980s, and it led to a real technique. The difficulty is that a whole photograph is not made of shrunken copies of the whole photograph. But small patches of a photograph often look like shrunken, darkened or brightened versions of larger patches elsewhere in the same photograph: a bit of tree bark resembles a bigger bit of bark, an edge resembles a bigger edge.
Arnaud Jacquin, a student of Barnsley's, turned this into a practical method around 1989, published in 1992. Cut the image into small range blocks. For each one, search the image for a larger domain block that, shrunk, perhaps rotated or flipped, and adjusted in brightness and contrast, looks most like it. Store only those instructions. These are called partitioned iterated function systems, because each map works on a piece of the image rather than the whole.
To decode, start from any image at all, even plain gray, and apply every stored instruction at once, over and over. Because each instruction is a contraction, the collage theorem's logic applies: the image converges to the attractor of the instructions, which is close to the original photo. Since the instructions describe shapes rather than pixels, you can decode at a higher resolution than you encoded, and the result invents plausible detail rather than showing blocks.
Fractal compression worked, and it was studied intensively through the 1990s. It lost out for practical reasons. Encoding was slow, since every range block needs a search through many domain blocks. Patent licensing was a hurdle. And wavelet and DCT methods, the families behind JPEG 2000 and JPEG, matched or beat its quality with far less computation. What survives is the idea, and the elegant fact that you can decode by starting from noise.