The Chaos Game: How Random Half-Jumps Draw the Sierpinski Triangle

The rule, stated exactly

Fix three points A, B, C in the plane. They do not have to form an equilateral triangle; any three non-collinear points work, and the picture you get is an affine copy of the same fractal. Now define three maps, one per corner:

f_A(x) = (x + A)/2    f_B(x) = (x + B)/2    f_C(x) = (x + C)/2

Each one is a homothety: a pure scaling centred on its corner, with ratio 1/2. Applying it to a whole picture produces a half-size copy of that picture, pulled into that corner. Applying it to two points halves the distance between them: |f(x) − f(y)| = |x − y| / 2, for every x and y. That single inequality is what makes the whole thing work, and everything below is a consequence of it.

The game is then: start anywhere, and iterate x ← f_k(x) with k chosen uniformly at random from {A, B, C}, plotting every landing point. Twenty jumps of warm-up and a few tens of thousands of marks is plenty for a phone screen.

How it works in Python

import random

A, B, C = (0.0, 0.0), (1.0, 0.0), (0.5, 0.8660254)
x, y = 0.31, 0.72          # any starting point in the plane will do
points = []

for i in range(50_000):
    vx, vy = random.choice((A, B, C))
    x, y = (x + vx) / 2, (y + vy) / 2
    if i >= 20:            # throw away the transient (see below)
        points.append((x, y))

There is no test in that loop, no geometry, and no picture of a triangle anywhere in it. The only thing the program knows is three corners and the word halfway.

Why the dots snap onto the fractal: the error halves every jump

Call the Sierpinski triangle on A, B, C the set S. A newcomer's objection is reasonable: the starting dot is almost certainly not on S, so the first marks are wrong. They are — but not for long.

Suppose the current point x sits a distance δ from S. Whichever corner comes up, f_k halves distances, so f_k(x) is a distance δ/2 from f_k(S). And f_k(S) is a subset of S (that is the self-similarity, proved in the next section). So the new point is at most δ/2 away from S. Iterating:

dist(x_n, S) ≤ dist(x₀, S) / 2ⁿ.

Put numbers on it for a triangle of side 1. Start a full unit away from the fractal — well outside the triangle. After 10 jumps the error is at most 2⁻¹⁰ ≈ 0.00098, already under a thousandth of the side. After 20 jumps it is 2⁻²⁰ ≈ 0.00000095: under one millionth of the triangle. On a 1000-pixel-wide render one pixel is 0.001 of the width, so by mark number 10 the dot is already inside the correct pixel, and by mark 20 it is a thousand times finer than that.

Two things follow. First, the standard advice to discard the first 10 to 20 points is not superstition; it is the only part of the run that is visibly off the fractal. Second, the starting point genuinely does not matter. Start a kilometre away and thirty jumps put you within 1000 m / 2³⁰ ≈ 10⁻⁶ m — a micrometre — of a metre-wide fractal. Be precise about the claim, though: unless x₀ happens to lie on S, no plotted point is ever exactly on S. They are only ever within 2⁻ⁿ — which is exact enough to beat any resolution you can draw at, and nothing more.

Three half-size copies: the equation that pins the shape down

The Sierpinski triangle satisfies one equation:

S = f_A(S) ∪ f_B(S) ∪ f_C(S)

In words: S is made of three half-size copies of itself, one tucked into each corner. That is exactly what the animation shows when the finished cloud is halved towards each corner in turn and the three shrunken copies reassemble the original.

The load-bearing word is unique. Collect the three maps into the Hutchinson operator W(K) = f_A(K) ∪ f_B(K) ∪ f_C(K), acting on the set of non-empty compact subsets of the plane, measured with the Hausdorff metric. That space is complete, and because each f_k contracts by 1/2, W contracts by 1/2 as well. The Banach fixed-point theorem then gives exactly one fixed set, and Wⁿ(K) converges to it from any compact starting set K. John Hutchinson set this up in 1981 (Fractals and self similarity, Indiana University Mathematics Journal 30, 713–747).

