The Sierpinski triangle

The chaos game

The Sierpinski triangle is usually built by subdivision: take a triangle, remove the middle quarter, repeat forever on the three that remain. This post builds it the other way round, by a rule so simple it looks like it cannot possibly work:

  1. Start anywhere inside an equilateral triangle.
  2. Pick one of the three corners at random.
  3. Move half the way to it. That is your new point.
  4. Repeat.

No subdivision, no recursion, no memory of where the holes should go. Just ten thousand coin flips and a halving rule. The fractal appears anyway. This is Barnsley’s chaos game, and it is the cheapest demonstration I know that a deterministic attractor can be traced out by a random walk.

The triangle

An equilateral triangle with side 1, sitting on the x axis. The apex is at height \(\sqrt{3}/2\), which is what makes the sides equal rather than merely the base.

n <- 10000
set.seed(42)

V <- tibble(
  corner = factor(c("A", "B", "C")),
  x      = c(0, 1, 0.5),
  y      = c(0, 0, sqrt(3) / 2)
)
V
## # A tibble: 3 × 3
##   corner     x     y
##   <fct>  <dbl> <dbl>
## 1 A        0   0    
## 2 B        1   0    
## 3 C        0.5 0.866

The starting point has to be uniform inside the triangle, and this is the one place where the obvious approach is wrong. Drawing x and y independently and rejecting anything outside the triangle works but wastes draws; worse, the tempting shortcut of weighting the three vertices by three uniform random numbers concentrates points toward the centroid. The standard fix takes the square root of one of the two uniforms, which stretches the distribution back out to the edges:

runif_triangle <- function(V) {
  r1 <- runif(1)
  r2 <- runif(1)
  s  <- sqrt(r1)                       # the sqrt is what makes it uniform
  w  <- c(1 - s, s * (1 - r2), s * r2) # barycentric weights, summing to 1
  c(x = sum(w * V$x), y = sum(w * V$y))
}

p0 <- runif_triangle(V)
p0
##         x         y 
## 0.5083197 0.7761929

In practice the starting point barely matters — the walk forgets it within a dozen steps, for reasons the last section gets to — but it costs two lines to do properly.

The walk

Ten thousand steps, each one a random corner and a halving. The loop is written out rather than vectorised because each point depends on the one before it: this is a recurrence, not a transformation, and cumsum-style tricks do not apply.

px <- numeric(n + 1)
py <- numeric(n + 1)
px[1] <- p0[["x"]]
py[1] <- p0[["y"]]

k <- sample.int(3L, n, replace = TRUE)   # which corner, at every step

for (i in seq_len(n)) {
  px[i + 1] <- (px[i] + V$x[k[i]]) / 2
  py[i + 1] <- (py[i] + V$y[k[i]]) / 2
}

Each row of the result is one segment: where the walk was, and where it went. Note that the vectors are named px/py rather than x/y. Inside tibble() columns are evaluated in order and can refer to earlier ones, so a column named x would shadow an outer vector called x, and xend = x[-1] would silently take its values from the column instead — returning 9,999 rows and a confusing error.

walk <- tibble(
  step   = seq_len(n),
  corner = V$corner[k],
  x      = px[seq_len(n)],   # starting point
  y      = py[seq_len(n)],
  xend   = px[-1],           # ending point, halfway to the chosen corner
  yend   = py[-1]
)

walk
## # A tibble: 10,000 × 6
##     step corner     x      y  xend   yend
##    <int> <fct>  <dbl>  <dbl> <dbl>  <dbl>
##  1     1 A      0.508 0.776  0.254 0.388 
##  2     2 A      0.254 0.388  0.127 0.194 
##  3     3 B      0.127 0.194  0.564 0.0970
##  4     4 B      0.564 0.0970 0.782 0.0485
##  5     5 B      0.782 0.0485 0.891 0.0243
##  6     6 A      0.891 0.0243 0.445 0.0121
##  7     7 C      0.445 0.0121 0.473 0.439 
##  8     8 C      0.473 0.439  0.486 0.653 
##  9     9 A      0.486 0.653  0.243 0.326 
## 10    10 A      0.243 0.326  0.122 0.163 
## # ℹ 9,990 more rows

A quick check that the rule does what it claims. Every segment should be exactly half the distance from its start to the chosen corner, and no point should ever escape the triangle:

chosen <- V[k, c("x", "y")]
tibble(
  `max halving error` = max(abs(
    sqrt((walk$xend - walk$x)^2 + (walk$yend - walk$y)^2) -
    sqrt((chosen$x  - walk$x)^2 + (chosen$y  - walk$y)^2) / 2
  )),
  `all points inside` = all(
    walk$yend >= 0 &
    walk$yend <= sqrt(3) / 2 * (1 - abs(2 * walk$xend - 1))
  )
)
## # A tibble: 1 × 2
##   `max halving error` `all points inside`
##                 <dbl> <lgl>              
## 1            1.11e-16 TRUE

The segments

Here are all ten thousand segments, coloured by the corner each one jumped toward. Because the colours are matched to the factor levels by name, the vector is passed to scale_colour_manual() as-is rather than through unname().

CORNER_COLS <- c(A = "#d33682", B = "#268bd2", C = "#859900")

ggplot(walk) +
  geom_segment(aes(x = x, y = y, xend = xend, yend = yend, colour = corner),
               linewidth = 0.1, alpha = 0.15) +
  scale_colour_manual(values = CORNER_COLS, name = "Corner") +
  coord_fixed() +
  labs(title = "Ten thousand segments of the chaos game",
       subtitle = "Each segment runs halfway from the current point to a random corner",
       x = NULL, y = NULL)

