Dyadic transformation

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)

T:[0,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{for all }}n\geq 0,\ x_{n+1}=(2x_{n}){\bmod {1}}

.^[3]

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

T(x)={\begin{cases}2x&0\leq x<{\frac {1}{2}}\\2x-1&{\frac {1}{2}}\leq 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. 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.^[4]^[5]^[6]

^ Chaotic 1D maps, Evgeny Demidov
^ Wolf, A. "Quantifying Chaos with Lyapunov exponents," in Chaos, edited by A. V. Holden, Princeton University Press, 1986.
^ Dynamical Systems and Ergodic Theory – The Doubling Map Archived 2013-02-12 at the Wayback Machine, Corinna Ulcigrai, University of Bristol
^ A. Rényi, “Representations for real numbers and their ergodic properties”, Acta Math Acad Sci Hungary, 8, 1957, pp. 477–493.
^ A.O. Gel’fond, “A common property of number systems”, Izv Akad Nauk SSSR Ser Mat, 23, 1959, pp. 809–814.
^ W. Parry, “On the β -expansion of real numbers”, Acta Math Acad Sci Hungary, 11, 1960, pp. 401–416.

[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.

[3] Dynamical Systems and Ergodic Theory – The Doubling Map Archived 2013-02-12 at the Wayback Machine, Corinna Ulcigrai, University of Bristol

[4] A. Rényi, “Representations for real numbers and their ergodic properties”, Acta Math Acad Sci Hungary, 8, 1957, pp. 477–493.

[5] A.O. Gel’fond, “A common property of number systems”, Izv Akad Nauk SSSR Ser Mat, 23, 1959, pp. 809–814.

[6] W. Parry, “On the β -expansion of real numbers”, Acta Math Acad Sci Hungary, 11, 1960, pp. 401–416.

[1]

[2]

[3]

[4]

[5]

[6]