Dyadic transformation

The dyadic transformation is the mapping
produced by the rule
Equivalently, the dyadic transformation can also be defined as the iterated function map of the piecewise linear function
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. 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 Cantor set

Note that the sum
gives the Cantor function, as conventionally defined. This is one reason why the set 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 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 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
The conjugacy is explicitly given by
so that
That is, This is stable under iteration, as
It is also conjugate to the chaotic r = 4 case of the logistic map.
The r = 4 case of the logistic map is ; this is related to the bit shift map in variable x by
There is also a semi-conjugacy between the dyadic transformation and the quadratic polynomial. Here, the map doubles angles measured in turns. That is, the map is given by

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, 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 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 followed by a q-bit sequence 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:
which has reached a cycle of period 2. Within any subinterval of [0, 1), no matter how small, there are therefore [an infinite number">orbit (dynamics)">forward orbit of x₀ is eventually periodic, with period equal to the period of the 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 followed by a q-bit sequence 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:
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 chaotic maps.

Periodicity via bit shifts

The periodic and non-periodic orbits can be more easily understood not by working with the map directly, but rather with the bit shift map defined on the Cantor space.
That is, the homomorphism
is basically a statement that the Cantor set can be mapped into the reals. It is a surjection: every dyadic rational has not one, but two distinct representations in the Cantor set. For example,
This is just the binary-string version of the famous 0.999... = 1 problem. The doubled representations hold in general: for any given finite-length initial sequence of length, one has
The initial sequence corresponds to the non-periodic part of the orbit, after which iteration settles down to all zeros.
Expressed as bit strings, the periodic orbits of the map can be seen to the rationals. That is, after an initial "chaotic" sequence of, a periodic orbit settles down into a repeating string of length. It is not hard to see that such repeating sequences correspond to rational numbers. Writing
one then clearly has
Tacking on the initial non-repeating sequence, one clearly has a rational number. In fact, every rational number can be expressed in this way: an initial "random" sequence, followed by a cycling repeat. That is, the periodic orbits of the map are in one-to-one correspondence with the rationals.
This phenomenon is note-worthy, because something similar happens in many chaotic systems. For example, geodesics on compact manifolds can have periodic orbits that behave in this way.
Keep in mind, however, that the rationals are a set of measure zero in the reals. Almost all orbits are not periodic! The aperiodic orbits correspond to the irrational numbers. This property also holds true in a more general setting. An open question is to what degree the behavior of the periodic orbits constrain the behavior of the system as a whole. Phenomena such as Arnold diffusion suggest that the general answer is "not very much".

Density formulation

Instead of looking at the orbits of individual points under the action of the map, it is equally worthwhile to explore how the map affects densities on the unit interval. That is, imagine sprinkling some dust on the unit interval; it is denser in some places than in others. What happens to this density as one iterates?
Write as this density, so that. To obtain the action of on this density, one needs to find all points and write
The denominator in the above is the Jacobian determinant of the transformation, here it is just the derivative of and so. Also, there are obviously only two points in the preimage of, these are and Putting it all together, one gets
By convention, such maps are denoted by so that in this case, write
The map is a linear operator, as one easily sees that and for all functions on the unit interval, and all constants.
Viewed as a linear operator, the most obvious and pressing question is: what is its spectrum? One eigenvalue is obvious: if for all then one obviously has so the uniform density is invariant under the transformation. This is in fact the largest eigenvalue of the operator, it is the Frobenius–Perron eigenvalue. The uniform density is, in fact, nothing other than the invariant measure of the dyadic transformation.
To explore the spectrum of in greater detail, one must first limit oneself to a suitable space of functions to work with. This might be the space of Lebesgue measurable functions, or perhaps the space of square integrable functions, or perhaps even just polynomials. Working with any of these spaces is surprisingly difficult, although a spectrum can be obtained.

Borel space

A vast amount of simplification results if one instead works with the Cantor space, and functions Some caution is advised, as the map is defined on the unit interval of the real number line, assuming the natural topology on the reals. By contrast, the map is defined on the Cantor space, which by convention is given a very different topology, the product topology. There is a potential clash of topologies; some care must be taken. However, as presented above, there is a homomorphism from the Cantor set into the reals; fortunately, it maps open sets into open sets, and thus preserves notions of continuity.
To work with the Cantor set, one must provide a topology for it; by convention, this is the product topology. By adjoining set-complements, it can be extended to a Borel space, that is, a sigma algebra. The topology is that of cylinder sets. A cylinder set has the generic form
where the are arbitrary bit values, and the are a finite number of specific bit-values scattered in the infinite bit-string. These are the open sets of the topology. The canonical measure on this space is the Bernoulli measure for the fair coin-toss. If there is just one bit specified in the string of arbitrary positions, the measure is 1/2. If there are two bits specified, the measure is 1/4, and so on. One can get fancier: given a real number one can define a measure
if there are heads and tails in the sequence. The measure with is preferred, since it is preserved by the map
So, for example, maps to the interval and maps to the interval and both of these intervals have a measure of 1/2. Similarly, maps to the interval which still has the measure 1/2. That is, the embedding above preserves the measure.
An alternative is to write
which preserves the measure That is, it maps such that the measure on the unit interval is again the Lebesgue measure.