Wednesday, June 13, 2012

Iteration and Chaos Theory

Obviously, this post will not be too involved, as the subject is an extremely deep one. In all probability, you have already heard about chaos theory, from some source of other. The idea, such as it was, may have been that, for example, a butterfly flapping its wings in the desert, can cause hurricanes, or something similar. As analogies go, it is a horrible one, since it is extremely obfuscated. The only way to understand what it is an analogy for, is to already know the thing it is an analogy for.

In fact, what the butterfly truism tells us is that, with some processes, a small change in the initial conditions can have a disproportionate, enormous effect on the results. It is not that a butterfly causes hurricanes; but if all the other necessary conditions are already there (within a specific distance of the equator, a sufficiently high temperature, a sufficiently low pressure, a large area of water), then a butterfly's flapping could be the catalyst which starts a process, which itself eventually pushes the system over the edge and causes the hurricane to emerge. In the same way, however, a butterfly's flapping wings could be the catalyst that slightly increases the air pressure and therefore stops a hurricane from appearing, instead.

The type of process studied by chaos theorists is known as a dynamic process. In general, one tries to find out the effect of taking a function and applying it to a successive sequence of inputs, each input generally being the previous output. As a very trivial example, we could take the function f(x) = 2x. If we start with some number for x, e.g. 3, and then each time we apply the function, we use the new result as our new x, we get the following sequence: 3, 6, 12, 24, 48, 96, 192 and so on. Clearly, the numbers in this sequence, will grow without limit. That is, the sequence goes to infinity, or diverges. If, instead, we start with x = 0, our sequence becomes 0, 0, 0 ... i.e. x never changes. The sequence is convergent. It is also fixed.

The process of applying the same function successively to its own outputs is known as iteration. The numbers 3 and 0, used as the initial values are known as the seeds for our iteration. 0 is also known as a fixed point of the function.

As we can easily see, unless x = 0, this function will diverge. This makes it simple to understand and therefore uninteresting. The same is true of a function like f(x) = x/2 where, for any seed we get convergence to the fixed point 0. However, there are functions which produce surprisingly unexpected results. These are known as chaotic functions. For example, we have the function f(x) = 1.25 - x^2. It has two fixed points, but beyond those, any conceivable seed between -2 and 2 will create a sequence that is simply unpredictable in its course. Naturally, the same is true of other types of functions.

As I mentioned, a chaotic function is interesting, because it is not simple to predict how it will behave over iteration. For example, it is not a simple matter to predict stock market fluctuations. This is partly because of the huge number of parametres involved, but also because of the chaotic nature of the processes involved.