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.
-
ALGORITHM OF THE CHAOS GAME
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
:

-
RESULT OF THE CONSTRUCTION
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.

-
WHY DO WE FIND THE SIERPINSKI TRIANGLE ?
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