Search Results for “dyadic transformation”

Source: 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) is the mapping (i.e., recurrence relation)

T
:
[
0
,
1
)
→
[
0
,
1

)

∞

{\displaystyle T:[0,1)\to [0,1)^{\infty }}

x
↦
(

x

0

,

x

1

,

x

2

,
…
)

{\displaystyle x\mapsto (x_{0},x_{1},x_{2},\ldots )}

(where

[
0
,
1

)

∞

{\displaystyle [0,1)^{\infty }}

is the set of sequences from

[
0
,
1
)

{\displaystyle [0,1)}

) produced by the rule

x

0

=
x

{\displaystyle x_{0}=x}

for all

n
≥
0
,

x

n
+
1

=
(
2

x

n

)

mod

1

{\displaystyle {\text{for all }}n\geq 0,\ x_{n+1}=(2x_{n}){\bmod {1}}}

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

T
(
x
)
=

{

2
x

0
≤
x
<

1
2

2
x
−
1

1
2

≤
x
<
1.

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

β

(
x
)
=
β
x

mod

1

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

Relation to the Bernoulli process

dyadic

= The Cantor set

Rate of information loss and sensitive dependence on initial conditions

Relation to tent map and logistic map

Periodicity and non-periodicity

= Periodicity via bit shifts

dyadic

Density formulation

transformation

dyadic

transformation

= Borel space

one can define a measure

μ

p

(
∗
,
…
,
∗
,

b

k

,
∗
,
…
)
=

p

n

(
1
−
p

)

m

{\displaystyle \mu _{p}(*,\dots ,*,b_{k},*,\dots )=p^{n}(1-p)^{m}}

if there are

n

{\displaystyle n}

heads and

m

{\displaystyle m}

tails in the sequence. The measure with

p
=
1

/

2

{\displaystyle p=1/2}

is preferred, since it is preserved by the map

(

b

0

,

b

1

,

b

2

,
…
)
↦
x
=

∑

n
=
0

∞

b

n

2

n
+
1

.

{\displaystyle (b_{0},b_{1},b_{2},\dots )\mapsto x=\sum _{n=0}^{\infty }{\frac {b_{n}}{2^{n+1}}}.}

So, for example,

(
0
,
∗
,
⋯
)

{\displaystyle (0,*,\cdots )}

maps to the interval

[
0
,
1

/

2
]

{\displaystyle [0,1/2]}

and

(
1
,
∗
,
…
)

{\displaystyle (1,*,\dots )}

maps to the interval

[
1

/

2
,
1
]

{\displaystyle [1/2,1]}

and both of these intervals have a measure of 1/2. Similarly,

(
∗
,
0
,
∗
,
…
)

{\displaystyle (*,0,*,\dots )}

maps to the interval

[
0
,
1

/

4
]
∪
[
1

/

2
,
3

/

4
]

{\displaystyle [0,1/4]\cup [1/2,3/4]}

which still has the measure 1/2. That is, the embedding above preserves the measure.
An alternative is to write

(

b

0

,

b

1

,

b

2

,
…
)
↦
x
=

∑

n
=
0

∞

[

b

n

p

n
+
1

+
(
1
−

b

n

)
(
1
−
p

)

n
+
1

]

{\displaystyle (b_{0},b_{1},b_{2},\dots )\mapsto x=\sum _{n=0}^{\infty }\left[b_{n}p^{n+1}+(1-b_{n})(1-p)^{n+1}\right]}

which preserves the measure

μ

p

.

{\displaystyle \mu _{p}.}

That is, it maps such that the measure on the unit interval is again the Lebesgue measure.

= Frobenius–Perron operator

=
Denote the collection of all open sets on the Cantor set by

B

{\displaystyle {\mathcal {B}}}

and consider the set

F

{\displaystyle {\mathcal {F}}}

of all arbitrary functions

f
:

B

→

R

.

{\displaystyle f:{\mathcal {B}}\to \mathbb {R} .}

The shift

T

{\displaystyle T}

induces a pushforward

f
∘

T

−
1

{\displaystyle f\circ T^{-1}}

defined by

(

f
∘

T

−
1

)

(
x
)
=
f
(

T

−
1

(
x
)
)
.

{\displaystyle \left(f\circ T^{-1}\right)\!(x)=f(T^{-1}(x)).}

This is again some function

B

→

R

.

{\displaystyle {\mathcal {B}}\to \mathbb {R} .}

In this way, the map

T

{\displaystyle T}

induces another map

L

T

{\displaystyle {\mathcal {L}}_{T}}

on the space of all functions

B

→

R

.

{\displaystyle {\mathcal {B}}\to \mathbb {R} .}

That is, given some

f
:

B

→

R

{\displaystyle f:{\mathcal {B}}\to \mathbb {R} }

, one defines

L

T

f
=
f
∘

T

−
1

{\displaystyle {\mathcal {L}}_{T}f=f\circ T^{-1}}

This linear operator is called the transfer operator or the Ruelle–Frobenius–Perron operator. The largest eigenvalue is the Frobenius–Perron eigenvalue, and in this case, it is 1. The associated eigenvector is the invariant measure: in this case, it is the Bernoulli measure. Again,

L

T

(
ρ
)
=
ρ

{\displaystyle {\mathcal {L}}_{T}(\rho )=\rho }

when

ρ
(
x
)
=
1.

{\displaystyle \rho (x)=1.}

= Spectrum

=
To obtain the spectrum of

L

T

{\displaystyle {\mathcal {L}}_{T}}

, one must provide a suitable set of basis functions for the space

F

.

{\displaystyle {\mathcal {F}}.}

One such choice is to restrict

F

{\displaystyle {\mathcal {F}}}

to the set of all polynomials. In this case, the operator has a discrete spectrum, and the eigenfunctions are (curiously) the Bernoulli polynomials! (This coincidence of naming was presumably not known to Bernoulli.)
Indeed, one can easily verify that

L

T

B

n

=

2

−
n

B

n

{\displaystyle {\mathcal {L}}_{T}B_{n}=2^{-n}B_{n}}

where the

B

n

{\displaystyle B_{n}}

are the Bernoulli polynomials. This follows because the Bernoulli polynomials obey the identity

1
2

B

n

(

y
2

)

+

1
2

B

n

(

y
+
1

2

)

=

2

−
n

B

n

(
y
)

{\displaystyle {\frac {1}{2}}B_{n}\!\left({\frac {y}{2}}\right)+{\frac {1}{2}}B_{n}\!\left({\frac {y+1}{2}}\right)=2^{-n}B_{n}(y)}

Note that

B

0

(
x
)
=
1.

{\displaystyle B_{0}(x)=1.}

Another basis is provided by the Haar basis, and the functions spanning the space are the Haar wavelets. In this case, one finds a continuous spectrum, consisting of the unit disk on the complex plane. Given

z
∈

C

{\displaystyle z\in \mathbb {C} }

in the unit disk, so that

|

z

|

<
1

{\displaystyle |z|<1}

, the functions

ψ

z
,
k

(
x
)
=

∑

n
=
1

∞

z

n

exp
⁡
i
π
(
2
k
+
1
)

2

n

x

{\displaystyle \psi _{z,k}(x)=\sum _{n=1}^{\infty }z^{n}\exp i\pi (2k+1)2^{n}x}

obey

L

T

ψ

z
,
k

=
z

ψ

z
,
k

{\displaystyle {\mathcal {L}}_{T}\psi _{z,k}=z\psi _{z,k}}

for

k
∈

Z

.

{\displaystyle k\in \mathbb {Z} .}

This is a complete basis, in that every integer can be written in the form

(
2
k
+
1
)

2

n

.

{\displaystyle (2k+1)2^{n}.}

The Bernoulli polynomials are recovered by setting

k
=
0

{\displaystyle k=0}

and

z
=

1
2

,

1
4

,
…

{\displaystyle z={\frac {1}{2}},{\frac {1}{4}},\dots }

A complete basis can be given in other ways, as well; they may be written in terms of the Hurwitz zeta function. Another complete basis is provided by the Takagi function. This is a fractal, differentiable-nowhere function. The eigenfunctions are explicitly of the form

blanc

w
,
k

(
x
)
=

∑

n
=
0

∞

w

n

s
(
(
2
k
+
1
)

2

n

x
)

{\displaystyle {\mbox{blanc}}_{w,k}(x)=\sum _{n=0}^{\infty }w^{n}s((2k+1)2^{n}x)}

where

s
(
x
)

{\displaystyle s(x)}

is the triangle wave. One has, again,

L

T

blanc

w
,
k

=
w

blanc

w
,
k

.

{\displaystyle {\mathcal {L}}_{T}{\mbox{blanc}}_{w,k}=w\;{\mbox{blanc}}_{w,k}.}

All of these different bases can be expressed as linear combinations of one-another. In this sense, they are equivalent.
The fractal eigenfunctions show an explicit symmetry under the fractal groupoid of the modular group; this is developed in greater detail in the article on the Takagi function (the blancmange curve). Perhaps not a surprise; the Cantor set has exactly the same set of symmetries (as do the continued fractions.) This then leads elegantly into the theory of elliptic equations and modular forms.

Relation to the Ising model

The Hamiltonian of the zero-field one-dimensional Ising model of

2
N

{\displaystyle 2N}

spins with periodic boundary conditions can be written as

H
(
σ
)
=
g

∑

i
∈

Z

2
N

σ

i

σ

i
+
1

.

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

Letting

C

{\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

Z
=

∑

{

σ

i

=
±
1
,

i
∈

Z

2
N

}

∏

i
∈

Z

2
N

C

e

−
β
g

σ

i

σ

i
+
1

.

{\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

Z

{\displaystyle Z}

can also be equated with the partition function for a smaller system with but

N

{\displaystyle N}

spins,

Z
=

∑

{

σ

i

=
±
1
,

i
∈

Z

N

}

∏

i
∈

Z

N

R

[
C
]

e

−

R

[
β
g
]

σ

i

σ

i
+
1

,

{\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

C

{\displaystyle C}

and

β
g

{\displaystyle \beta g}

with renormalized values

R

[
C
]

{\displaystyle {\mathcal {R}}[C]}

and

R

[
β
g
]

{\displaystyle {\mathcal {R}}[\beta g]}

satisfying the equations

R

[
C

]

2

=
4
cosh
⁡
(
2
β
g
)

C

4

,

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

e

−
2

R

[
β
g
]

=
cosh
⁡
(
2
β
g
)
.

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

Suppose now that we allow

β
g

{\displaystyle \beta g}

to be complex and that

Im
⁡
[
2
β
g
]
=

π
2

+
π
n

{\displaystyle \operatorname {Im} [2\beta g]={\frac {\pi }{2}}+\pi n}

for some

n
∈

Z

{\displaystyle n\in \mathbb {Z} }

. In that case we can introduce a parameter

t
∈
[
0
,
1
)

{\displaystyle t\in [0,1)}

related to

β
g

{\displaystyle \beta g}

via the equation

e

−
2
β
g

=
i
tan
⁡

(

π
(
t
−

1
2

)

)

,

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

and the resulting renormalization group transformation for

t

{\displaystyle t}

will be precisely the dyadic map:

R

[
t
]
=
2
t

mod

1

.

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