Devaney’s Definition Of Chaos

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
  • Logistic map as a transformation of the doubling map
• Topological Transitivity
• Sensitivity to initial conditions
  • Proof

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 \(X\) be a metric space. A continuous map \(f: X \to X\) is said to be chaotic on \(X\) if

1. f is transitive
2. the periodic points of f are dense in X
3. 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 \(a=4\):

$$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 \([0,1]\), 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 \(x \in [0,1]\) 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 \([0,1]\) because rational numbers are dense in the reals. In other words, for every two real numbers \(a\) and \(b\), I can find a rational number that falls between them, no matter how close \(a\) and \(b\) 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 \(\mu=2\):

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

also defined on \([0,1]\).

Second we say that two maps are topologically conjugate if there exists a bijective function \(h\) for two maps \(j\) and \(k\) such that:

$$ h \circ j = k \circ h $$

If \(h\) is surjective but not bijective, then the two maps are semiconjugate.

The logistic map and tent maps are conjugate via the function \(C=\sin^2\left(\frac{\pi x}{2}\right)\), which is bijective on \([0,1]\):

$$ 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 \(n\) iterations of the logistic map in terms of the logistic function, the conjugate function, and iterate number \(n-1\) 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 \([0,1]\).

Topological Transitivity

The definition of topological transitivity is as follows:

Let \(X\) be a metric space with the metric \(d\) and \(f: X \to X\) be continuous. The dynamical system \((X,f)\) is called topologically transitive if it satisfies the following condition:

For every pair of non-empty open sets \(U\) and \(V\) in \(X\), there is a non-negative integer \(n\) such that \(f^n(U) \cap V \neq \emptyset\).

This essentially means that for an open interval of initial conditions, with enough iterations I will overlap with some other subinterval \(V\). 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 \(\epsilon > 0 \), a ball of size \(\epsilon\) around the point only contains that point. For the interval \([0,1]\), 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 \([0,1]\) 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 \(x_0\) 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 \(1\) are \({0,1}\), and the binary numbers of length \(2\) are \({00,01,10,11}\), so

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

For any number \(y \in [0,1]\), there exists an \((n \in \mathbb{N},\epsilon \in \mathbb{R}) > 0\) 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 \(x_0,y_0 \in X\), for all \(d \geq 0\) I can find an \(n > 0\) such that

$$ |f^n(x_0) – f^n(y_0)| \geq d $$

then we say that \(f\) has a sensitive dependence on initial conditions.

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

Proof

Let \(x \in X\), \(f: X \to X\) and \(p \in Per(f) \subset Y\), meaning \(p\) belongs to the set of periodic points whose orbit is distinct from \(x\). Let \(c\) be the distance between \(x\) and the orbit of \(p\):

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

Let \(d:= \frac{c}{4}\). Pick any \(\epsilon > 0\) and let \(\epsilon’ = \min(d,\epsilon)\). The ball around \(x\) of radius \(\epsilon’\) is disjoint from orbit of \(p\) due to our choice of \(d\) (and consequently \(\epsilon’\)).

By the density of \(Per(f)\), there exists another periodic point \(q \in N_{\epsilon’}(x) \subset N_{\epsilon}(x)\). Let \(n\) be the period of \(q\), and consider the set

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

\(V\) is open because it is the intersection of finitely many open sets, and it is nonempty because \(p \in V\).

\(V\) consists of all the points for which \(\left| f^k(v) – f^k(p) \right| < d\) for \(k=0,\ldots,n-1\). The key is that we want points that stay close to \(p\) through one period of \(q\).

By the transitivity of \(f\), there exists \(z \in N_{\epsilon’}(x) \subset N_{\epsilon}(x)\) such that \(f^m(z) \in V\) for some \(m\). Then, as we continue to iterate, we will end up inside our ball of size \(d\) centered around \(p\).

What this means is that for some \(z\) that starts in the ball centered around \(x\), we will end up in the open subset \(V\) that begins to stay close to \(p\) for future iterations.

We want to find \(N\) such that \(f^N(z) \in N_{d}(p)\) and \(f^N(q) = q\). Then \(f^N(q) \in N_{d}(x)\), so they will sufficiently far apart to say that the map is sensitive to initial conditions.

Formally, let \(N\) equal the smallest integer greater than or equal to \(m\) such that \(f^N(q) = q\). Since the period of \(q\) is \(n\), then \(N-m \leq n-1\). Since \(f^m(z) \in V\), this implies that

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

Because \(V\) guarantees we’re still close to \(p\) after \(n-1\) 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 \(f^N(q) = q\). 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 \(c-d-\epsilon’\). Why?

• \(\left\|f^{N-m}(p) – x\right\|\) is greater than \(c := \min\limits_{i \geq 0} \left\|f^i(p) – x\right\|\)
• \(\left\|f^N(z) – f^{N-m}(p)\right\|\) is the distance between two points that are in a ball of size \(d\)
• \(\left\|x – q\right\|\) is the distance between two points in a ball of size \(\epsilon’\)

Because \(\epsilon’\leq d\) and \(c = 4d\), the whole right hand side is greater than or equal to \(2d\). Hence, though \(z\) and \(q\) both originated in a ball of size \(\epsilon’\), after \(N\) iterations they achieved a separation of \(2d\). 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 \(x_0=x\) is our initial value. One term on the left hand side must be greater than or equal to \(d\). If the first term satisfies this requirement, then let \(y_0=z\). Otherwise, let \(y_0=q\). For the appropriate choice of \(y_0\),

$$\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!