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
In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...
)
:
:
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
Binary may refer to:
Science and technology Mathematics
* Binary number, a representation of numbers using only two digits (0 and 1)
* Binary function, a function that takes two arguments
* Binary operation, a mathematical operation that t ...
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
Chaos or CHAOS may refer to:
Arts, entertainment and media Fictional elements
* Chaos (''Kinnikuman'')
* Chaos (''Sailor Moon'')
* Chaos (''Sesame Park'')
* Chaos (''Warhammer'')
* Chaos, in ''Fabula Nova Crystallis Final Fantasy''
* Cha ...
. This map readily generalizes to several others. An important one is the
beta transformation
Beta (, ; uppercase , lowercase , or cursive Greek, cursive ; grc, βῆτα, bē̂ta or ell, βήτα, víta) is the second letter of the Greek alphabet. In the system of Greek numerals, it has a value of 2. In Modern Greek, it represents th ...
, 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
Alfréd Rényi (20 March 1921 – 1 February 1970) was a Hungarian mathematician known for his work in probability theory, though he also made contributions in combinatorics, graph theory, and number theory.
Life
Rényi was born in Budapest to ...
in 1957, and an invariant measure for it was given by
Alexander Gelfond
Alexander Osipovich Gelfond (russian: Алекса́ндр О́сипович Ге́льфонд; 24 October 1906 – 7 November 1968) was a Soviet mathematician. Gelfond's theorem, also known as the Gelfond-Schneider theorem is named after hi ...
in 1959 and again independently by
Bill Parry in 1960.
Relation to the Bernoulli process
The map can be obtained as a
homomorphism
In algebra, a homomorphism is a structure-preserving map between two algebraic structures of the same type (such as two groups, two rings, or two vector spaces). The word ''homomorphism'' comes from the Ancient Greek language: () meaning "same" ...
on the
Bernoulli process
In probability and statistics, a Bernoulli process (named after Jacob Bernoulli) is a finite or infinite sequence of binary random variables, so it is a discrete-time stochastic process that takes only two values, canonically 0 and 1. Th ...
. 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
In dynamical systems theory, the baker's map is a chaotic map from the unit square into itself. It is named after a kneading operation that bakers apply to dough: the dough is cut in half, and the two halves are stacked on one another, and comp ...
. 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 mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
in the
unit interval
In mathematics, the unit interval is the closed interval , that is, the set of all real numbers that are greater than or equal to 0 and less than or equal to 1. It is often denoted ' (capital letter ). In addition to its role in real analysis, ...
0 \le x \le 1. The shift
T induces a
homomorphism
In algebra, a homomorphism is a structure-preserving map between two algebraic structures of the same type (such as two groups, two rings, or two vector spaces). The word ''homomorphism'' comes from the Ancient Greek language: () meaning "same" ...
, 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
In dynamical systems theory, the baker's map is a chaotic map from the unit square into itself. It is named after a kneading operation that bakers apply to dough: the dough is cut in half, and the two halves are stacked on one another, and comp ...
.
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
In mathematics, the Cantor function is an example of a function that is continuous, but not absolutely continuous. It is a notorious counterexample in analysis, because it challenges naive intuitions about continuity, derivative, and measure. Th ...
, as conventionally defined. This is one reason why the set
\^\mathbb is sometimes called the
Cantor set
In mathematics, the Cantor set is a set of points lying on a single line segment that has a number of unintuitive properties. It was discovered in 1874 by Henry John Stephen Smith and introduced by German mathematician Georg Cantor in 1883.
Thr ...
.
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 = 0.1001101, but we only observe the truncated value 0.1001. Our prediction for ''x''
1 is 0.001. If we wait until the real-world process has generated the true ''x''
1 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 In mathematics, two functions are said to be topologically conjugate if there exists a homeomorphism that will conjugate the one into the other. Topological conjugacy, and related-but-distinct of flows, are important in the study of iterated fun ...
to the unit-height
tent map
A tent () is a shelter consisting of sheets of fabric or other material draped over, attached to a frame of poles or a supporting rope. While smaller tents may be free-standing or attached to the ground, large tents are usually anchored using g ...
. 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 logistic map is a polynomial mapping (equivalently, recurrence relation) of degree 2, often referred to as an archetypal example of how complex, chaotic behaviour can arise from very simple non-linear dynamical equations. The map was popular ...
.
The ''r'' = 4 case of the logistic map is
z_=4z_n(1-z_n); this is related to the
bit shift
In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic operati ...
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
In mathematics, a quadratic polynomial is a polynomial of degree two in one or more variables. A quadratic function is the polynomial function defined by a quadratic polynomial. Before 20th century, the distinction was unclear between a polynomia ...
. 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
Irrationality is cognition, thinking, talking, or acting without inclusion of rationality. It is more specifically described as an action or opinion given through inadequate use of reason, or through emotional distress or cognitive deficiency. T ...
(as
almost all
In mathematics, the term "almost all" means "all but a negligible amount". More precisely, if X is a set, "almost all elements of X" means "all elements of X but those in a negligible subset of X". The meaning of "negligible" depends on the math ...
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''
0 is
rational
Rationality is the quality of being guided by or based on reasons. In this regard, a person acts rationally if they have a good reason for what they do or a belief is rational if it is based on strong evidence. This quality can apply to an abi ...
the image of ''x''
0 contains a finite number of distinct values within
forward_orbit_of_''x''
0_is_eventually_periodic,_with_period_equal_to_the_period_of_the_
forward_orbit_of_''x''
0_is_eventually_periodic,_with_period_equal_to_the_period_of_the_Binary_numeral_system">binary
_
Binary_may_refer_to:
__Science_and_technology___Mathematics_
*_Binary_number,_a_representation_of_numbers_using_only_two_digits_(0_and_1)
*__Binary_function,_a_function_that_takes_two_arguments
*_Binary_operation,_a_mathematical_operation_that_t_...
_expansion_of_''x''
0.__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.html" "title="Binary_numeral_system.html" "title="orbit_(dynamics).html" ;"title=", 1) and the orbit (dynamics)">forward orbit of ''x''
0 is eventually periodic, with period equal to the period of the Binary numeral system">binary
Binary may refer to:
Science and technology Mathematics
* Binary number, a representation of numbers using only two digits (0 and 1)
* Binary function, a function that takes two arguments
* Binary operation, a mathematical operation that t ...
. 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:
:
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