# Logistical nightmare

When initially fiddling around and getting to grips with Matlab a while ago, I had a go at implementing the ‘logistic map’, a well known mathematical process which leads to deterministic chaos.

http://en.wikipedia.org/wiki/Logistic_map

The mathematical operations involved are extremely simple, namely for some value of $k$ we repeatedly perform the operation

$x \rightarrow kx(1-x)$.

Starting at $x_0 = 0.5$, after a single iteration we should end up at $x_1 = k/4$, and after another we should be at $x_2 = k \cdot k/4 \cdot (1 - k/4) = k^2/4 - k^3/16$. Continuing this process, you might expect that we should converge on some function $f$ which stipulates $x_{final} = f(k)$. Calculating this function is trivial, we look for a ‘fixed point’ of the map above and solve:

$x = kx(1-x) \Rightarrow x = 1 - \frac{1}{k}$.

If we plot a few iterations and our ‘solution’ below, note a few interesting things.

The functions are all bounded between 0 and 1 for $0 < k < 4$, and increase in polynomial order as we increase the number of iterations, much like a Taylor series. However, the ‘final’ function contains a term $\propto 1/k$, which can’t be approximated by a finite number of positively-powered polynomial terms. In other words, no matter how many iterations we produce, our resulting functions $f(k)$ will never contain a $1/k$ term and so will never quite reach the ‘actual’ function.

This reminds me slightly of a calculation in condensed matter field theory, where the pairing potential between electrons is calculated to be of the form $e^{(1/V)}$, where $V$ is some (assumed small) interaction between electrons. This is then a non-perturbative result, as no amount of perturbation orders, i.e. terms proportional to $V^n$, will lead to a function containing a $1/V$ term.

Anyway, physics distractions aside, we can continue this iteration process and see where we end up.

All of the iterations up to 1000 are plotted on top of one another, the first $k/4$ one is visible, and successive iterations converge upon the blue line representing $x = 1 - 1/k$. Great! That is, until $k = 3$ where something funky happens – the line splits into 2 and diverges from our supposed solution.

Like all great experimental scientists, we should examine our theory again in light of new evidence. Guided by what we’ve seen, lets suppose there exist 2 solutions to our map, call them $x_A$ and $x_B$. Then we have

$x_B = kx_A(1-x_A)$

$x_A = kx_B(1-x_B)$

$x_A^3 - 2x_A^2 + \frac{k+1}{k}x_A + \frac{1-k^2}{k^3} = 0$.

This is a cubic equation with 3 solutions (thank you symbolic algebra toolbox!):

$x = 1 - \frac{1}{k}$

$x = \frac{k \pm \sqrt{(k+1)(k-3)} + 1}{2k}$

Accounting for the possibility $x_A = x_B$, one of the solutions ends up being our original solution which is nice. The second two represent the two new branches of the map above $k = 3$, and as we can see plotted below, fit very nicely. Also, we see why the branches occur at this point – the new solutions become imaginary for $k < 3$ and so the map reverts back to the single solution again.

Unfortunately, at around $k \approx 3.45$ the map splits again, and in solving for this we would have to deal with a 15th degree polynomial, which isn’t ideal. However, by dividing out the above solutions (because 1 and 2 are factors of 4, then the above solutions must be included as we could have all 4 solutions the same, or two sets of two) we end up with a 12th degree polynomial, and by investigating its discriminant we find the onset of the 4 solutions at $k = 1 + \sqrt{6} \approx 3.449...$.

This doubling process occurs quicker and quicker until in a finite period we end up with chaos – the mess above $k \approx 3.5$. Nevertheless there are still patterns in here, hinting at the underlying deterministic order. We can zoom in and we find smaller copies of the overall pattern

and so again in this blog we have what looks like a fractal. Nothing as fancy as complex numbers need get involved here, just the kind of equation you could understand in secondary school, and eminently simple to visualise if you feel like a bit of programming on a wet Sunday afternoon.