Given IFS rules, the Deterministic Algorithm renders a picture of the fractal by applying all the rules to any (compact) initial picture, then applying all the rules to the resulting picture, and continuing this process. Regardless of the starting shape, this sequence of pictures converges to a unique limiting shape, the only (compact) set invariant under simultaneous application of all the rules.
The Random Algorithm is another method of rendering the fractal determined by a given set of rules, T1, ..., TN. Start with a point (x0, y0) belonging to the fractal. (For example, take (x0, y0) the fixed point of one of the Ti.) Let {n1, n2, ... } be a random sequence of numbers, each from {1, ..., N}. (In a moment we'll say why "random" is important.) Generate a sequence of points
| (x1, y1) = Tn1(x0, y0), |
| (x2, y2) = Tn2(x1, y1), |
| ... |
This sequence of points eventually will fill up the fractal to any prescribed accuracy. For example, here are pictures of the Random Algorithm applied to the gasket rules.
|
|
The left picture shows 500 points, the right 5000.
Try it here
Why should the Random Algorithm and the Deterministic Algorithm produce the same picture? To undersatnd this, we use the concept of addresses of a fractal, for a given set of transformations T1, ..., TN. Then the same picture results from this property of randomness: every infinite sequence of random numners contains all finite sequences.
Why should infinite sequences of random numbers have this property? To answer this, we must think of the more general question, "What makes an infinite sequence of digits random?"
Are these random sequences?
(a) 1111111111111111111111111111...
(b) 1212121212121212121212121212...
(c) 1010010001000010000010000001...
(d) 1415926535897932384626433832...
Of course, these are just finite sequences, but they will show us the way to the answer.
Sequence (a) appears to be all 1s, certainly not random. Sequence (b) alternates 1 and 2, (c) alternates 1 and strings of consecutive 0s, with the number of 0s in each string increasing by one from one string to the next. What about (d)? It is the first 28 digits in the decimal expansion of pi.
We'll take this definition of random. An infinite sequence of digits is random if it cannot be specified completely in any way shorter than listing the whole sequence. With this definition, certainly sequences (a) - (d) are not random.
So how can we make a random sequence? To make the explanation easier, we'll consider only random sequences of 0s and 1s. To make an infinite random sequence of 0s and 1s, toss a coin infinitely many times. Each time a heads comes up, put a 1 in the sequence. Each times tails comes up, put a 0 in the sequence. So if the coin toss started out
heads, heads, tails, heads, tails, tails, tails, heads
the random sequence would start
11010001
Why does random imply all finite sequences will occur somewhere in the infinite sequence? Suppose we have an infinite sequence of 0s and 1s, and nowhere in the sequence do we find 000. By the definition given, this infinite sequence is not random. Why? Suppose we're describing the sequence by listing all its terms. Whenever we get to a 00 pair, we don't have to say what the next number is. It MUST be 1, because otherwise the infinite sequence would contain 000. Consequently, we don't have to list the entire infinite sequence to specify it completely. We say once the sequence does not contain the triple 000, and then whenever the pair 00 occurs, we know the next number must be 1.
Similar arguments show that all finite sequences must occur somewhere (in fact, infinitely often) in an infinite random sequence. If any one is missing, we can use this missing sequence to describe the infinite sequence without listing all its entries.
This property of randomness guarantees that the random and deterministic algorithms produce the same picture.
Return to IFS