Chaotic 1D maps
Surprisingly, a very simple map yieldes rather good model of chaotic systems.
Sawtooth map and Bernoulli shifts

The sawtooth map is determined as
x_{n+1} = 2x_{n} (mod 1)
where x (mod 1) is the fractional part of x. In the binary
number system x_{n+1} is the left shift of x_{n}
x_{0} = 0.01011 ...
x_{1} = 0.1011 ...
x_{2} = 0.011 ...
and so on... The sequence (x_{0}, x_{1} ...)
is called the orbit of a point x_{0}.

Symbolic dynamics and chaos
If the first digit in x_{n} after binary point is 0
(1) then x lies in the Left (Right) halfinterval 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 halfinterval randomly. Existence of continuum of complex
orbits is a sign of chaos.

For the continuous tent map (to the left) for any x_{n}
one can always find preceding x_{n1} value lying in the
left or in the right halfinterval. Thus in this case too it is possible
to make orbit for any symbolic LR sequence by reverse iterations.


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 x_{o} and y_{o} have k equal
first binary digits then for the sawtooth map while n < k
y_{n}  x_{n} =2^{n}
(y_{o}  x_{o}) = (y_{o}  x_{o})
e^{n 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 x_{o} its binary fraction and orbit
x_{n} 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 x_{n} points to be mapped into
one x_{n+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
pseudotrajectory) will have no correlation with the true orbit.
However for given x_{n} of the pseudotrajectory 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 pseudotrajectory 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
x_{o} = 0.a_{1}a_{2}a_{3}...
then for any
s = 0.b_{1}b_{2}b_{3}...b_{k}
we can always find somewhere in x_{o} coincident subsequence,
i.e. x_{n} 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(x_{n}) = ∫ A(x) dx.
In general case for a chaotic map
<A> = ∑_{n} A(x_{n}) =
∫ 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 x_{n} is
C(m) = lim_{N→∞}
1/N S_{n=1,N}
(x_{n}  <x>)(x_{n+m}  <x>) ,
<x> = lim_{N→∞}
1/N ∑_{n} x_{n} .
If invariant measure for a map is known then
C(m) = lim_{N→∞}
1/N ∑_{n}(x_{n}  <x>)(f^{ om}(x_{n})
 <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