Skip to main content

Section 2.9 The doubling map and chaos

A glance at the cobweb plots of \(f(x)=x^2-2\) and \(g(x)=4x(1-x)\) shows that they both exhibit very complicated behavior. In fact, they are chaotic in a perfectly quantitative sense. In this section, we'll introduce the doubling map, which is (in a sense) the prototypical chaotic map. After seeing why it's chaotic, we'll show that it's conjugate to \(f(x)=x^2-2\text{,}\) implying that it too is chaotic.

Subsection 2.9.1 The doubling map

Let \(H\) denote the half-open, half-closed unit interval:

\begin{equation*} H = [0,1) = \{x\in\mathbb R: 0\leq x < 1\}. \end{equation*}

The doubling map \(d\) is the function \(d:H\to H\) defined by

\begin{equation*} d(x) = 2x \bmod 1 = \begin{cases} 2x \amp 0 \leq x \leq 1/2 \\ 2x-1 \amp 1/2 \leq x \leq 1 \end{cases}. \end{equation*}

A graph of the doubling map together with a typical cobweb plot starting at an irrational number is shown in Figure 2.9.1

Figure 2.9.1. The doubling map

As it turns out, the doubling map is particularly easy to analyze if we consider its effect on the binary representation of a number. Suppose that \(x\in H\) has binary representation

\begin{equation*} x = 0_{\dot 2}b_1 b_2 b_3 b_4 b_5 \cdots, \end{equation*}

where each \(b_i\) is a zero or a one. (In computer parlance, the \(b_i\)s are called the bits of the number.)

Now, the effect of \(d\) on the binary representation of \(x\) is simple:

\begin{equation*} d(x) = 0_{\dot 2}b_2 b_3 b_4 b_5 \cdots. \end{equation*}

That is, the effect of \(d\) is to simply shift the bits of \(x\) to the left, discarding the bit that shifted into the ones place.

Of course, some numbers have multiple binary representations. For example,

\begin{equation*} 0_{\dot 2}1 = 0_{\dot 2}0\overline{1} = \frac{1}{2}, \end{equation*}

The doubling map, though, is defined independently of the binary representation of the number. Thus, we would expect that the shift operation, when applied to different representations of the same number, should lead to the same result. For example, the shift operation when applied to the two representations of \(1/2\) above yield.

\begin{equation*} 0_{\dot 2}\overline{0} = 0_{\dot 2}\overline{1} = 0 \mod 1. \end{equation*}

This characterization of the doubling map makes it very easy to find orbits with specific properties. Suppose, for example, we want an orbit of period 3. Simply pick (almost) any number of the form

\begin{equation*} x = 0_{\dot 2}\overline{b_1 b_2 b_3} \end{equation*}

The only caveat is that we can't have all \(b_i\)s the same for that would lead to either zero (which is fixed) or one (which is not in \(H\)). As a concrete example,

\begin{equation*} x = 0_{\dot 2}\overline{001} = \sum_{k=1}^{\infty}\frac{1}{8^k}=\frac{1}{7} \end{equation*}

has period 3. In fact, it's easy to verify that

\begin{equation*} \frac{1}{7} \to \frac{2}{7} \to \frac{4}{7} \to \frac{8}{7} = \frac{1}{7} \bmod 1 \end{equation*}

under the doubling map.

Another nice feature of this representation is that there is a simple correspondence between the binary expansion of a number and its position in the unit interval. Every number with a binary expansion starting with a zero lies in the left half of the unit interval, while every number starting with a one lies in the right half. The first two bits of a number specify in which quarter of the interval the number lies; the first three bits specify in which eighth of the unit interval the number lies, as shown in Figure 2.9.2

Figure 2.9.2. Dyadic intervals

More generally, given \(n\in\mathbb N\text{,}\) we can break the unit interval up into \(n\) pieces with length \(1/2^n\) and endpoints \(i/2^n\) for \(i=0,1,\ldots,2^n\text{.}\) These are called dyadic intervals and their endpoints (number of the form \(1/2^n\)) are called dyadic rationals. The first \(n\) bits of a number specify in which \(n^{\text{th}}\) level dyadic interval that number lies. In fact, the left hand endpoint of a dyadic interval has a terminating binary expansion which tells you exactly the first \(n\) bits of all the points in that interval.

