School of Computing. Dublin City University.
Online coding site: Ancient Brain
x := λ x (1-x)for certain values of λ (lambda) and certain starting values of x in the range:
0 < x < 1(Note that starting with x=0 or x=1 will just cause x:=0 forever.)
I often use := for assignment to distinguish from = for equality.
0 < λ < 4
(λ=0 obviously causes x:=0 forever.)
For example, put λ = 2. You will see that the stable solution for the equation is x = 0.5. You will also see that for any starting value of x from 0 to 1, the process will actually converge to this stable value x = 0.5, e.g. try starting at 0.1 or 0.9.
It is known (though not proved here) that for 1 < λ < = 3 the process will converge to the stable solution. Though for precisely 3, convergence is dramatically slow.
Q. For λ =
1 + √5,
is one of the attractors
Prove it either way (by applying update twice and seeing if get back to 0.5 exactly).
Now try λ = 3.5. Again, there is a stable solution (at x = 5/7 = 0.7142857142857), but again it is largely irrelevant because all other values end up in an attractor cycle. Note that as we increase λ, the length of the cycle is increasing. Now the cycle is of length 4, e.g. start at x = 0.875.
Q. For λ = 3.5, is one of the attractors
Prove it either way (by applying update 4 times and seeing if get back to 0.875 exactly).
The length of the cycle goes to infinity as λ increases.
In fact, the length of the cycle goes to infinity as λ goes to a constant (the "accumulation point") which is approximately 3.569945672. Between approximately 3.569945672 and 4, we have new behaviour.
Oddly enough, there are sub-regions in which oscillation between a few values
e.g. λ = 1 + √8 = 3.82842712474619009760
Stable soln 0.73879612503625855748588356095603.
Other start values bounce between 3 values.
Start at 0.16.
From now, we will look at λ = 4, for which there are no oscillations.
In general, given any number c between 0 and 1, there are exactly 2 solutions, both between 0 and 1, to:
4 x (1-x) = cWe can see this as follows:
Now c is between 0 and 1, so (1-c) is, so
So (1 + √1-c) / 2 is between 1/2 and 1.
And (1 - √1-c) / 2 is between 0 and 1/2.
Each solution is of course (1 - the other solution).
So we have 2 unique numbers that lead to c after 1 more iteration.
x = 0.5 - goes to 0 after 2 steps 2 numbers - go to 0 after 3 steps 4 numbers - go to 0 after 4 steps 2^3 numbers - go to 0 after 5 steps 2^4 numbers - go to 0 after 6 steps ...If we consider a sequence of any finite length n, there are a finite number of 2(n-2) real numbers in the interval 0 to 1 that have converged to 0 at the end of that sequence of n iterations. Obviously, there are an infinite number of real numbers that have not.
x = 0.75 - goes to 0.75 after 0 steps 2 numbers - go to 0.75 after 1 steps 4 numbers - go to 0.75 after 2 steps 2^3 numbers - go to 0.75 after 3 steps 2^4 numbers - go to 0.75 after 4 steps ...If we consider a sequence of any finite length n, there are a finite number of 2n real numbers in the interval 0 to 1 that have converged to 0.75 at the end of that sequence of n iterations. Obviously, there are an infinite number of real numbers that have not.
If the starting value of x is 0.75 it will stay at that value forever. However, other starting values (apart from the unusual special cases just listed) do not converge to 0.75, or indeed to anything, e.g. try starting at x = 0.7. You will see that values bounce around randomly in the interval between 0 and 1 forever. The length of the attractor cycle has gone to infinity. Even try starting at x = 0.7501. You will see that it will rapidly diverge from 0.75, and never go back.
This illustrates the classic chaotic property that tiny initial differences lead to massive differences later. Here is a system that is deterministic yet unpredictable.
Let f(x) = the result of applying the update to x 29 times with λ = 4.i.e. f(x) = the last line of the sequence here. There are 227 real numbers for which f(x)=0 converged. There are 229 real numbers for which f(x)=0.75 converged. And there are an infinite number of other real numbers whose f values go all over the interval 0 to 1. Note that it is symmetric: f(c) = f(1-c).
f(0.751) = 0.16135 f(0.752) = 0.62721 f(0.753) = 0.04611 f(0.754) = 0.81176
A smooth curve going up between 0.751 and 0.752?
No. It bounces around in that interval:
f(0.751) = 0.16135 f(0.7511) = 0.96567 f(0.7512) = 0.74842 f(0.7513) = 0.97527 f(0.7514) = 0.08098 f(0.7515) = 0.63691 f(0.7516) = 0.23017 f(0.7517) = 0.68586 f(0.7518) = 0.12163 f(0.7519) = 0.49033 f(0.752) = 0.62721
A smooth curve going up between 0.751 and 0.7511?
No. It bounces around in that interval:
f(0.751) = 0.16135 f(0.75101) = 0.32690 f(0.75102) = 0.43537 f(0.75103) = 0.46383 f(0.75104) = 0.40957 f(0.75105) = 0.27892 f(0.75106) = 0.10807 f(0.75107) = 0.00091 f(0.75108) = 0.12277 f(0.75109) = 0.54406 f(0.7511) = 0.96567
and so on, for all the other tiny intervals.
Note it is symmetric: f(c) = f(1-c).
f(0) = 0. f(0.5) = 0. f(1) should be = 0 but is not because of a compiler bug.
Is this what f looks like? No. Let's plot in steps of 0.01:
Is this what f looks like? No. Let's plot in steps of 0.001:
Is this what f looks like? No. Let's plot in steps of 0.0001:
gnuplot can't really draw it. To draw it is to more or less just fill the square (x=0 to x=1, y=0 to y=1) with points.
Q. Is it really to fill the square with points?
1000 samples between 0 and 0.01.
Is that all the detail there is? No:
This does 10,000 samples between 0 and 0.01.
Q. Does it always go to minus infinity?