Vignette 9
The Chaos Game

The Chaos Game is played as follows:

On a sheet of paper, mark the three vertices of an equilateral triangle.  (Variations of the game use triangles of other shapes.)  Mark the vertices A, B and C, as shown below.

With a pencil or pen, mark any other point chosen at random on the paper.  We will call this point P.  You should mark the point, but don't label it.  Now roll an ordinary 6-faced die.  If the die comes up 1 or 2, measure half the distance from P to vertex A, and plot a new point there.  (Remember where this point is, but don't label it.)  If the die shows 3 or 4, do the same thing, but instead go half the distance toward vertex B.  If the die shows 5 or 6, go halfway to vertex C.  Continue this process, using your newly marked points as the new starting points for each move.  Play for about 30,000 moves or until you get tired -- whichever comes later.

The Chaos Game

It seems intuitively clear that "chaos" would be a good word to describe this game.  After all, you are marking 30,000 points, each of which is selected by applying a random process -- the roll of a die.  And each game should progress differently, since there is randomness involved in each move.  After 30 rolls of the die in one play of the game, the following points were plotted:

Of course, if you start with a point within the boundaries of the triangle, then all of the points will stay within the triangle.  So it is not unexpected that all of these points are contained within the triangle.  But is there any other pattern that we do not yet see?  Let's continue to play the game, this time for a total of 100 rolls:
After 400 rolls of the die, a pattern begins to emerge:
And after 30,000 rolls of the die, the pattern is quite obvious:
Rather than a random spattering of dots, we find that the points plotted all fall in the Sierpinski gasket, a fractal set that you saw in the vignette on The Snowflake Curve and Other Fractals.

Order in Chaos

One of the strange allures of mathematics is that it often happens that there is an eerie kind of order lurking just behind the scene in what at first appears to be chaos!  In this particular case, however, it is not that difficult to believe that the chaos game should indeed give rise to the Sierpinski gasket.  Let's denote the Sierpinski gasket by the letter SIf we start with a point P that just happens to be one of the points in S, then the next point (which is halfway toward one of the vertices) will also be in S.  (This can be proven algebraically, but it is easy to convince yourself from the picture that this will be the case.  Just try it with a few of the points shown in S above.)  So in the case that we happened to start with a point in S, then the next 30,000 points plotted will also be in S.

On the other hand, if we start with a point P that is not in S, then none of the 30,000 points plotted will actually be in S!  (Try this by looking at a point P that is in the large omitted triangle in the middle of the picture above.  If we move halfway toward a vertex, we will be in the next-smaller-sized omitted triangle that is closer to that vertex.  And that pattern of not being in S will continue indefinitely.)  However, with each roll of the die, the point plotted is closer to some point in S.  Specifically, if the initial point P is a distance d from the closest point in S, then after the next roll, our distance from some point of S will be d/2.  Since the distance from S is halved with each roll, it follows that after only 10 rolls, our distance from some point in S will be , which is less than , and after 30 rolls, the distance from S is , a distance which is imperceptible on even the highest resolution display device.  Thus, after a relatively small number of rolls, it appears that all of the remaining points are in S.  So the Chaos Game may not always draw a picture of S, but it will at least always give a good forgery!  To make the forgery even better, we simply omit the first 30 points when drawing the final picture.

Variations of the Chaos Game

The process of moving half the distance to a vertex can be accomplished by applying a transformation of the plane.  In order to obtain algebraic formulas for the three transformations used in the Chaos Game, let's place the lower left vertex A at the origin of the plane.  If the coordinates of the point P are , then the point that is half the distance toward A will be .  Mathematically, we can express this process as a transformation of the plane: .  The transformations T2 and T3 corresponding to the other two moves in the Chaos Game can be expressed by similar formulas.  The Chaos Game is played mathematically by (many times) randomly selecting one of T1T2 or T3  and applying it to the previously plotted point.

We can vary the Chaos Game mathematically by varying the transformations.  This is much, much easier than inventing a geometric interpretation of each new variation!  The only stipulation is that the transformations must be based on linear processes, and must reduce distances.  The discovery that these two conditions will guarantee a bounded picture as a result is actually quite recent, dating back only 15 years or so.  The underlying mathematics belongs to an emerging field known as fractal geometry.  A few examples of the kinds of images that can result from such variations of the Chaos Game are shown below.  You can click on each of the thumbnail images to get a larger version.  Some of these images have been designed to resemble things found in nature.

Further Exploration

• Spanky Fractal Database (the best source of all things fractal)
• Chaos in the Classroom