Dyadic transformation

[[Image:Exampleergodicmap.svg|thumb|The map T : [0, 1) → [0, 1), ${\displaystyle x\mapsto 2x{\bmod {1}}}$ preserves the Lebesgue measure.]]

The map can be obtained as a homomorphism on the Bernoulli process. Let ${\displaystyle \Omega =\{H,T\}^{\mathbb {N} }}$ be the set of all semi-infinite strings of the letters ${\displaystyle H}$ and ${\displaystyle T}$. These can be understood to be the flips of a coin, coming up heads or tails. Equivalently, one can write ${\displaystyle \Omega =\{0,1\}^{\mathbb {N} }}$ 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 ${\displaystyle \{0,1\}^{\mathbb {Z} }}$ consisting of all doubly-infinite (double-ended) strings; this will lead to the Baker's map. The qualification "semi-" is dropped below.

This space has a natural shift operation, given by

${\displaystyle T(b_{0},b_{1},b_{2},\dots )=(b_{1},b_{2},\dots )}$

where ${\displaystyle (b_{0},b_{1},\dots )}$ is an infinite string of binary digits. Given such a string, write

${\displaystyle x=\sum _{n=0}^{\infty }{\frac {b_{n}}{2^{n+1}}}.}$

The resulting ${\displaystyle x}$ is a real number in the unit interval ${\displaystyle 0\leq x\leq 1.}$ The shift ${\displaystyle T}$ induces a homomorphism, also called ${\displaystyle T}$, on the unit interval. Since ${\displaystyle T(b_{0},b_{1},b_{2},\dots )=(b_{1},b_{2},\dots ),}$ one can easily see that ${\displaystyle T(x)=2x{\bmod {1}}.}$ For the doubly-infinite sequence of bits ${\displaystyle \Omega =2^{\mathbb {Z} },}$ the induced homomorphism is the Baker's map.

The dyadic sequence is then just the sequence

${\displaystyle (x,T(x),T^{2}(x),T^{3}(x),\dots )}$

That is, ${\displaystyle x_{n}=T^{n}(x).}$

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

The dyadic transformation is topologically semi-conjugate to the unit-height tent map. Recall that the unit-height tent map is given by

${\displaystyle x_{n+1}=f_{1}(x_{n})={\begin{cases}x_{n}&\mathrm {for} ~~x_{n}\leq 1/2\\1-x_{n}&\mathrm {for} ~~x_{n}\geq 1/2\end{cases}}}$

The conjugacy is explicitly given by

${\displaystyle S(x)=\sin \pi x}$

so that

${\displaystyle f_{1}=S^{-1}\circ T\circ S}$

That is, ${\displaystyle f_{1}(x)=S^{-1}(T(S(x))).}$ This is stable under iteration, as

${\displaystyle f_{1}^{n}=f_{1}\circ \cdots \circ f_{1}=S^{-1}\circ T\circ S\circ S^{-1}\circ \cdots \circ T\circ S=S^{-1}\circ T^{n}\circ S}$

It is also conjugate to the chaotic r = 4 case of the logistic map. The r = 4 case of the logistic map is ${\displaystyle z_{n+1}=4z_{n}(1-z_{n})}$; this is related to the bit shift map in variable x by

