Bifurcation and the logistic mapping
I've been reading Ian Stewart's book Does God Play Dice? The New Mathematics of Chaos, and I got inspired to play about with some of the stuff described therein. You've probably all seen this image before:
The formula that produces it is almost shockingly simple, and yet the behaviour it produces is really quite surprising: yet another reminder that "complicated" is not the same as "deep".
It all comes from the so-called logistic mapping:logistic(x) = kx(1-x)
It should be reasonably easy to see that if k is between 0 and 4, then this will take a number between 0 and 1 to another number between 0 and 1. One thing to note about this definition: logistic(x + y) is not, in general, equal to logistic(x) + logistic(y); we say that the logistic mapping is nonlinear.
Things start getting interesting when we ask "what happens if we take a number between 0 and 1, and apply the logistic mapping over and over again?" Well, if k is between 0 and 1, it eventually settles down to 0. If k is between 1 and 3, it eventually settles down to some other value (as you might expect, the other solution to the equation x = kx(1-x): once it's reached this, it will stay there forever). But at k=3, something interesting happens: there's still a value of x for which x = kx(1-x), but it's unstable, which is to say that values of x close to the solution no longer get closer and closer with more iterations: instead, small differences get magnified. But the system does eventually settle down; however, instead of a single fixed point, it now goes into a 2-cycle: a pair of values x1 and x2 such that x1 = logistic(x2), and x2 = logistic(x1). For instance, at k=3.072 x alternates between about 0.5746 and about 0.7508. We say that a bifurcation occurs. Then, at around k=3.44, it bifurcates again: instead of cycling between two different values, it now cycles between four different values. At k=3.504, for instance, x goes 0.876, 0.381, 0.826, 0.503, and then back to 0.876. At about k=3.54, it bifurcates again: x now converges to an 8-cycle. Then it bifurcates again, and again, with each bifurcation coming harder on the heels of the last. At around 3.57, it has bifurcated infinitely many times, and becomes chaotic. Let's zoom in on the range 3.1 < k < 3.6:
But the fun doesn't stop there! See that white line at around k=3.8? That's not just an artefact of the drawing process, that actually happens. Let's zoom in on it:
At around 3.83, chaos abruptly ceases, and it becomes periodic again! But now, it has period 3, rather than a power of 2 as before. But look at each of the three threads: just after 3.84, we get another bifurcation, and now we have a six-cycle. Then another, then another... until it eventually becomes chaotic again. in fact, we have three copies of the whole figure! This kind of self-similarity is very common in this kind of situation: you may have seen it in the well-known Mandelbrot set.
In fact, cycles of every possible length exist somewhere in the set - 5-cycles, 73-cycles, 27395269-cycles - and in each case, you get the same behaviour: an n-cycle will bifurcate into a 2n-cycle, which will bifurcate into a 4n-cycle, and so on, and eventually the behaviour will become chaotic again - in fact, you have n copies of the whole set. Here are a few more:
And here's something I discovered for myself: the closer you get to a bifurcation point, the more iterations it takes before x settles down to the attractor. Here's the region around k=3, throwing away the first 500 iterations:
And here it is again, throwing away the first 5000:
Cool, eh?
The formula that produces it is almost shockingly simple, and yet the behaviour it produces is really quite surprising: yet another reminder that "complicated" is not the same as "deep".
It all comes from the so-called logistic mapping:logistic(x) = kx(1-x)
It should be reasonably easy to see that if k is between 0 and 4, then this will take a number between 0 and 1 to another number between 0 and 1. One thing to note about this definition: logistic(x + y) is not, in general, equal to logistic(x) + logistic(y); we say that the logistic mapping is nonlinear.
Things start getting interesting when we ask "what happens if we take a number between 0 and 1, and apply the logistic mapping over and over again?" Well, if k is between 0 and 1, it eventually settles down to 0. If k is between 1 and 3, it eventually settles down to some other value (as you might expect, the other solution to the equation x = kx(1-x): once it's reached this, it will stay there forever). But at k=3, something interesting happens: there's still a value of x for which x = kx(1-x), but it's unstable, which is to say that values of x close to the solution no longer get closer and closer with more iterations: instead, small differences get magnified. But the system does eventually settle down; however, instead of a single fixed point, it now goes into a 2-cycle: a pair of values x1 and x2 such that x1 = logistic(x2), and x2 = logistic(x1). For instance, at k=3.072 x alternates between about 0.5746 and about 0.7508. We say that a bifurcation occurs. Then, at around k=3.44, it bifurcates again: instead of cycling between two different values, it now cycles between four different values. At k=3.504, for instance, x goes 0.876, 0.381, 0.826, 0.503, and then back to 0.876. At about k=3.54, it bifurcates again: x now converges to an 8-cycle. Then it bifurcates again, and again, with each bifurcation coming harder on the heels of the last. At around 3.57, it has bifurcated infinitely many times, and becomes chaotic. Let's zoom in on the range 3.1 < k < 3.6:
But the fun doesn't stop there! See that white line at around k=3.8? That's not just an artefact of the drawing process, that actually happens. Let's zoom in on it:
At around 3.83, chaos abruptly ceases, and it becomes periodic again! But now, it has period 3, rather than a power of 2 as before. But look at each of the three threads: just after 3.84, we get another bifurcation, and now we have a six-cycle. Then another, then another... until it eventually becomes chaotic again. in fact, we have three copies of the whole figure! This kind of self-similarity is very common in this kind of situation: you may have seen it in the well-known Mandelbrot set.
In fact, cycles of every possible length exist somewhere in the set - 5-cycles, 73-cycles, 27395269-cycles - and in each case, you get the same behaviour: an n-cycle will bifurcate into a 2n-cycle, which will bifurcate into a 4n-cycle, and so on, and eventually the behaviour will become chaotic again - in fact, you have n copies of the whole set. Here are a few more:
And here's something I discovered for myself: the closer you get to a bifurcation point, the more iterations it takes before x settles down to the attractor. Here's the region around k=3, throwing away the first 500 iterations:
And here it is again, throwing away the first 5000:
Cool, eh?