# Devaney’s Definition Of Chaos

This post discusses discrete dynamical systems and explores chaos with a mix of formal math and informal observations.

I am currently working as a teaching assistant for an undergraduate course
at NYU on chaos and dynamical systems.
Sinan Gunturk (the course instructor)
decided on this textbook,
which begins with discrete maps and moves on to continuous dynamical
systems later on. Maps can display all kinds of interesting behavior,
even for autonomous systems in 1D. So for a course where *chaos* is the first
word in the title, it is a logical choice.

I am not ashamed to admit that my background in pure mathematics is weak compared with my other peers at Courant. For the work I do, I am not required to apply very much mathematical rigor. However, this course has given me a much-needed opportunity to brush up on concepts in real analysis.

- Defining chaos
- Periodic points dense in X
- Topological Transitivity
- Sensitivity to initial conditions

### Defining chaos

In particular, my students recently learned about *Devaney’s definition of
chaos*, which according to this paper,
can be stated in the following way:

Let be a metric space. A continuous map is said to be chaotic on if

- f is transitive
- the periodic points of f are dense in X
- f has sensitive dependence on initial conditions

The last criterion is what I have always taken chaos to mean. When Ed Lorenz was trying to make accurate weather predictions in the 1960’s, he discovered that small changes in the initial conditions resulted in a wild divergence from the expected results. However, it turns out that the first two criteria imply the third, and this is stated as a theorem in the same paper and later proved. Thus, one could also say that the first two criteria define chaos, and that chaos implies a sensitive dependence on initial conditions.

In class, one of our current goals is to prove that the logistic map, written below, exhibits chaotic solutions for the value :

\(x_{n+1} = L(x_n) = a x_n ( 1 - x_n ) \)

This is achieved by establishing a relationship between this map and the simpler doubling map (also known as the dyadic map), which is

\(D(x_n) = 2 x \text{ (mod 1)} \)

Both of these functions are defined on , and in class this is the primary interval we have dealt with. Of course, Devaney’s definition can apply to any proper metric space. But limiting ourselves to small subset of the real line makes life considerably easier.

### Periodic points dense in X

The doubling map has a neat property: if one writes a number in its binary representation, it is equivalent to chopping off the left-most bit. From here one can derive the property that all rational numbers are eventually periodic under this map, as they will either have a terminating or repeating representation.

Thus, the periodic points of this map are dense in because rational numbers are dense in the reals. In other words, for every two real numbers and , I can find a rational number that falls between them, no matter how close and are.

#### Logistic map as a transformation of the doubling map

The relationship between the two maps (logistic and doubling) can be
found as follows. First, we introduce a **third** map called the *tent map*
with parameter :

\(T(x_n) = \mu \min(x,1-x) = 2 \min(x,1-x) \)

also defined on .

Second we say that two maps are *topologically conjugate* if there exists
a bijective function for two maps and such that:

\( h \circ j = k \circ h \)

If is surjective but not bijective, then the two maps are *semiconjugate*.

The logistic map and tent maps are conjugate via the function , which is bijective on :

\( L \circ C = C \circ T \)

And the tent map and doubling map are semiconjugate via the tent map itself:

\( T \circ T = T \circ D \)

Combining these results, one can derive the solution for iterations of the logistic map in terms of the logistic function, the conjugate function, and iterate number of the doubling map (which we can compute simply):

\( L^n = L \circ C \circ D^{n-1} \circ C^{-1} \)

Lastly, the density of periodic points is preserved under conjugacy and semiconjugacy (which we have not proven explicitly). Because the logistic map is conjugate to the tent map, which is semiconjugate to the doubling map, then the periodic points of the logistic map are dense in .

### Topological Transitivity

The definition of *topological transitivity* is as follows:

Let be a metric space with the metric and be continuous. The dynamical system is called topologically transitive if it satisfies the following condition:

For every pair of non-empty open sets and in , there is a non-negative integer such that .

This essentially means that for an open interval of initial conditions, with enough iterations
I will overlap with some other subinterval . In the case of the real line,
**transitivity is equivalent to the existence of a dense orbit**.

