A limsup exercise: iterating the logistic map

Define the sequence {\{x_n\}} as follows: {x_1=1/3} and {x_{n+1} = 4x_n(1-x_n)} for {n=1,2,\dots}. What can we say about its behavior as {n\rightarrow\infty}?

The logistic map {f(x)=4x(1-x)} leaves the interval [0,1] invariant (as a set), so {0\le x_n\le 1} for all {n}. There are two fixed points: 0 and 3/4.

f2
Two fixed points of the logistic map: 0 and 3/4

Can {x_n} ever be 0? If {n} is the first index this happens, then {x_{n-1}} must be {1}. Working backwards, we find {x_{n-2}=1/2}, and {x_{n-3}\in \{1/2 \pm \sqrt{2}/4\}}. But this is impossible since all elements of the sequence are rational. Similarly, if {n} is the first index when {x_n = 3/4}, then {x_{n-1}=1/4} and {x_{n-2}\in \{1/2\pm \sqrt{3}/4\}}, a contradiction again. Thus, the sequence never stabilizes.

If {x_n} had a limit, it would have to be one of the two fixed points. But both are repelling: {f'(x) = 4 - 8x}, so {|f'(0)|=4>1 } and {|f'(3/4)| = 2 > 1}. This means that a small nonzero distance to a fixed point will increase under iteration. The only way to converge to a repelling fixed point is to hit it directly, but we already know this does not happen. So the sequence {\{x_n\}} does not converge.


But we can still consider its upper and lower limits. Let’s try to estimate {S = \limsup x_n} from below. Since {f(x)\ge x} for {x\in [0,3/4]}, the sequence {\{x_n\}} increases as long as {x_n\le 3/4}. Since we know it doesn’t have a limit, it must eventually break this pattern, and therefore exceed 3/4. Thus, {S\ge 3/4}.

This can be improved. The second iterate {f_2(x)=f(f(x))} satisfies {f_2(x)\ge x} for {x} between {3/4} and {a = (5+\sqrt{5})/8 \approx 0.9}. So, once {x_n>3/4} (which, by above, happens infinitely often), the subsequence {x_n, x_{n+2}, x_{n+4},\dots} increases until it reaches {a}. Hence {S\ge a}.

The bound {\limsup x_n\ge a} is best possible if the only information about {x_1} is that the sequence {x_n} does not converge. Indeed, {a} is a periodic point of {f}, with the corresponding iteration sequence {\{(5+ (-1)^n\sqrt{5})/8\}}.

Further improvement is possible if we recall that our sequence is rational and hence cannot hit {a} exactly. By doubling the number of iterations (so that the iterate also fixes {a} but also has positive derivative there) we arrive at the fourth iterate {f_4}. Then {f_4(x)\ge x} for {a\le x\le b}, where {b } is the next root of {f_4(x)-x} after {a}, approximately {0.925}. Hence {S\ge b}.

iterate
Stacking the iterates

This is a colorful illustration of the estimation process (made with Sage): we are covering the line {y=x} with the iterates of {f}, so that each subsequent one rises above the line the moment the previous one falls. This improves the lower bound on {S} from 0.75 to 0.9 to 0.92.

Although this process can be continued, the gains diminish so rapidly that it seems unlikely one can get to 1 in this way. In fact, one cannot because we are not using any properties of {x_1} other than “the sequence {x_n} is not periodic.” And it’s not true that {\limsup x_n = 1} for every non-periodic orbit of {f}. Let’s return to this later.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s