What happens when you take f[f[f[f[...f[x]...]]]]?

(Based on a lecture by Prof. L. Polvani; Spring, 1997)

Introduction

I assume you all are comfortable with some level of calculus.  For a function f[x] one is traditionally concerned with "limits", for instance the limit of f[x] as x->∞.  Here, were a going to study another limit, a bit perverse perhaps.  Suppose we are given the function f[x] and we consider the sequence x, f[x], f[f[x]], f[f[f[x]]], etc.  This is easy to do in Mathematica with the function Nest[f,x,n].  Suppose we want to iterate 3 times; then we just do

Nest[f, x, 3]

We  call this the 3rd iterate of f.  Now, the name of the game here is to find the limit of Nest[f,x,n], given a function f, as n->∞.  This turns out to be a very hard and extremely interesting mathematical problem, and is one of the by-now-classic "chaos" problems that was the rage about a decade or so ago.  The best way to get us started is to play around with a specific (and very interesting)  function f[x], the so-called "logistic" function.

The Logistic Map

The logistic map is simply the quadratic function defined by

Logistic[r_][x_] := r x (1 - x)

where r is a parameter; if we choose 0 < r < 4.  Logistic takes the interval [0,1] into itself; in other words it maps [0,1] into [0,1];  this is why we call it a map.  Let's plot this map to see what it looks like, say when r=3:

Plot[Logistic[3][x],{x,0,1},PlotRange->{0,1},Frame->True]

As you can see, Logistic[r][x] is just a simple parabola with a single control parameter, r.

Iterates of Logistic Map

Now let's look at a few iterates of the logistic map.  Let's start with the second iterate, i.e. Logistic[Logistic[x]]

Plot[Nest[Logistic[3],x,2],{x,0,1},PlotRange->{0,0.8},Frame->True]

OK, that's a simple quartic (i.e. a polynomial of degree 4). Now let's look at the 4th iterate

Plot[Nest[Logistic[3],x,4],{x,0,1},PlotRange->{0,0.8},Frame->True]

OK, just a bit more wiggly. Let's keep going; this is the 6th iterate:

Plot[Nest[Logistic[3],x,6],{x,0,1},PlotRange->{0.4,0.8},Frame->True,PlotPoints->100]

It does not seem to be very different from the 4th iterate.  Let's be brave and look at the 14th iterate!

Plot[Nest[Logistic[3],x,14],{x,0,1},PlotRange->{0.4,0.8},Frame->True,PlotPoints->100]

Again, it looks very similar to the 4th and 6th iterates.  However, let's look more carefully at what is happening near the edges.  How many wiggles are near the edges?  Let's look closer...

Plot[Nest[Logistic[3],x,14],{x,0,0.1},PlotRange->{0.4,0.8},Frame->True,PlotPoints->100]

OK, let's blow up some more...

Plot[Nest[Logistic[3],x,14],{x,0,0.01},PlotRange->{0.4,0.8},Frame->True,PlotPoints->100]

Something weird is happening! This function looks the same in the interval [0,0.01] as in the interval [0,0.1]; how can that be?  Let's blow up some more...

Plot[Nest[Logistic[3],x,14],{x,0,0.001},PlotRange->{0.4,0.8},Frame->True,PlotPoints->100]

This is really weird!  Now matter how close we look, this function looks the same!  Lets blow up once more...

Plot[Nest[Logistic[3],x,14],{x,0,0.0001},PlotRange->{0.4,0.8},Frame->True,PlotPoints->100]

OK! What crazy function is this any way?  How bad can it be?  All we did was iterating a quadratic a mere 14 times.  Let's look at the iterates in functional form.  Start with the first non trivial iterate:

Nest[Logistic[3],x,2]

Well, this is not too illuminating; let's make a polynomial out of this; we can do this with the function Expand.

Expand[Nest[Logistic[3],x,2]]

OK, so the second iterate is a polynomial of degree 4; that what we'd expect from the figure (see above); how about the third iterate?

Expand[Nest[Logistic[3],x,3]]

Wow!  It jumps to a polynomial of degree 8!  How about the fourth iterate?

