Why does the Chaos Game generate a fractal?

Question

To generate the Sierpinski triangle illustrated below, there are at least $3$ approaches:

1. The Deterministic IFS Algorithm: Determine the affine transformations $T_1,T_2,T_3$ that characterize the fractal, and given an initial compact $P_0$, iteratively compute $$ P_n= \bigcup_{i=1}^3T_i(P_{n-1}) $$
2. The Random IFS Algorithm: Determine the affine transformations $T_1,T_2,T_3$ that characterize the fractal, and given an initial compact $P_0$, iteratively compute $$ P_n= T_i(P_{n-1}), $$ where $i\in \{1,2,3\}$ is randomly chosen at each step.
3. The Chaos Game: Given a starting point on the edge of the largest triangle of the fractal, iteratively move half-way between the current point and a corner of the triangle.

It makes sense to me why the first two approaches generate the same set: roughly speaking, the random IFS algorithm applies the same sequence of transformations as the deterministic one, but in a different order. What I don't understand is why the Chaos game produces the same result, without using any information from the transformations $T_1,T_2,T_3$, hence my question:

My question:

Why does the Chaos Game on a triangle generate the Sierpinski triangle? Given that the Random IFS algorithm is a generalization of the Chaos game, how can we relate the two methods ?

Answer 1

Someone hinted the answer to me, but deleted it. This person was absolutely correct, only the answer was incomplete (as it was a hint). This person said:

When you perform the chaos game, you actually perform transformations $T_1,T_2$, and $T_3$.

Here is why this is correct: the transformations for the Sierpinski triangle are: \begin{align*} T_1(x,y)&=(x/2,y/2)\\ T_2(x,y)&=(x/2+1/2,y/2)\\ T_3(x,y)&=(x/2+1/4,y/2+\sqrt{3}/4)\\ \end{align*}

And when you iteratively move half-way between the current point $(x,y)$ and a corner $(X_i,Y_i)$ of the triangle , you get the point with coordinates: $$ (X_i+\frac{1}{2}(x-X_i),Y_i+\frac{1}{2}(x-Y_i)) $$

If we replace $X_i,Y_i$ with the coordinates of the corners, we end up with exactly $T_1,T_2,T_3$.

Answer 2

You've already got an answer, so I'll just give you another way to look at it using barycentric coordinates.

We usually think of points in the plane with two coordinates, but when we're dealing with a triangle $ABC$, it's often more natural to consider three coordinates that add to $1$. So we can define $A = (1, 0, 0)$, $B = (0, 1, 0)$, and $C = (0, 0, 1)$, and every other point in the plane is just a weighted average of those three.

The Sierpinski Triangle in barycentric coordinates is given by the triples $(a, b, c)$ such that $0 \le a, b, c \le 1$, and when represented in binary, exactly one of $a, b, c$ has a $1$ in each position.

The move described in the chaos game (say toward $A$) moves from $X = (a, b, c)$ to $(\frac{1}{2} + \frac{a}{2}, \frac{b}{2}, \frac{c}{2})$ (the average of $X$ and $A$).

It's fairly simple to see that this move preserves points in the Sierpinski Triangle, and with enough moves, you generate a dense subset of it. In fact, the Sierpinski Triangle is an attractor for this move, and any starting point in the plane will tend toward it.