According to Scholarpedia, topological transitivity implies the existence of a dense orbit if there are no isolated points in the set. That is, there is no point in the set such that for some , a ball of size around the point only contains that point. For the interval , of course there are no isolated points.

And the existence of a dense orbit implies topological transitivity if the metric space is separable (that is, it contains a countable dense subset). The rational numbers on form a countable dense subset of this interval, so this is true as well.

Thus, to show topological transitivity, we simply must show that there exists an initial condition such that the orbit is dense. Intuitively, for the doubling map, only an irrational initial condition can produce a dense orbit. One such initial condition is the set of binary numbers of all lengths strung together. For example, the binary numbers of length are , and the binary numbers of length are , so

\(x_0 = 0.\text{ }0\text{ }1\text{ }00\text{ }01\text{ }10\text{ }11\ldots \)

For any number , there exists an such that

\(\left\|D^n(x_0) - y\right\| < \epsilon \)

Thus, by extension, the logistic map is also topologically transitive by the relationship to the doubling map described in the previous section (conjugacy and semiconjugacy preserve topological transitivity, which we have not proven explicitly).

### Sensitivity to initial conditions

Now that we have shown that our map is chaotic, we can prove that this implies a sensitivity to initial conditions. What can we say about the trajectories of the two orbits under the map?

If for any , for all I can find an such that

\( \|f^n(x_0) - f^n(y_0)\| \geq d \)

then we say that has a sensitive dependence on initial conditions.

I have included a version of a proof provided in class by Prof. Gunturk.

#### Proof

Let , and , meaning belongs to the set of periodic points whose orbit is distinct from . Let be the distance between and the orbit of :

\( c := \min\limits_{i \geq 0} \|x-f^i(p)\| \)

Let . Pick any and let . The ball around of radius is disjoint from orbit of due to our choice of (and consequently ).

By the density of , there exists another periodic point . Let be the period of , and consider the set

\( V := \bigcap\limits_{k=0}^{n-1} f^{-k}(N_d(f^k(p))) \)

is open because it is the intersection of finitely many open sets, and it is nonempty because .

consists of all the points for which for . The key is that we want points that stay close to through one period of .

By the transitivity of , there exists such that for some . Then, as we continue to iterate, we will end up inside our ball of size centered around .

What this means is that for some that starts in the ball centered around , we will end up in the open subset that begins to stay close to for future iterations.

We want to find such that and . Then , so they will sufficiently far apart to say that the map is sensitive to initial conditions.

Formally, let equal the smallest integer greater than or equal to such that . Since the period of is , then . Since , this implies that

\(f^N(z) = f^{N-m} \circ f^m(z) \in N_d(p) \)

Because guarantees we’re still close to after iterations. Thus,

\(\left|f^N(z) -f^{N-m}(p) \right|< d \)

We are almost done. Let us write

\( f^N(z) -f^{N}(q) = (f^N(z) - f^{N-m}(p)) + (f^{N-m}(p) - x) + (x - q) \)

since . Applying inequalities,

\( \left|f^N(z) -f^{N}(q)\right| \geq \left|f^{N-m}(p) - x\right| - \left|f^N(z) - f^{N-m}(p)\right| - \left|x - q\right| \)

And the right hand side is greater than or equal to . Why?

- is greater than
- is the distance between two points that are in a ball of size
- is the distance between two points in a ball of size

Because and , the whole right hand side is greater than or equal to .

Hence, though and both originated in a ball of size , after iterations they achieved a separation of .

There is one final step. Using the triangle inequality,

\( \left| f^N(z) - f^N(x) \right| + \left| f^N(x) - f^N(q) \right| > \left|f^N(z) -f^{N}(q)\right| \geq 2d\)

So is our initial value. One term on the left hand side must be greater than or equal to . If the first term satisfies this requirement, then let . Otherwise, let . For the appropriate choice of ,

\(\left|f^N(x_0) - f^N(y_0) \right| \geq d \)

Thus, we have shown that chaos implies a sensitive dependence on initial conditions!

*Let me know
if I have made any mistakes throughout this blog post. Greatly appreciated!*

## Leave a Comment