Which is a tangle, and worth dwelling on rather than apologising for. The segments are not the fractal. Every jump is a straight line aimed at one of three corners, so the segments sweep across the interior and cover the holes they are busy creating. The structure lives in where the walk stops, not in the paths it takes between stops. Drawing the journeys hides the destinations.

Sixty segments make the mechanism visible in a way that ten thousand cannot:

ggplot(filter(walk, step <= 60)) +
  geom_segment(aes(x = x, y = y, xend = xend, yend = yend, colour = corner),
               linewidth = 0.4,
               arrow = arrow(length = unit(4, "pt"), type = "closed")) +
  geom_point(aes(x = xend, y = yend), size = 0.7) +
  scale_colour_manual(values = CORNER_COLS, name = "Corner") +
  coord_fixed() +
  labs(title = "The first sixty steps",
       subtitle = "Arrows point to each new position; the walk crosses the empty regions freely",
       x = NULL, y = NULL)

The endpoints

Plot the same ten thousand rows as their endpoints alone, and the attractor appears:

ggplot(walk) +
  geom_point(aes(x = xend, y = yend, colour = corner),
             size = 0.15, alpha = 0.6) +
  scale_colour_manual(values = CORNER_COLS, name = "Corner") +
  coord_fixed() +
  labs(title = "The Sierpinski triangle",
       subtitle = "The same 10,000 rows, drawn as endpoints instead of segments",
       x = NULL, y = NULL)

Identical data, identical seed, one aesthetic changed — xend/yend mapped to a point rather than the end of a line — and the holes resolve down to the limit of the resolution.

The exact construction

The plot above is a sample of the Sierpinski triangle: ten thousand points drawn from its attractor, with all the graininess that implies. The fractal itself is a deterministic object, and it is worth drawing properly alongside the sampled version.

The classical construction goes the other way round from the chaos game. Take a filled triangle, join the midpoints of the three sides, discard the middle triangle that this creates, and recurse into the three that remain. After depth rounds there are \(3^{\text{depth}}\) filled triangles:

sierpinski <- function(V, depth) {
  tris <- list(as.matrix(V[, c("x", "y")]))
  for (d in seq_len(depth)) {
    tris <- unlist(lapply(tris, function(t) {
      m <- rbind((t[1, ] + t[2, ]) / 2,     # midpoints of the three sides
                 (t[2, ] + t[3, ]) / 2,
                 (t[3, ] + t[1, ]) / 2)
      list(rbind(t[1, ], m[1, ], m[3, ]),   # corner triangle at vertex 1
           rbind(m[1, ], t[2, ], m[2, ]),   # ... at vertex 2
           rbind(m[3, ], m[2, ], t[3, ]))   # ... at vertex 3
    }), recursive = FALSE)                  # the middle one is simply not kept
  }
  bind_rows(lapply(seq_along(tris), function(i)
    tibble(id = i, x = tris[[i]][, 1], y = tris[[i]][, 2])))
}

exact <- sierpinski(V, depth = 7)
n_distinct(exact$id)
## [1] 2187

Each triangle is a closed polygon, so this is geom_polygon() grouped by triangle id rather than a scatter of points:

ggplot(exact, aes(x = x, y = y, group = id)) +
  geom_polygon(fill = "#268bd2", colour = NA) +
  coord_fixed() +
  labs(title = "The Sierpinski triangle, exactly",
       subtitle = "Seven rounds of subdivision: 2,187 filled triangles",
       x = NULL, y = NULL)

The two pictures agree, which is the point: a random walk with no memory and a deterministic subdivision with no randomness converge on the same set. But they fail in opposite directions. The chaos game is exact about where the set is and ragged about filling it in — more steps always help. The subdivision is exact at every scale it reaches and completely blind below that: depth 7 resolves to triangles of side \(1/128\) and says nothing whatsoever about what happens beneath them.

Each round keeps three of the four sub-triangles, so the area after depth rounds is \((3/4)^{\text{depth}}\) of the original — about 13.3% at depth 7, and heading to zero. The limiting object has zero area but infinite perimeter, which is why its dimension is neither 1 nor 2 but \(\log 3 / \log 2 \approx 1.585\): three copies of itself, each at half the scale.

What the colours show

The colouring is not decoration. Every point drawn in magenta is one whose last jump was toward corner A, and all of them land in A’s own third of the figure; the same holds for B and C. The three colours partition the triangle cleanly into its three sub-triangles, with no mixing at the boundaries.

That is the whole trick, and it explains both the fractal and the forgetting. Halving the distance to corner A maps the entire triangle into the sub-triangle at A — whatever the current point is. So after one step you are in the third belonging to your last corner; after two, in the sub-sub-triangle belonging to your last two corners; and so on. A point’s position encodes the recent history of the random draws, most recent first, and nothing else.

This is why the starting point stops mattering so quickly. Each step shrinks any discrepancy by exactly one half, so after \(m\) steps two walks that made the same draws from different starts are within \(2^{-m}\) of each other — around a millionth of the side length by step 20. The initial condition is not so much forgotten as geometrically crushed.

It also says what the holes are: a point in the central gap would require a sequence of corner choices that no sequence can produce, because every reachable point lies in A’s third or B’s third or C’s third, and the middle belongs to none of them. The same argument applies inside each sub-triangle, forever. The chaos game does not remove the middles. It simply never had a way to reach them.