The Chaos game

The chaos game has been introduced by Peitgen and Saupe. This absolutely chaotic algorithm produces an ordered and regular structure when iterating to infiny : the Sierpinski triangle.


  Choose any triangle you want and color the vertices : one red, one blue and the last green.
Take a die and color two faces in red, two blue and two green.
Choose a point in the plane of the triangle = seed.
Roll the die.
Move the seed half the distance to the appropriately colored vertex given by the die.
Continue the process as indicated on the figure below :



The first iterations must not be recorded. After around ten initial rolls, record the position of the points. To infiny, the resulting image is, with probability one, the Sierpinski triangle. The orbit of any seed will fill out the triangle even with a seed very far from the triangle but in this case, you will need more initial rolls.
So you get this picture where the colors indicate the proximity of the vertex with the given color.


It seems at first time very strange that the Sierpinski triangle emerges from the random chaos game. But you can easily understand it with the following geometrical reason :
Take a seed into the the middle largest triangle of the Sierpinski triangle above. Then, roll the die and record the successive positions of the point.
After the first roll, it reaches one of the three next-smaller triangles.
After one more iteration, this point moves to the next smallersize triangles and so forth.
In fact, if you begin with a seed into the middle triangle of the Sierpinski triangle, points will always fall into removed triangles. But after some iterations, triangles are so small in size that you can no more see them.  So the orbit of the seed looks like it lies on the Sierpinski triangle; actually it will never reach it but just tends closer and closer to it. That's why the Sierpinski triangle is called a strange attractor it means that the orbit is "attracted" to the Sierpinski triangle but never reaches it.
 
 
 

see the chaos game algorithm and program