Expand[Nest[Logistic[3],x,4]]

Ouch!  We are starting to get the picture... every time we iterate we get a polynomial of twice the degree as the previous iterate

Expand[Nest[Logistic[3],x,5]]

OK, this is getting ridiculous! Can we figure out the order of the polynomial corresponding to the 14th iterate (that's the function we were looking at before)?  Well for the 2nd iterate the polynomial has degree 4, for the 3rd iterate degree 8, for the 4th iterate degree 16, so it's pretty clear that for the nth iterate of the simple logistic function is actually a polynomial of degree (2^n).  This means that the 14th iterate of a simple parabola (that what our logistic function is) is a polynomial of degree...

2^14

So the 14th iterate of a parabola is a polynomial of degree 16,384, WOW!!!  Now you see why we said we are playing a pretty perverse game, especially if the name of the game is really want to look at Nest[f,x,n] in the limit n->∞!  For a number as small as n=100, which is not exactly close to Infinity, our function has become a polynomial of degree

2^100

Looks big!  How big is this number?

N[2^100]

So if we take only the first 100 steps, we have a polynomial with more than one thousand billion billion billions terms!  It looks like there's no hope for us to do this problem.  But in fact there is...

Point-wise exploration

Obviously, the function becomes extremely complicated as the number of iteration grows.  Suppose try to be more humble, and look at what each point is doing as the number of iterations goes to infinity.  That may be simpler than studying the whole function...

Small r…

So consider, for instance, looking at the value r=2.5 and seeing what happens there...

NestList[Logistic[2.4],0.1,10]

Notice that it seems to be converging... try to go further

NestList[Logistic[2.4],0.1,20]

Well, it seems to be going to the same point.  No matter which x we pick in [0,1] f(f(f(f(...f(x))))) is equal to

N[Last[NestList[Logistic[2.4],.1,500]],10]

N[Last[NestList[Logistic[2.4],.2,500]],10]

N[Last[NestList[Logistic[2.4],.5,500]],10]

OK. From the figures it is pretty clear that no matter which x we pick in [0,1] the iteration converges to the point where Logistic[x] == x; we can solve for this using the function Solve

N[Solve[r x (1-x) == x /. r -> 2.4, x],10]

Yup, that's exactly it.  So, for this value of r we the answer is actually easy: as n->∞ the iterates converge to a very simple function, namely the function f[x] = 5833333333... which is just a constant function.

Medium r…

Of course the question now becomes: what happens if we change r? Does the iteration give an easy function as well? Let's try the value r=3.05.

Hum... after 1000 iterations, it seems to be converging very slowly... may it is not converging at all... perhaps we should look at the numbers...

NestList[Logistic[3.05],0.1,100]

Wow! It seems that for this new value of r the iterates are bouncing between two numbers.  Let's plot these points versus the iteration number n, so we get a better feeling for what is happening...

ListPlot[NestList[Logistic[3.05],0.1,40],Joined->True,PlotRange->{0.5,0.8}]

OK, very nice.  This kind of behavior is called a limit cycle.  The iterates oscillate between the two values 0.590164... and 0.737705... The name of this behavior is called a "limit cycle",

OK, very nice.  Now we should worry:does this limit cycle depend on where we start? Suppose we start at x=.5

ListPlot[Drop[NestList[Logistic[3.05],0.5,100],20],PlotRange->{0,1},Frame->True,PlotStyle->RGBColor[0,0,1]]

Drop[NestList[Logistic[3.05],0.5,100],90]

As for the case r=2.4, it does not seem that the final values of the iterates depend on the initial value of x.  So in summary this is the story:  independent of the initial value of x, for r=2.4 the iteration goes to a single number while for r=3.05 the iteration oscillates between two numbers.  Hence there is a point, let's call it (Subscript[r, 1])where the behavior changes drastically. This is called a bifurcation, a fancy word for saying the something has split into two.  You will have to find the value of (Subscript[r, 1])in your assignment.

Larger r…

Let increase r some more and play more games.  Consider the case r=3.5

Drop[NestList[Logistic[3.5],0.5,100],88]

Well, there seem to be four numbers here!  Let's plot them to see what's happening

ListPlot[Drop[NestList[Logistic[3.5],0.5,500],100],PlotRange->{0,1},Joined->False,Frame->True,PlotStyle->Blue]

This is a limit cycle with twice the period (it take 4 iterations to get back to a given point, instead of two as before).  So as we go from r=3.05 to r=3.5 another bifurcation has occurred, at some point which we call (Subscript[r, 2]).  In this case the bifurcation leads from an oscillation between 2 numbers to an oscillation between 4 numbers.  Hence the period of the oscillation is doubled.

Still larger r…

OK, let increase r a bit more and try r=3.55

r = 3.55;
ListPlot[Drop[NestList[Logistic[3.5],0.5,500],100],PlotRange->{0,1},PlotJoined->False, Frame->True,PlotStyle->Blue]

Again this is a limit cycle with twice the period (it take 8 iterations to get back to a given point, instead of 4 as before).  To make sure of this, look closely and you will see that there are 8 different numbers that keep repeating.  If we blow up the plot between 0.8 and 1 it's clear that there are 4 distinct points there.

ListPlot[Drop[NestList[Logistic[3.5],0.5,500],100],PlotRange->{0.8,0.9},Joined->False,Frame->True,PlotStyle->Blue]

So between r=3.5 and r=3.55 another bifurcation has occurred.  Let's call this point (Subscript[r, 3]).

Onset of chaos for r > 3.5699456…

This period doubling scenario goes on until the magic point (Subscript[r, ∞])=3.5699456... after which point? well beyond (Subscript[r, ∞]) let's say that "hell breaks lose".  What happens then is that the numbers that come out are completely random.  Wonna see? Here are the first 5000 points at r=0.8

ListPlot[NestList[Logistic[3.8],0.5,5000],PlotRange->{0,1},Joined->False,Frame->True,PlotStyle->Blue]

Pretty amazing, eh?  Well what we have talked about, is the famous period-doubling-route to CHAOS, discovered by Feigenbaum in the late 1970s.  That's just 30 years ago...

Sensitivity to Initial Conditions

One important characteristic of a chaotic system is it's the sensitivity to initial conditions. If you start a sequence of the logistic map for small r, then the sequence will converge to the same fixed point independent of the initial condition. However, when r > 3.57, then the sequence changes dramatically depending upon the initial condition. As you will see, two chaotic trajectories that are initially infinitesimally close become exponentially separated as the sequence is iterated!

Let's examine two cases.

Small r

listA = NestList[Logistic[2.7], 0.5, 50];
listB = NestList[Logistic[2.7], 0.5+ 0.0001, 50];
Δ = listB - listA;

ListLogPlot[Abs[Δ],PlotStyle->{Red,PointSize[0.02]},GridLines->Automatic,Frame->True,PlotLabel->"Sequence Difference"]

Large r

listA = NestList[Logistic[3.7], 0.5, 50];
listB = NestList[Logistic[3.7], 0.5+ 0.0001, 50];
Δ = listB - listA;

ListLogPlot[Abs[Δ],PlotRange->All,PlotStyle->{Red,PointSize[0.02]},GridLines->Automatic,Frame->True,PlotLabel->"Sequence Difference"]

Summary

The Logistic Map illustrates deterministic chaos when the single control parameter, r, exceeds a critical value (approximately 3.57.) For small values of r, the trajectory converges to a single value independent of the initial condition. As r increases, the trajectory follows a limit cycle of increasing complexity until chaotic behavior results at a critical control parameter.

A nice summary plot of the limiting behavior of the Logistic Map is shown below.

logisticSummary = Table[Transpose[{Table[r, {201}],Drop[NestList[Logistic[r],0.5,500],300]}], {r, 1, 4, 0.001}] // Flatten[#,1]&;

Dimensions[logisticSummary]

ListPlot[logisticSummary,Frame->True, PlotStyle -> PointSize[Tiny]]

Show[%,PlotRange->{{2.8,3.8},All}]

Show[%%,PlotRange->{{3.3,3.7},{0.25,0.6}}]

Show[%%%,PlotRange->{{3.5,3.6},{0.45,0.58}}]