Now, suppose that

\begin{equation*} x_1 = 0_{\dot 2}b_1 b_2 \cdots b_n b_{n+1} b_{n+2}'\cdots \: \text{ and } \: x_2 = 0_{\dot 2}b_1 b_2 \cdots b_n b_{n+1}' b_{n+2}'\cdots. \end{equation*}

Thus, the binary expansions of \(x_1\) and \(x_2\) agree up to at least the \(n^{\text{th}}\) spot but potentially disagree after that. Then, our geometric understanding of dyadic intervals allows us to easily see that,

\begin{equation*} |x_1-x_2|\leq\frac{1}{2^n}. \end{equation*}

Of course, there's also a simple algebraic proof of this fact, based on the fact that the bits cancel for \(k\leq n\)

\begin{align*} |x_1 - x_2| &= \left|\sum_{k=n+1}^{\infty}\frac{b_k-b_k'}{2^k}\right|\\ &\leq \sum_{k=n+1}^{\infty}\frac{|b_k-b_k'|}{2^k} \leq \sum_{k=n+1}^{\infty}\frac{1}{2^k} = \frac{1}{2^n}. \end{align*}

Subsection 2.9.2 Chaos

We can now prove three claims about the doubling map that, together, assert that the doubling map displays some of the essential features of chaos. First, we'll need to state and prove a lemma.

Computing the difference using the binary representations, taking into account that the terms disagree in the first spot and agree in the second, and finally applying the reverse triangle inequality, we get

