Editing Dyadic transformation (section)

{{Short description|Doubling map on the unit interval}}
[[Image:Dyadic trans.gif|right|thumb|''xy'' plot where ''x''&nbsp;=&nbsp;''x''<sub>0</sub>&nbsp;∈&nbsp;[0,&thinsp;1] is [[Rational number|rational]] and ''y''&nbsp;=&nbsp;''x''<sub>''n''</sub> for all&nbsp;''n'']]
The '''dyadic transformation''' (also known as the '''dyadic map''', '''bit shift map''', '''2''x''&nbsp;mod&nbsp;1 map''', '''Bernoulli map''', '''doubling map''' or '''sawtooth map'''<ref>[http://www.ibiblio.org/e-notes/Chaos/saw.htm Chaotic 1D maps], Evgeny Demidov</ref><ref>Wolf, A. "Quantifying Chaos with Lyapunov exponents," in ''Chaos'', edited by A. V. Holden, Princeton University Press, 1986.</ref>) is the [[map (mathematics)|mapping]] (i.e., [[recurrence relation]])

: <math>T: [0, 1) \to [0, 1)^\infty</math>
: <math>x \mapsto (x_0, x_1, x_2, \ldots)</math>

(where <math>[0, 1)^\infty</math> is the set of [[sequence]]s from <math>[0, 1)</math>) produced by the rule

: <math>x_0 = x</math>
: <math>\text{for all } n \ge 0,\ x_{n+1} = (2 x_n) \bmod 1</math>.<ref>[http://www.maths.bristol.ac.uk/~maxcu/Doubling.pdf Dynamical Systems and Ergodic Theory – The Doubling Map] {{webarchive|url=https://web.archive.org/web/20130212163126/http://www.maths.bristol.ac.uk/~maxcu/Doubling.pdf |date=2013-02-12 }}, Corinna Ulcigrai, University of Bristol</ref>

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

: <math>T(x)=\begin{cases}2x & 0 \le x < \frac{1}{2} \\2x-1 & \frac{1}{2} \le x < 1. \end{cases}</math>

The name ''bit shift map'' arises because, if the value of an iterate is written in [[binary number|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 theory|chaos]]. This map readily generalizes to several others. An important one is the [[beta transformation]], defined as <math>T_\beta (x)=\beta x\bmod 1</math>. 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 (mathematician)|Bill Parry]] in 1960.<ref>
A. Rényi, “Representations for real numbers and their ergodic properties”, Acta Math Acad Sci Hungary, 8, 1957, pp. 477–493.
</ref><ref>
A.O. Gel’fond, “A common property of number systems”, Izv Akad Nauk SSSR Ser Mat, 23, 1959, pp. 809–814.
</ref><ref>
W. Parry, “On the β -expansion of real numbers”, Acta Math Acad Sci Hungary, 11, 1960, pp. 401–416.
</ref>