So the Sierpinski triangle is not merely a set built from three half-size copies of itself. It is the only one. That is why the chaos game cannot draw anything else, and why starting W from a solid triangle (the familiar cut-out-the-middle construction) and starting it from a single dot (the chaos game's deterministic cousin) land on the same limit.

The dimension falls out of the same three maps. The copies meet only at three points, so the open set condition holds and the Hausdorff dimension equals the similarity dimension d solving 3 · (1/2)^d = 1, that is d = log 3 / log 2 = 1.58496… — more than a curve, less than a surface, and exactly the number the three-copies-at-half-scale rule forces.

Why the middle stays empty, at every scale

Once a point is on S (to within 2⁻ⁿ), its last jump decides which third of the picture it is in: a jump towards A lands it in f_A(S), which lives entirely inside the half-size triangle at corner A. The three half-size corner triangles between them leave one region untouched — the upside-down triangle whose vertices are the three edge midpoints. Nothing lands there. That is the big central hole, and it is a consequence of the rule, not of the random number generator.

Now read the last two choices instead of the last one. They pin the point into one of 3² = 9 quarter-size triangles, leaving three smaller upside-down holes, one inside each half-size copy. Read m choices and you get 3^m triangles of side 2^−m with holes between them. Every level of hole comes from one more symbol of history — which is why the gaps keep appearing as you zoom in, and why 34,000 marks show holes for about six levels before the dots run out: level six already splits the picture into 3⁶ = 729 triangles, about 47 marks each, and two levels further down there are only five marks per triangle — too few to tell a hole from a gap in the sampling.

Pushed to the limit, the sequence of choices is the point. Every infinite address (k₁, k₂, k₃, …) over {A, B, C} names exactly one point of S, namely the limit of f_k1 ∘ f_k2 ∘ … . The naming is onto, and one-to-one apart from a countable set of touching points where two copies meet: the midpoint of AB, for instance, is both f_A(B) with address A,B,B,B,… and f_B(A) with address B,A,A,A,…

Where the picture stops being proof. Watching the holes open up on screen is an illustration, not a demonstration. A finite sample of marks can only ever show gaps down to the pixel, and a sparse random sample leaves gaps everywhere. The claim that the holes persist at every scale for ever rests on the uniqueness argument in the previous section; the animation shows you what that argument is saying.

What the randomness actually controls

Not the shape. The attractor S depends only on the three maps; the probabilities do not appear in Hutchinson's equation at all. Bias the die to 0.6 / 0.2 / 0.2 and you draw exactly the same set — but the shading changes, with the favoured corner's copy visibly denser. What the probabilities fix is the invariant measure on S, not S itself. Equal odds give the natural, evenly spread measure; unequal odds give a multifractal one.

The theorem that licenses a single run is Elton's ergodic theorem (John Elton, An ergodic theorem for iterated maps, Ergodic Theory and Dynamical Systems 7, 1987, 481–488): for a contractive iterated function system with positive probabilities, almost every orbit's running averages converge to the integral against the unique invariant measure. Without it you could only say the fractal exists somewhere; with it you can say that your run, with probability 1, paints it correctly.

Genuine randomness is not required, only enough variety. Two ways to break it are instructive:

• Cycle the corners. Choose A, B, C, A, B, C, … for ever and the orbit is drawn to the fixed point of f_C ∘ f_B ∘ f_A, a similarity of ratio (1/2)³ = 1/8 with exactly one fixed point. You get a three-point cycle, not a fractal.
• Use a poor generator. Short-range correlations in a pseudo-random source show up as streaks and uneven shading in the gasket. The chaos game is a cheap and surprisingly sensitive eyeball test for a random number generator; a generator whose low bits are correlated makes certain sub-triangles conspicuously thin.

Change the corners, or change the ratio

The two dials are the number of corners n and the jump ratio r, and the interesting setting is the one where the shrunken copies just touch. For a triangle that is r = 1/2, which is why the classic game uses halves.

Turn r down to 1/3 and the three copies pull apart: they leave a gap along every edge and the attractor becomes a totally disconnected dust, a Cantor set in the plane, of similarity dimension log 3 / log 3 = 1 exactly. Turn r up to 2/3 and the copies overlap so thoroughly that their union is the whole triangle; the attractor is the solid triangle and the fractal is gone. Both transitions are sharp, but they happen at different ratios, and it is worth keeping them apart. The gap left in the middle of each edge has length 1 − 2r, so it closes exactly at r = 1/2: that is where the copies stop being separated and start just touching, and the attractor stops being a dust. The central hole is a separate threshold. For r ≥ 1/2 it is an upside-down triangle of side 2 − 3r, which at r = 1/2 is still a full half a side wide — it is the big hole of the gasket — and it shrinks to a point only at r = 2/3, where the three copies finally cover the whole triangle.

Four corners with r = 1/2 is the classic disappointment. The four quarter-squares tile the square exactly, so the attractor is the filled square and the dots just make grey. The Sierpinski carpet is not this game: it needs eight maps of ratio 1/3, the eight border cells of a 3×3 grid, and has dimension log 8 / log 3 ≈ 1.893. Restricting the square game instead — forbidding an immediate repeat, say — does give fractals, but they are attractors of a graph-directed system, where the legal next maps depend on the current state, rather than of a plain IFS.

Five corners has a pretty answer: the just-touching ratio for a regular pentagon is r = (3 − √5)/2 ≈ 0.381966, which is 1/φ² for the golden ratio φ. The result is the pentaflake, of dimension log 5 / log(φ²) ≈ 1.672.

Finally, drop the requirement that all the maps shrink by the same factor in the same way and allow general affine maps with their own probabilities. Same game, richer maps: four of them, weighted 0.85 / 0.07 / 0.07 / 0.01, give the Barnsley fern.

Where it came from, and where it turns up

Wacław Sierpiński described the shape in 1915 (Sur une courbe dont tout point est un point de ramification, Comptes Rendus 160, 302–305) as a curve every point of which is a branch point — a pathological example, not a picture. The game that draws it came much later, out of the machinery for handling such sets.

John Hutchinson (1981) supplied the framework: contraction maps, the Hausdorff metric, a unique attractor. Michael Barnsley and Stephen Demko (1985), in Iterated function systems and the global construction of fractals (Proceedings of the Royal Society A 399, 243–275), introduced the random iteration algorithm as a practical way to render those attractors, and Barnsley's 1988 book Fractals Everywhere gave it the name “the chaos game”. The commercial ambition behind it was image compression: the collage theorem says that if you can cover a picture with distorted small copies of itself, the short list of maps is the picture. Barnsley's company Iterated Systems built fractal compression on that idea, and fractally compressed images shipped in Microsoft Encarta in the 1990s.

The most durable application is elsewhere. In 1990 H. Joel Jeffrey published the chaos game representation of DNA (Nucleic Acids Research 18, 2163–2170): put A, C, G and T at the corners of a square, take r = 1/2, and make one jump per base of a sequence. The square that results is emphatically not uniform. A point's position encodes the last several bases exactly, so a sparse sub-square means an under-used k-mer — the well-known shortage of CG pairs in vertebrate genomes is visible at a glance as a thinned quadrant. CGR images are still used as fixed-size features for alignment-free sequence comparison and for machine-learning classifiers.

The same gasket also arrives by routes with no randomness in them at all: colour the odd entries of Pascal's triangle and it appears; run the elementary cellular automaton Rule 90 from a single cell and it appears; plot the states of the Tower of Hanoi puzzle and it appears. That several unrelated rules converge on one shape is the usual sign that the shape is the unique solution of a simple equation — which, by Hutchinson's theorem, it is.

Change the corners or the jump ratio r and the same game draws something else. The last column is the Hausdorff dimension of what the dots actually settle onto. It equals the similarity dimension log(number of maps) / log(1/r) only when the shrunken copies do not overlap; where they overlap, that formula overcounts and the true value is lower.

Corners	Jump ratio r	What the dots settle onto	Dimension of the attractor
3 (triangle)	1/2	Sierpinski triangle — the three copies just touch, at the edge midpoints	log 3 / log 2 ≈ 1.585
3 (triangle)	1/3	A totally disconnected dust — the copies leave a gap on every edge	log 3 / log 3 = 1 exactly
3 (triangle)	2/3	The solid filled triangle — the copies overlap and cover it	2 — the formula would say log 3 / log 1.5 ≈ 2.71, impossible in the plane; overlap voids it
4 (square)	1/2	The solid filled square — the four quarter-squares tile it exactly	2, and here the formula agrees: log 4 / log 2 = 2 (no longer a fractal)
5 (pentagon)	(3 − √5)/2 ≈ 0.382	Pentaflake, or Sierpinski pentagon — copies just touch	log 5 / log 2.618 ≈ 1.672