The Chaos Game (Chapter 6)
Up to now we have used IFS's to draw fractals by iterating the IFS starting with an initial image. By the the Contraction Mapping Principle, the image W^n(A) will look like the fixed point (fractal) of the IFS as n tends to infinity. We also estimated how long, i.e., how large n has to be, before the image W^n(A) looks like the fractal (see 4 February comments). There we concluded that while for some fractals like the Sierpinski triangle it doesn't take very long for the IFS to get a good impression of the fractal, for other fractals it is just impossible for the computer to draw the fractal completely. Such is the case for the Barnsley Fern, for example. (This is discussed in Section 5.5 of the text).
We now describe another way to draw fractals; the so-called chaos game. Here we still use the IFS, but not in the same way as before. Suppose the IFS is W = w1 U w2 U ... U wk. Let p1, p2, ..., pk be probabilities, i.e., pi > 0 and p1 + p2 + ... + pk = 1. The chaos game for this IFS is played as follows. Start with any point z0 on the fractal (even if z0 does not lie on the fractal this is ok). Then choose one of the numbers 1,2,...,k at random according to the probabilities p1,...,pk (so this means that on average, 1 will be picked p1*100 percent of the time, 2 will be picked p2*100 percent of the time, etc). For example, if k = 6 and pi = 1/6 for each i (equal probabilities), you could roll a die and which ever number came up would be the number you choose (there are 6 sides to a die with the numbers 1 to 6 on them). Or if k = 3 you could roll a die and if any of the numbers 1,2,3 came up you would pick 1, if 4 or 5 came up you would pick 2, and if 6 came up you would pick 3 (so p1 = 1/2, p2 = 1/3, p3 = 1/6; unequal probabilities).
Suppose the first number choosen is s1 (s1 is one of 1,...,k). Then the second point z1 of the chaos game is z1 = ws1(z0). To obtain the next point of the chaos game, one number of 1,...,k is again choosen randomly according to the probabilities p1,...,pk. Call this number s2. Then the next point z2 is z2 = ws2(z1) = ws2(ws1(z0)) which we will write simply as z2 = ws1 ws2(z0). Thus, we obtain a sequence of points {z0, z1, z2, ... }. This (infinite) sequence is one run of the chaos game. It is proven in the text on page 317 that any run of the chaos game will eventually fill the fractal; see also page 305.
As an example, suppose we play the chaos game with the Sierpinski triangle. Here, the IFS is W = w1 U w2 U w3, where w1 = A, w2 = A + (.5,0), w3 = A + (.25,.5), and where A is the diagonal matrix with diagonal entries 1/2. Note that the fixed points of the wi are; (0,0) for w1, (1,0) for w2, and (.5,1) for w3. Let z0 be the initial point, say, z0 = (.5,1). Now roll a die and pick one of the numbers 1,2,3 according to the uniform probabilities pi = 1/3 described above. Suppose that 2 is picked (so s1 = 2). Then the next point in the game is z1 = w2(z0) = 1/2(.5,1) + (.5,0) = (.75,.5). Notice that z1 is obtained by traveling half the distance to the fixed point of w2. This holds in general: to obtain the game point zn+1, pick a number from 1,2 or 3, call this number sn1, and move one-half the distance from zn to the fixed point of wsn1; this is zn+1. (See page 298 of the text.) This is the Chaos Game for the Sierpinski IFS; for other IFS's, the 'rules' may be more complicated (see the commentary for 16 Feb, 2001).
See the Chaos Game page for examples of fractals drawn with the chaos game.
It takes about 1000 steps in the game as described in the previous paragraph to see the Sierpinski triangle clearly, and by 10,000 steps you are done (no more details can be seen by continuing the game); see Figure 6.2. For the Barnsley Fern, however, the situation is different. In that case there are 4 transformations w_1, ... w_4 in the IFS. If we assign them equal probabilities, p_i = 1/4, then even after 100,000 steps in the chaos game we do not see the whole fern; Figure 6.4. So we can not draw the fern this way with the chaos game (even though in principle the chaos game will draw the fractal in the limit as n tends to infinity, but in this case n will hve to be impossibly large; see below).
However, if we adjust the proabilities (so they are not all equal) we can obtain a good image of the fern with 10,000 or so steps of the chaos game. To decide how to adjust the probabilities we have to figure out why the chaos game doesn't give us a good image when we use equal probabilities p_i = 1/4. To do this we have to discuss the addresses of points on the fern. Addresses for the Sierpinski triangle are discussed in Section 6.2, and for the fern on page 326. Without going into all the details here, addresses of pieces of the fractal of any IFS are assigned according to the transformations w_i that make up the IFS. Small self-similar pieces of the fractal can be labeled by a certain sequence of the numbers 1,...,k. Suppose the sequence is s1, s2, ..., sm where each of the s1,...,sm are one of the numbers 1,..,k. Let A be an initial image for the IFS (so for the Sierpinski triangle A could be the large triangle that outlines the fractal, or it could be the unit square; for the fern A could be the outline of the fern in Figure 5.48). Then w_s1 w_s2 ... w_sm(A) is the part of the fractal that has the address s1,s2,...,sm (see Figures 6.14 and 6.24 for example).
Now, the probability that a game point falls in the piece of the fractal with address s1,s2,...,sm is p_s1*p_s2*...*p_sm (product) so if we have done n steps in the game we will expect n*(p_s1*p_s2*...*p_sm) points in that piece of the fractal (see Equation (6.3) on page 325 in the text). If this number p_s1*...*p_sm is smaller than 1/n, then we expect no points to fall in that piece of the fractal during the first n steps of the game.
Let's consider the example of the Sierpinski triangle with equal probabilities p_i = 1/3. Suppose we will play the game up to n = 100,000. Then p_s1*...*p_sm = (1/3)^m, so as long as m is less than 16 we expect at least one game point to lie in that part of the fractal with address s1,...,s2. This sub-triangle has size (1/2)^16 (!!) which is way too small to be seen on any computer screen. The smallest sub-triangle discernable is about size (1/2)^10 (this will shrink a 1000 by 1000 pixel square to one pixel), so these small triangle will contain about 100 points each, more than enough to fill out the Sierpinski triangle. It's different for the fern when we have equal probabilities p_i = 1/4. The tops or ends of the subferns have addresses that begin with a 3 and end with a tail of 1's (see page 326,327). The address of the nth branch up along the main stem is 11....13 where there are (n-1) 1's (Figure 6.24). Say you want to see game points in the 15th branch of the fern. The probability of seeing a point here is (p_1)^(14)*(p_3) = (1/4)^(15) = 10^(-9), so you need 10^9 steps in the game to get a point up here! I think it would take a VERY long time for your computer to plot a billion game points. So if we only have 100,000 points, we wouldn't expect any points to lie above the eigth branch. This is why the fern looks incomplete when we play the chaos game with equal probabilities (Figure 6.4).
We can obtain a much better result (i.e., a much better image of the fern) by adjusting the probabilities. Roughly speaking, the problem with uniform probabilities is that too many of the game points end up on the lower branches of the fern. After a while those lower branches get saturated with points and we would like to put the succeeding points up into the higher branches. We can accomplish a similar result if we move some of the points that end up on the lower branches up to higher branches; that is, if we change the probabilities so that there is some chance that some of those many points that are falling on the lower branches get put into the higher branches. To this end we change the probabilities so that p_1 is much greater than the other probabilities (recall that w_1 is responsible for building the higher branches of the fern). In fact, if p_1 = .85 and p_2 = p_3 = p_4 = .05, then we will expect about 500 game points to fall in the 15th branch of the fern (see page 326). Thus, with these (nonuniform) probabilities we obtain a good image of the fern (see Figure 6.4).