Bit Shift Map

The dyadic transformation (also known as the dyadic map, bit shift map, 2''x'' mod 1 map, Bernoulli map, doubling map or sawtooth map) is the mapping (i.e., recurrence relation)

: T: , 1) \to [0, 1)^\infty
: $x \mapsto (x_0, x_1, x_2, \ldots)$

(where $[0, 1)^\infty$ is the set of sequences from $[0, 1)$) produced by the rule

: $x_0 = x$
: $\text n \ge 0,\ x_ = (2 x_n) \bmod 1$.

Equivalently, the dyadic transformation can also be defined as the iterated function map of the piecewise linear function

: $T(x)=\begin2x & 0 \le x < \frac \\2x-1 & \frac \le x < 1. \end$

The name ''bit shift map'' arises because, if the value of an iterate is written in binary notation, the next iterate is obtained by shifting the binary point one bit to the right, and if the bit to the left of the new binary point is a "one", replacing it with a zero.

The dyadic transformation provides an example of how a simple 1-dimensional map can give rise to chaos. This map readily generalizes to several others. An important one is the beta transformation, defined as $T_\beta (x)=\beta x\bmod 1$. This map has been extensively studied by many authors. It was introduced by Alfréd Rényi in 1957, and an invariant measure for it was given by Alexander Gelfond in 1959 and again independently by Bill Parry in 1960.

Relation to the Bernoulli process

The map can be obtained as a homomorphism on the Bernoulli process. Let $\Omega = \^$ be the set of all semi-infinite strings of the letters $H$ and $T$. These can be understood to be the flips of a coin, coming up heads or tails. Equivalently, one can write $\Omega = \^$ the space of all (semi-)infinite strings of binary bits. The word "infinite" is qualified with "semi-", as one can also define a different space $\^$ consisting of all doubly-infinite (double-ended) strings; this will lead to the Baker's map. The qualification "semi-" is dropped below.

This space has a natural shift operation, given by
:$T(b_0, b_1, b_2, \dots) = (b_1, b_2, \dots)$
where $(b_0, b_1, \dots)$ is an infinite string of binary digits. Given such a string, write

:$x = \sum_^\infty \frac.$
The resulting $x$ is a real number in the unit interval $0 \le x \le 1.$ The shift $T$ induces a homomorphism, also called $T$, on the unit interval. Since $T(b_0, b_1, b_2, \dots) = (b_1, b_2, \dots),$ one can easily see that $T(x)=2x\bmod 1.$ For the doubly-infinite sequence of bits $\Omega = 2^,$ the induced homomorphism is the Baker's map.

The dyadic sequence is then just the sequence
:$(x, T(x), T^2(x), T^3(x), \dots)$
That is, $x_n = T^n(x).$

The Cantor set

Note that the sum
:$y=\sum_^\infty \frac$
gives the Cantor function, as conventionally defined. This is one reason why the set $\^\mathbb$ is sometimes called the Cantor set.

Rate of information loss and sensitive dependence on initial conditions

One hallmark of chaotic dynamics is the loss of information as simulation occurs. If we start with information on the first ''s'' bits of the initial iterate, then after ''m'' simulated iterations (''m'' < ''s'') we only have ''s'' − ''m'' bits of information remaining. Thus we lose information at the exponential rate of one bit per iteration. After ''s'' iterations, our simulation has reached the fixed point zero, regardless of the true iterate values; thus we have suffered a complete loss of information. This illustrates sensitive dependence on initial conditions—the mapping from the truncated initial condition has deviated exponentially from the mapping from the true initial condition. And since our simulation has reached a fixed point, for almost all initial conditions it will not describe the dynamics in the qualitatively correct way as chaotic.

Equivalent to the concept of information loss is the concept of information gain. In practice some real-world process may generate a sequence of values (''x''_''n'') over time, but we may only be able to observe these values in truncated form. Suppose for example that ''x''₀ = 0.1001101, but we only observe the truncated value 0.1001. Our prediction for ''x''₁ is 0.001. If we wait until the real-world process has generated the true ''x''₁ value 0.001101, we will be able to observe the truncated value 0.0011, which is more accurate than our predicted value 0.001. So we have received an information gain of one bit.

Relation to tent map and logistic map

The dyadic transformation is topologically semi-conjugate to the unit-height tent map. Recall that the unit-height tent map is given by

:$x_ = f_1(x_n) = \begin x_n & \mathrm~~ x_n \le 1/2 \\ 1-x_n & \mathrm~~ x_n \ge 1/2 \end$

The conjugacy is explicitly given by
:$S(x)=\sin \pi x$
so that

:$f_1 = S^ \circ T \circ S$

That is, $f_1(x) = S^(T(S(x))).$ This is stable under iteration, as
:$f_1^n = f_1\circ\cdots\circ f_1 = S^ \circ T \circ S \circ S^ \circ \cdots \circ T \circ S = S^ \circ T^n \circ S$

It is also conjugate to the chaotic ''r'' = 4 case of the logistic map.
The ''r'' = 4 case of the logistic map is $z_=4z_n(1-z_n)$; this is related to the bit shift map in variable ''x'' by

:$z_n =\sin^2 (2 \pi x_n).$

There is also a semi-conjugacy between the dyadic transformation (here named angle doubling map) and the quadratic polynomial. Here, the map doubles angles measured in turns. That is, the map is given by
:$\theta\mapsto 2\theta\bmod 2\pi.$

Periodicity and non-periodicity

Because of the simple nature of the dynamics when the iterates are viewed in binary notation, it is easy to categorize the dynamics based on the initial condition:

If the initial condition is irrational (as almost all points in the unit interval are), then the dynamics are non-periodic—this follows directly from the definition of an irrational number as one with a non-repeating binary expansion. This is the chaotic case.

If ''x''₀ is rational the image of ''x''₀ contains a finite number of distinct values within forward orbit of ''x''₀ is eventually periodic, with period equal to the period of the Binary numeral system">binary expansion of ''x''₀. Specifically, if the initial condition is a rational number with a finite binary expansion of ''k'' bits, then after ''k'' iterations the iterates reach the fixed point 0;
if the initial condition is a rational number with a ''k''-bit transient (''k'' ≥ 0) followed by a ''q''-bit sequence (''q'' > 1) that repeats itself infinitely, then after ''k'' iterations the iterates reach a cycle of length ''q''. Thus cycles of all lengths are possible.

For example, the forward orbit of 11/24 is:

: $\frac \mapsto \frac \mapsto \frac \mapsto \frac \mapsto \frac \mapsto \frac \mapsto \frac \mapsto \cdots,$

which has reached a cycle of period 2. Within any subinterval of [0, 1), no matter how small, there are therefore an infinite number of points whose orbits are eventually periodic, and an infinite number of points whose orbits are never periodic. This sensitive dependence on initial conditions is a characteristic of list of chaotic maps">chaotic maps