\begin{align*} |x-y| &= \left|\sum_{i=1}^{\infty} \frac{b_i-b_i'}{2^n}\right| = \left|\pm\frac{1}{2} + \sum_{i=3}^{\infty} \frac{b_i-b_i'}{2^n}\right|\\ &\geq \left|\left|\pm\frac{1}{2}\right|-\left|\sum_{i=3}^{\infty} \frac{b_i-b_i'}{2^n}\right|\right| \geq \left|\frac{1}{2} - \frac{1}{4}\right| = \frac{1}{4}. \end{align*}

A geometric interpretation of this lemma is as follows. The fact that the two points disagree in the first spot means that they cannot lie in the same half of \(H\text{.}\) The fact that they do agree in the second spot means that they lie in the same quarter relative to their half, as shown in Figure 2.9.4. Clearly, any two such points cannot be within \(1/4\) of one another.

Figure 2.9.4. Possible positions of points in lemma Lemma 2.9.3

Choose \(n\in\mathbb N\) large enough so that \(1/2^n < \varepsilon\text{.}\) Now suppose that \(x\in H\) has binary expansion

\begin{equation*} x = 0_{\dot 2}b_1 b_2\cdots b_n b_{n+1} b_{n+2} \cdots. \end{equation*}

Define \(y\in H\) so that

\begin{equation*} y = 0_{\dot 2}b_1 b_2\cdots b_n (1-b_{n+1}) b_{n+2} \cdots. \end{equation*}

That is, the bits of \(y\) agree with those of \(x\) in the first \(n\) spots, disagree with \(x\) in the \((n+1)^{\text{st}}\) spot, and finally agree with \(x\) again in the \((n+2)^{\text{nd}}\) spot.

Then, the numbers \(d^n(x)\) and \(d^n(y)\) satisfy the hypotheses of lemma Lemma 2.9.3, thus \(|d^n(x)-d^n(y)| \geq 1/4\text{.}\)

Let \(x\in I\) and choose \(n\in\mathbb N\) large enough so that

\begin{equation*} (x,x+1/2^n)\subset I. \end{equation*}

Now suppose that

\begin{equation*} x = 0_{\dot 2}b_1 b_2\cdots b_n\cdots. \end{equation*}

Then,

\begin{equation*} \hat{x} = 0_{\dot 2}\overline{b_1 b_2\cdots b_n} \end{equation*}

is a periodic point in \(I\text{.}\)

We'll define \(x\) by specifying its binary expansion. We begin by writing down all possible finite binary strings:

\begin{equation*} 0,\,1, \:\: 00,\,01,\,10,\,11, \:\: 000,\,001,\,010,\,011,\,100,\,101,\,110,\,111,\ldots \end{equation*}

We then concatenate these to obtain the binary representation of \(x\)

\begin{equation*} x = 0_{\dot 2}0\,1\,00\,01\,10\,11\,000\,001\,010\,011\,100\,101\,110\,111\ldots \end{equation*}

Now, let \(I\subset H\) be an open interval. We claim that there is some iterate of \(x\) in \(I\text{.}\) To see that, let \(L\) denote the length of \(I\) and choose \(n\in\mathbb N\) large enough so that

\begin{equation*} \frac{1}{2^n} < \frac{1}{2}L. \end{equation*}

Let \(i\) be the smallest integer such that \(i/2^n \in I\text{.}\) Note that we must also have \((i+1)/2^n \in I\text{.}\) Thus, the dyadic interval \([i/2^n,(i+1)/2^n)\) is wholly contained in \(I\) and the first \(n\) bits of every point in that interval agree with \(i/2^n\text{.}\) So, let

\begin{equation*} \frac{i}{2^n} = 0_{\dot 2}b_1 b_2 \cdots b_n \end{equation*}

and note that, by construction, the string \(b_1 b_2 \cdots b_n\) appears somewhere in the binary expansion of \(x\text{.}\) Thus, we can apply the doubling function to the point \(x\) some number, say \(m\text{,}\) times to obtain

\begin{equation*} d^m(x) = 0_{\dot 2}b_1 b_2 \cdots b_n \cdots. \end{equation*}

The number \(d^m(x)\) is then an iterate of \(x\) that lies in \(I\text{.}\)

While there is no truly universally accepted definition of chaos, claims Claim 2.9.5, Claim 2.9.6, and Claim 2.9.7 are generally agreed to express some of the essential features of chaos. We might think of them as representing:

  • Instability,

  • Structure, and

  • Indecomposability

Subsection 2.9.3 A chaotic quadratic

Let \(f(x)=x^2-2\text{.}\) We now show that \(f\) is semi-conjugate to the doubling map \(d\) under the semi-conjugacy \(\varphi(x)=2\cos(2\pi x)\text{.}\) As a result, \(\varphi\) maps all the orbit types that \(d\) has to an orbit of \(f\) with similar properties. Thus, \(f\) is chaotic.

We must simply show that \(f\circ\varphi=\varphi\circ d\text{,}\) so let's compute. First,

\begin{equation*} f(\varphi(x)) = 2(2\cos(2\pi x))^2 - 2 = 4\cos^2(2\pi x)-2. \end{equation*}

Well, that was easy. The next part is a little trickier - we just need to apply a couple of trig identities and use the fact that we can drop the mods inside the squared trig functions due to the symmetries of those functions.

\begin{align*} \varphi(d(x)) &= 2\cos(2\pi(2x \bmod 1))\\ &= 2(\cos^2(\pi (2 x \bmod 1))-\sin^2(\pi (2 x \bmod 1)))\\ &= 2(\cos^2(2\pi x)-\sin^2(2\pi x))\\ &= 2(\cos^2(2\pi x)-(1-\cos^2(2\pi x)))\\ &= 2(2\cos^2(2\pi x)-1)\\ &= 4\cos^2(2\pi x)-2 \end{align*}

Again, the key fact about semi-conjugacy is that \(\varphi\) maps orbits of \(d\) to orbits of \(f\text{.}\) Thus, since \(d\) has a dense orbit \(f\) too has a dense orbit. Here's a concrete example illustrating this idea.

Find a point of period 11 for the chaotic quadratic \(f(x)=x^2-2\text{.}\)

Solution.

First, it's easy to find an orbit of period 11 for the doubling map. One example is

\begin{equation*} 0_{\dot 2}00000000001 = \sum_{k=1}^{\infty}\frac{1}{2^{11k}} = \frac{1}{2047}. \end{equation*}

The point behind conjugacy is that \(\varphi(1/2047) = 2\cos(2\pi/2047)\) will be a point of period 11 for \(f\text{.}\) The reader is advised to check this numerically!