This is a brief description of a few topics from Chapters 8 and 9 that were not covered in detail in class. These notes are for your interest only; they will not appear in any test.
A cellular automata is a collection of cells (say, a grid of squares) each of which behaves 'automatically', i.e., like a robot. Each cell follows certain 'rules'; the rules of the automaton. Typically, these rules involve only the neighbours of the cell, so the rules act 'locally'. However, because the neighbours of the neighbours, etc., eventually reach over the entire grid, these local rules have far-ranging effects. One begins with an initial configuration of the cells, and then lets the cells 'evolve' according to the rules. Each application of the rules is one step in the evolution. One of the questions to investigate is what is the large-scale structure that results from a given set of rules, or conversely, what are the rules (if any) that will produce a certain large-scale structure on the grid.
An example of a cellular automata is the "Game of Life" (pages 413-415). We colour a cell black if it is alive and white if it is dead. The rules are as follows. If among the 9 nearest neighbours of a cell two or three are alive then the cell remains alive. If more than three neighbours are alive then the cell dies (too much competition). If less than two neighbours are alive the cell dies (of loneliness). A cell becomes alive if exactly three of its neighbours are alive. There is a great variety of patterns that may result in the game of life; 'colonies' (i.e., groups of cells) that have a periodic cycle (as the game evolves the colony changes shape but then returns to its initial configuration), colonies that move across the grid ('migration'), colonies that shoot off smaller colonies, 'ships' that leave a trail of smaller colonies as they travel along, etc. (see Figure 8.8)
Another example of a cellular automata has for its rules the "majority rule"; if five or more of its nine neighbours is alive then the cell becomes or remains alive, otherwise it will die or remain dead. In this case, a stable pattern usually results after many iterations (ie., a pattern that does not evolve anymore); see Figure 8.11. Starting with different initial patterns a different final pattern results, but these final patterns have some similarities such as the total area of black cells is (roughly) the same, the largest and smallest pieces of constant colour are (roughly) the same. One can ask what properties the stable pattern will have given the rules of the automata.
Cellular automata has become an important method in modeling and simulation in many areas of science and technology such as physics, chemistry, biology, engineering, sociology, and finance.
We can 'randomnize' fractals in several ways. For example, during the 'geometric construction' of fractals we can apply, say, one of two rules randomly. Take the Koch curve. If instead of adding the smaller triangles always on the 'top' of the curve we sometimes add them to the 'bottom' of the curve, and choose whether we add them to the top or bottom randomly, then we obtain a fractal-like curve that is not exactly self-similar (see Figures 9.1 - 9.3). This curve looks more 'realistic' than the original Koch curve, and gives a good impression of the coastline of an island.
As another example, we can randomize the Sierpinski algorithm in the follwoing two ways. First, instead of dividing the sides of the triangles at each stage at their midpoints (and then removing the middle triangle), we choose the point randomly, i.e., randomly choose a point along each side and join them to form triangles. Then we remove the inside triangle; see Figure 9.6. Or we could divide the triangles into 4 subtriangles of half the size (as we do in the usual construction) but the triangle we remove is choosen at random (instead of always choosing the middle one); see Figure 9.8.
As another random variation, we could divide the triangle into smaller subtriangles of size (1/2)^n and colour each subtriangle black or white according to some random event. For example, to decide which colour to colour a particular subtriangle we could pick a number randomly from [0,1] and colour it black if the number is less than 1/2 and white if the number is greater or equal to 1/2. What results is a pattern of black and white subtriangles. This pattern will be different for different 'realizations', i.e., different runs of the 'game', but the general appearances will be the same (like the total areas of black subtriangles, or whether tha black subtriangles form connecting 'islands'). The colours are choosen randomly; let's call p the probability that a given cell is coloured black (so 1-p is the probability that a cell is coloured white). Then the typical appearance of the pattern produced will depend on the probability p. As an extreme example, if p = 1 then the resulting pattern will be a totally black triangle, while if p = 0 the result will be a totally white triangle. As p varies from 1 to 0 the resulting pattern will go from totally black, through mixtures of black and white, to totally white. At each fixed p, the patterns will (typically) be different for different realizations (runs of the game), but the overall appearance will be the same (as mentioned above). An interesting question is whether the general appearance changes abruptly at a particular value of the probability p. It turns out that this can indeed happen (when it does a 'phase transition' is said to occur). For example, look at Figure 9.8. There we see the final pattern for various values of p. For small p the small black triangles are mostly isolated, but as p increases they become larger and start to join together. At some critical value p_c (which in this case is about 0.6) there suddenly appears a connecting arc of black cells stretching from one side of the triangle to the other. We say then that percolation occurs; if the black corresponds to some kind of fluid (like water) and white corresponds to some material that doesn't allow fluid to pass through it (like stone), then when there is percolation the water can flow through the material. One could also use this model to describe the conductivity of solid-state electronic devices (here the black cells would represent conducting material like some metal, and the white cells would represent some insulating material like glass; the probability p represents the 'doping' or amount of impurity in the material, so at a critical value of p the whole piece becomes electrically conducting).
A fractal is produced by repeating a simple rule over and over again beginning with some geometric object (like a line segment or triangle). Above we saw that by adding a bit or randomness in the Koch curve constuction we could obtain a more realistic curve (the Koch curve has too much symmetry to be realistic). One can produce very realistic landscapes (surfaces) this way too. For example, one could start with a triangle lying flat horizontally. Then displace the midpoint of each side vertically (upwards) an amount that is determined randomly (say, choose a random number between 0 and 1 and displace that amount) to obtain a new object which is no longer flat. Now repeat the procedure; displace the midpoint of each of these sides randomly; see Figure 9.36. To prevent the 'mountain' from getting infinitely high, the displacements at each stage should get smaller and smaller. For example we could choose a number randomly from [0, (1/2)^n] at the (n+1) stage. What results is a good impression of a mountain; see Figure 9.38. This mountain has a fractal-like appearance because it was constructed by repeating the same rule over and over again. The fractal dimension of the resulting mountain depends on the probability distribution of the random displacements and how quickly they decrease in amplitude in each stage. The first collection of colour plates in the text show some examples of 'fractal-landscapes'.
See the Fractal mountains page for examples of mountains drawn in this way.
In a similar way one can simulate Brownian motion and fractional Brownian motion. Brownian motion is the continuum limit of a 'random walk'. In a random walk, a step is taken at each time interval and the direction of the step is random (so in one dimension the step is either forward or backward). Brownian motion was observed by Brown in 1827. He observed the random motions of pollen particles suspended in water and deduced that their motion was due to impacts from water molecules. Brownian motion has many applications in physics, engineering, and finance, to name a few. See sections 9.4 and 9.5.