Proving a function is chaotic on an interval

Question

I'm self studying from the book 'First course in chaotic dynamical systems' and am having a hard time grasping how to prove that a function is chaotic.

For the function we have $T(x) = 2x$ for $x \leq \frac{1}{2}$ and $T(x) = 2 - 2x$ for $x > \frac{1}{2}$. I need to prove that it is chaotic on $[0, 1]$.

The book says the three conditions we need to prove are as follows:
1. Periodic points for $F$ are dense
2. $F$ is transitive
3. $F$ depends sensitively on initial conditions*

*The book notes that #3 follows from the first two.

Now I couldn't figure out a way to even tackle this problem via proof so I thought a visual aid would help. So I created the following graph. Each $x$ value is a seed and each $y$ value is a point on an orbit. 200 points on the orbit of each seed were computed.

I think the plot might show proof that $T$ is transitive since it's looking like we can always find an orbit that gets near two arbitrary points.

However, I don't see how we could have a set of periodic points dense in $[0, 1]$ since all we have are the (period 1) fixed points $0$ and $\frac{2}{3}$. Hence, all this allows me to say is that $T$ is chaotic for period 1, right?

My questions:
How do I go about proving that $T$ is chaotic?
What is going on in my plot? There seem to be some pretty interesting patterns/trends in there and I can't figure out what they mean.

Plot code:

import matplotlib.pyplot as plt

plt.axis([0, 1, 0, 1])
plt.xlabel('x0')
plt.ylabel('y')

x = 0
n = 1

while x <= 1:
    for i in range(0, 500):
        if x >= 0 and x <= 1:
           plt.plot([.005625*(n - 1)], [x], 'o', markersize = .0625, 
                     markerfacecolor = 'green', markeredgecolor = 'green')
        print 'x: ' + str(.005625*(n - 1)) + ' y: ' + str(x)
        if x <= .5:
            x = 2*x
        if x > .5:
            x = 2 - 2*x

    x = n*.005625
    n += 1

Note that .005625 is essentially arbitrary.

Answer 1

An encoding of $T$ uses the fact that every number $x$ in $[0,1]$ can be represented as $$x=\frac12-\frac12\sum_{n\geqslant1}\frac{s_n(x)}{2^n},\qquad s_n(x)=\pm1,$$ where the sequence $(s_n(x))$ is unique except for the dyadic numbers $x$ in $(0,1)$. Then, $$s_n(Tx)=s_1(x)s_{n+1}(x)\qquad (n\geqslant1),$$ hence, for every $k\geqslant1$, $$s_n(T^kx)=s_k(x)s_{n+k}(x)\qquad (n\geqslant1).$$ Several properties of $T$ are easily seen on this representation:

• The periodic points of period $1$ are such that $s_n(x)=(s_1(x))^n$ for every $n$, that is, $x=0$ or $x=\frac23$.
• The periodic points of period $2$ but not $1$ are such that $s_{n+2}(x)=s_2(x)s_{n}(x)$ for every $n$ but $s_2(x)\ne1$, that is, $x=\frac25$ or $x=\frac45$.
• There are exactly $2^k$ periodic points of period $k$.
• If the expansion $(s_n(x))$ is ultimately periodic in the sense that $s_k(x)=1$ and $s_{n+k}(x)=s_n(x)$ for some fixed $k$ and every $n$ large enough, then $x$ is ultimately periodic for $T$ in the sense that $T^{n+k}x=T^nx$ for every $n$ large enough.

To get a periodic point $z$ close to some $x$, fix some $k\geqslant1$ and define $(s_n(z))$ as follows:

• $s_n(z)=s_n(x)$ for every $1\leqslant n\leqslant k-1$
• $s_{n+k}(z)=s_k(z)s_n(z)$ for every $n\geqslant1$

The first condition ensures that $|x-z|\leqslant1/2^{k-1}$, the second condition that $T^{k}z=z$.

Answer 2

First, I applaud your choice to experiment. I have some comments on your code, though, and where to go from there. Your code is very slow since you have a matplotlib API call buried in a loop. I'd prefer to do something like so:

import numpy as np
import matplotlib.pyplot as plt

def f(x): 
    if 0 <= x <= 0.5:
        return 2*x
    else:
        return 2-2*x

step = 0.001
xs = []
ys = []
for x0 in np.arange(0,1+step,step):
    x=x0
    for i in range(50):
        xs.append(x0)
        x=f(x)
        ys.append(x)

plt.axis([0, 1, 0, 1])
plt.xlabel('x0')
plt.ylabel('y')
plt.plot(xs,ys,'o', markersize = 1,
         markerfacecolor = 'green', markeredgecolor = 'black')
plt.show()

Note that there is no point in iterating more than 53 times since, for $n>53$, $f^n(x)=0$ for any machine number $x$ (which has only 53 significant bits). You really need more precision to experiment with this function. Nonetheless, we can see some interesting curves, which turn out to be the iterates of $f$. Let's plot those together with the identity function.

import numpy as np
import matplotlib.pyplot as plt

def f(x): 
    if 0 <= x <= 0.5:
        return 2*x
    else:
        return 2-2*x

def ff(n,x):
    y=x
    for i in range(n):
        y=f(y)
    return y

step = 1.0/2.0**5
xs = np.arange(0,1+step,step)
ys = np.array([[ff(n,x) for x in xs] for n in range(1,5)]).transpose()
plt.plot(xs,ys)
plt.plot(xs,xs, color='black', linewidth=3)
plt.show()

The points of intersection of these colored lines with the thick black line are all periodic points. The picture suggests the following lemma, which should be easy to prove by induction: For every positive integer $k$ and integers $i\in\{0,1,2,\ldots,2^{k-1}\}$ and $j\in\{0,1,2,\ldots,2^{k-1}-1\}$, the iterate $f^k$ satisfies $$f^{k}\left(\frac{2i}{2^k}\right)=0 \: \text{ and } \: f^{k}\left(\frac{2j+1}{2^k}\right)=1.$$ From here, it should be easy to prove that $f$ is chaotic. For example, $f^k$ has a fixed point in $[2i/2^k,(2i+1)/2^k]$ by the intermediate value theorem. Also, the system is transitive since $$f^k\left(\left[\frac{2i}{2^k},\frac{2i+1}{2^k}\right]\right) = [0,1].$$