Chaotic 1D maps

Surprisingly, a very simple map yieldes rather good model of chaotic systems.

Sawtooth map and Bernoulli shifts

Sawtooth The sawtooth map is determined as
    xn+1 = 2xn (mod 1)
where x (mod 1) is the fractional part of x. In the binary number system xn+1 is the left shift of xn
    x0 = 0.01011 ...
    x1 = 0.1011 ...
    x2 = 0.011 ...
and so on... The sequence (x0, x1 ...) is called the orbit of a point x0.

Symbolic dynamics and chaos

If the first digit in xn after binary point is 0 (1) then x lies in the Left (Right) half-interval of [0,1]. Thus for the map any orbit is determined by its symbolic LR sequence. For a random LR sequence points of corresponding orbit will visit the left or right half-interval randomly. Existence of continuum of complex orbits is a sign of chaos.
Sawtooth For the continuous tent map (to the left) for any xn one can always find preceding xn-1 value lying in the left or in the right half-interval. Thus in this case too it is possible to make orbit for any symbolic LR sequence by reverse iterations.
Sawtooth In general case not all symbolic sequences are allowed. E.g. RR subsequence is deprecated for the map to the left.

Unstable orbits and Lyapunov exponent

If xo and yo have k equal first binary digits then for the sawtooth map while n < k
    yn - xn =2n (yo - xo) = (yo - xo) en ln 2.
where λ=ln 2 is the Lyapunov exponent for the map. Thus the distance between two close orbits diverges exponentially with increasing n. It becomes about 1 after k iterations. This property is called sensitivity to initial conditions. It means too that all periodic orbits are unstable.

Unstable periodic orbits

For rational xo its binary fraction and orbit xn are periodic for the sawtooth map. Therefore there is infinite (countable) set of unstable periodic orbits and these orbits are dence in [0,1].

Stretching and folding

We may consider the sawtooth map to represent two steps: (1) a uniform stretching of the interval [0,1] to twice its original length, and (2) a left shift of its right half in original position. The stretching property leads to exponential separation of the nearby points and hence, sensitive dependence on initial conditions. The shift property keeps the generated sequence bounded, but also causes the map to be noninvertible, since it causes two different xn points to be mapped into one xn+1 point.

Shadowing

The exponential growth of errors iterating a chaotic dynamical system implies that a computer generated trajectory for some initial condition will rapidly diverge from the true orbit due to roundoff errors, so that after a relatively short time the computer generated orbit (called the pseudo-trajectory) will have no correlation with the true orbit.
However for given xn of the pseudo-trajectory we can imagine iterating backwards to find preimage of this point. Since the map is contracting under inverse iterations, the error decays for backwards orbits, and the trajectorry remains close to the backwards iteration of the true trajectory. Existence of a true trajectory that remains close to the pseudo-trajectory is called shadowing.

Invariant densities

In physical and computer experiments we can set initial conditions only approximately. But for any finite accurancy of the initial data chaotic dynamics is predictable only up to a finite number of steps! For such "turbulent" motions a statistical description may be of more use then actual knowledge of the true orbits. Therefore we have to trace evolution of the density of representative points.

For the sawtooth map after every iteration distance between close points increases two times, thus a smooth density spreads two times too. As since all points lay in the bounded [0,1] interval, therefore we get uniform distribution of the points in the n → ∞ limit. This density is left unchanged by the sawtooth map (it is called stationary or invariant density). Note that points of an unstable periodic orbit make singular invariant density.

Ergodicity

If we take random xo = 0.a1a2a3... then for any s = 0.b1b2b3...bk we can always find somewhere in xo coincident subsequence, i.e. xn will go close to s (probability of this "crossing" does not depend on s). Thus every random orbit will go arbitrary close to any point in [0,1] and cover this interval uniformly (a funny proof based on mysterious properties of randomness :)
One can use this fact to substitute "time" average <A> by "ensemble" average (ergodicity)
    <A> = ∑n A(xn) = ∫ A(x) dx.
In general case for a chaotic map
    <A> = ∑n A(xn) = ∫ A(x) dμ = ∫ A(x) ρ(x) dx ,
where μ is invariant measure and ρ(x) is invariant density for the map.

Decay of correlations

Average correlation function C(m) for a sequence xn is
    C(m) = limN→∞ 1/N Sn=1,N (xn - <x>)(xn+m - <x>) ,     <x> = limN→∞ 1/N ∑n xn .
If invariant measure for a map is known then
    C(m) = limN→∞ 1/N ∑n(xn - <x>)(f om(xn) - <x>) = ∫(x - <x>)(f om(x) - <x>) dμ
For the sawtooth map correlation function is
    C(m) = 2-m / 12 .
Thus mixing leads to exponential decay of correlations for large m.
Contents   Previous: Chaos in simple maps   Next: Chaotic quadratic maps
updated 15 June 2005