Fractals and the Chaos Game

Today's topic is the Chaos Game (which it should be noted has no relation to chaos) in which a string of random numbers is used to generate very complicated fractal patterns. Two specific examples of this game can be found for Sierpinski's Gasket and Sierpinski's Carpet, as well as the general rules (although it should be noted that the screensavers mentioned on these sites are approximately ten years old, and are no longer maintained)

The general rules of the game are:

1. The first, and most important step in producing a chaos game fractal is to choose a fractal which will work! The Selection Rules are:
1. The set of points contained in the fractal MUST be bounded. This means basically the fractal has no points at infinity, or that it can be enclosed in a big enough circle.
   
2. It SHOULD have obvious transformations which leave parts of the fractal unchanged. For example, in the Sierpinski Carpet, a large square is composed of eight small squares which are exactly the same as the large square. This the reason why the Mandelbrot set is an unwise choice for the Chaos Game.
2. Define S to be the set of all points contained in the fractal.
3. Now create a set, V, containing all of the possible mappings from S into S.
4. Define T to be a finite subset of V, such that the union of the ranges of the mappings in T is equivalent to S.
5. Now define the rules for this version of the Chaos Game to be:
   1. Select a point which is known to be in the fractal.(You must know at least one point to determine the location of the fractal anyways). Call this the current point.
   2. Randomly select a mapping in T, and apply that mapping to the current point.
   3. Redefine the image of the current point as the new current point, and repeat the last step and this step.

If these rules appear too complicated, go back to the two specific cases listed above and compare those specific cases to the general rules.

If you follow the rules correctly, you should see a few randomly placed dots slowly turn into a beautiful fractal! So why does it work? Because of the nature of these fractals - they are, by definition, similiar to themselves. Let us start by looking at a very simple shape - the circle. The rules for this game would be choose a point to be the origin and then another random point. Then rotate around the origin by a random amount and draw another point, and then repeat the process. Eventually you will get a circle. Since the circle is invariant under rotations, you can choose ANY point in the circle and any rotation and hit another point on the circle! The random part is simply the order in which the points are drawn, but eventually all points would be drawn in.

The same argument works for the more complicated fractals. Every symmetry of the fractal provides a transformation which leaves the fractal unchanges, so any point you choose can be transformed to another point in the fractal. And again, the random part simply determines the order in which the points are added. But since the rules are simple, and the player has a free choice of the random numbers, it seems magical to see a fractal pattern appear!