${\displaystyle 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. Here, the map doubles angles measured in turns. That is, the map is given by

${\displaystyle \theta \mapsto 2\theta {\bmod {2}}\pi .}$

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 x₀ is rational the image of x₀ contains a finite number of distinct values within [0, 1) and the 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 (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:

${\displaystyle {\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 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.

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 ${\displaystyle \rho$ :[0,1]\to \mathbb {R} } as this density, so that ${\displaystyle x\mapsto \rho (x)}$. To obtain the action of ${\displaystyle T}$ on this density, one needs to find all points ${\displaystyle y=T^{-1}(x)}$ and write[7]

${\displaystyle \rho (x)\mapsto \sum _{y=T^{-1}(x)}{\frac {\rho (y)}{|T^{\prime }(y)|}}}$

The denominator in the above is the Jacobian determinant of the transformation, here it is just the derivative of ${\displaystyle T}$ and so ${\displaystyle T^{\prime }(y)=2}$. Also, there are obviously only two points in the preimage of ${\displaystyle T^{-1}(x)}$, these are ${\displaystyle y=x/2}$ and ${\displaystyle y=(x+1)/2.}$ Putting it all together, one gets

${\displaystyle \rho (x)\mapsto {\frac {1}{2}}\rho \!\left({\frac {x}{2}}\right)+{\frac {1}{2}}\rho \!\left({\frac {x+1}{2}}\right)}$

By convention, such maps are denoted by ${\displaystyle {\mathcal {L}}}$ so that in this case, write

${\displaystyle \left[{\mathcal {L}}_{T}\rho \right](x)={\frac {1}{2}}\rho \!\left({\frac {x}{2}}\right)+{\frac {1}{2}}\rho \!\left({\frac {x+1}{2}}\right)}$

The map ${\displaystyle {\mathcal {L}}_{T}}$ is a linear operator, as one easily sees that ${\displaystyle {\mathcal {L}}_{T}(f+g)={\mathcal {L}}_{T}(f)+{\mathcal {L}}_{T}(g)}$ and ${\displaystyle {\mathcal {L}}_{T}(af)=a{\mathcal {L}}_{T}(f)}$ for all functions ${\displaystyle f,g}$ on the unit interval, and all constants ${\displaystyle a}$.

Viewed as a linear operator, the most obvious and pressing question is: what is its spectrum? One eigenvalue is obvious: if ${\displaystyle \rho (x)=1}$ for all ${\displaystyle x}$ then one obviously has ${\displaystyle {\mathcal {L}}_{T}\rho =\rho }$ so the uniform density is invariant under the transformation. This is in fact the largest eigenvalue of the operator ${\displaystyle {\mathcal {L}}_{T}}$, 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 ${\displaystyle {\mathcal {L}}_{T}}$ in greater detail, one must first limit oneself to a suitable space of functions (on the unit interval) 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.[7]

The Hamiltonian of the zero-field one-dimensional Ising model of ${\displaystyle 2N}$ spins with periodic boundary conditions can be written as

${\displaystyle H(\sigma )=g\sum _{i\in \mathbb {Z} _{2N}}\sigma _{i}\sigma _{i+1}.}$

Letting ${\displaystyle C}$ be a suitably chosen normalization constant and ${\displaystyle \beta }$ be the inverse temperature for the system, the partition function for this model is given by

${\displaystyle Z=\sum _{\{\sigma _{i}=\pm 1,\,i\in \mathbb {Z} _{2N}\}}\prod _{i\in \mathbb {Z} _{2N}}Ce^{-\beta g\sigma _{i}\sigma _{i+1}}.}$

We can implement the renormalization group by integrating out every other spin. In so doing, one finds that ${\displaystyle Z}$ can also be equated with the partition function for a smaller system with but ${\displaystyle N}$ spins,

${\displaystyle Z=\sum _{\{\sigma _{i}=\pm 1,\,i\in \mathbb {Z} _{N}\}}\prod _{i\in \mathbb {Z} _{N}}{\mathcal {R}}[C]e^{-{\mathcal {R}}[\beta g]\sigma _{i}\sigma _{i+1}},}$

provided we replace ${\displaystyle C}$ and ${\displaystyle \beta g}$ with renormalized values ${\displaystyle {\mathcal {R}}[C]}$ and ${\displaystyle {\mathcal {R}}[\beta g]}$ satisfying the equations

${\displaystyle {\mathcal {R}}[C]^{2}=4\cosh(2\beta g)C^{4},}$

${\displaystyle e^{-2{\mathcal {R}}[\beta g]}=\cosh(2\beta g).}$

Suppose now that we allow ${\displaystyle \beta g}$ to be complex and that ${\displaystyle \operatorname {Im} [2\beta g]={\frac {\pi }{2}}+\pi n}$ for some ${\displaystyle n\in \mathbb {Z} }$. In that case we can introduce a parameter ${\displaystyle t\in [0,1)}$ related to ${\displaystyle \beta g}$ via the equation

${\displaystyle e^{-2\beta g}=i\tan {\big (}\pi (t-{\frac {1}{2}}){\big )},}$

and the resulting renormalization group transformation for ${\displaystyle t}$ will be precisely the dyadic map:[9]

${\displaystyle {\mathcal {R}}[t]=2t{\bmod {1}}.}$

• Bernoulli process
• Bernoulli scheme
• Gilbert–Shannon–Reeds model, a random distribution on permutations given by applying the doubling map to a set of n uniformly random points on the unit interval