Dyadic transformation

Dyadic transformation
xy plot where x = x0 ∈ [0, 1] is rational and y = xn for all n.

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

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

produced by the rule

x0 = x
\forall n \ge 0, x_{n+1} = (2 \cdot x_n) \mod 1.

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

f(x)=\begin{cases}2x & 0 \le x < 0.5 \\2x-1 & 0.5 \le x < 1. \end{cases}

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.

Contents

Relation to tent map and logistic map

The dyadic transformation is topologically conjugate to :

The r=4 case of the logistic map is zn + 1 = 4zn(1 − zn); this is related to the bit shift map in variable x by

zn = sin2(2πxn).

There is semi-conjugacy between the dyadic transformation ( here named doubling map) and the quadratic polynomial.

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 x0 is rational the image of x0 contains a finite number of distinct values within [0, 1) and the forward orbit of x0 is eventually periodic, with period equal to the period of the binary expansion of x0. 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{11}{24} \mapsto \frac{11}{12} \mapsto \frac{5}{6} \mapsto \frac{2}{3} \mapsto \frac{1}{3} \mapsto \frac{2}{3} \mapsto \frac{1}{3} \mapsto \cdots,

which has reached a cycle of period 2. Within any sub-interval 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.

Solvability

The dyadic transformation is an exactly solvable model in the theory of deterministic chaos. The square-integrable eigenfunctions of the associated transfer operator of the Bernoulli map are the Bernoulli polynomials. These eigenfunctions form a discrete spectrum with eigenvalues 2 n for non-negative integers n. There are more general eigenvectors, which are not square-integrable, associated with a continuous spectrum. These are given by the Hurwitz zeta function; equivalently, linear combinations of the Hurwitz zeta give fractal, differentiable-nowhere eigenfunctions, including the Takagi function. The fractal eigenfunctions show a symmetry under the fractal groupoid of the modular group.

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 {xn} over time, but we may only be able to observe these values in truncated form. Suppose for example that x0 = .1001101, but we only observe the truncated value .1001 . Our prediction for x1 is .001 . If we wait until the real-world process has generated the true x1 value .001101, we will be able to observe the truncated value .0011, which is more accurate than our predicted value .001 . So we have received an information gain of one bit.

See also

References

  1. ^ Chaotic 1D maps, Evgeny Demidov
  2. ^ Wolf, A. "Quantifying Chaos with Lyapunov exponents," in Chaos, edited by A. V. Holden, Princeton University Press, 1986.

Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Dyadic — may refer to: Adicity of a mathematical relation or function (dyadic relations are usually called binary relations) Dyadic communication Dyadic counterpoint, the voice against voice conception of polyphony Dyadic fraction, a mathematical group… …   Wikipedia

  • Dyadic tensor — In multilinear algebra, a dyadic is a second rank tensor written in a special notation, formed by juxtaposing pairs of vectors, along with a notation for manipulating such expressions analogous to the rules for matrix algebra. Each component of a …   Wikipedia

  • List of mathematics articles (D) — NOTOC D D distribution D module D D Agostino s K squared test D Alembert Euler condition D Alembert operator D Alembert s formula D Alembert s paradox D Alembert s principle Dagger category Dagger compact category Dagger symmetric monoidal… …   Wikipedia

  • Complex squaring map — In mathematics, the complex squaring map, a polynomial mapping of degree two, is a simple and accessible demonstration of chaos in dynamical systems. It can be constructed by performing the following steps: Choose any complex number on the unit… …   Wikipedia

  • Dynamical system — This article is about the general aspects of dynamical systems. For technical details, see Dynamical system (definition). For the study, see Dynamical systems theory. Dynamical redirects here. For other uses, see Dynamics (disambiguation). The… …   Wikipedia

  • Recurrence relation — Difference equation redirects here. It is not to be confused with differential equation. In mathematics, a recurrence relation is an equation that recursively defines a sequence, once one or more initial terms are given: each further term of the… …   Wikipedia

  • Chaos theory — This article is about chaos theory in Mathematics. For other uses of Chaos theory, see Chaos Theory (disambiguation). For other uses of Chaos, see Chaos (disambiguation). A plot of the Lorenz attractor for values r = 28, σ = 10, b = 8/3 …   Wikipedia

  • Complex quadratic polynomial — A complex quadratic polynomial is a quadratic polynomial whose coefficients are complex numbers. Contents 1 Forms 2 Conjugation 2.1 Between forms 2.2 With doubling map …   Wikipedia

  • formal logic — the branch of logic concerned exclusively with the principles of deductive reasoning and with the form rather than the content of propositions. [1855 60] * * * Introduction       the abstract study of propositions, statements, or assertively used …   Universalium

  • Bounded mean oscillation — In harmonic analysis, a function of bounded mean oscillation, also known as a BMO function, is a real valued function whose mean oscillation is bounded (finite). The space of functions of bounded mean oscillation (BMO), is a function space that,… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”