Chaos game

Each roll of the chaos game moves a point a fraction r of the way towards one of the points $v_1, \dots, v_N$, chosen at random. In other words, it applies one of the maps

which shrink the plane by the factor s towards $v_i$. The dragon and the fern use affine maps $f_i(x) = A_i x + b_i$ instead. Here you can move the points, turn r, restrict the next roll and change the odds, and see which pictures the dice draw.

The picture counts landings: the more points land in a pixel, the stronger its colour. Last roll colours each landing by the point or map its last roll chose, and Previous roll by the roll before. Where colours mix, landings of different colours share a pixel.

Why does every game draw the same picture? Take rolls without memory first. Each map shrinks distances, so two points that follow the same rolls draw together. There is exactly one non-empty compact set K made of its own copies,

A point of K stays in K whatever is rolled, so the game’s distance to K tends to zero, and the start is forgotten.

The last k rolls put the point near one small copy of K, and earlier rolls only decide where near that copy it is. So Last roll shows the N copies, and Previous roll the $N^2$ smaller ones, each a copy of the whole. If every map has a chance, almost surely every finite sequence of rolls turns up sooner or later, so the points come close to every part of K. The copy machine needs no dice at all. It shrinks a whole shape into its N copies and repeats, and from the enclosing outline or a rabbit it closes in on the same K. The rabbit shows whether a map turns or flips.

When the points’ convex hull is a polygon and its N copies meet at most along their edges, the picture has dimension

The triangle at r = 1/2 has $D = \log 3/\log 2 \approx 1.585$, and the carpet at r = 2/3 has $\log 8/\log 3 \approx 1.893$. When the copies overlap, this number is only an upper bound, and the page gives no dimension. When they cover the whole polygon, the polygon is made of its own copies, so by uniqueness it is the picture: solid.

With No repeats or No neighbours, the next roll depends on the last one, and neighbours go by the points’ numbering, which dragging does not change. The picture then splits by the last roll into pieces, each a copy of the pieces allowed just before it. So a restriction can change the shape itself: at r = 1/2, a square with no repeats is no longer solid, but a fractal of dimension $\log 3/\log 2$.

As long as every map has some chance, the odds do not change K. They only decide how the landings spread over it. The fern is drawn By area. With Equal odds the leaf keeps its shape, while the stem gets more points and the tips fewer.

Michael Barnsley’s book Fractals Everywhere (1988) made drawing these pictures with random rolls widely known as the chaos game.