University of Bologna University of Ferrara

Approccio Statistico all'Analisi di Sistemi Caotici e Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'InformazioneApplicazioni all'Ingegneria dell'Informazione

Gianluca Setti13 Riccardo Rovatti23

1Dip. di Ingegneria – Università di Ferrara2 Dip. di Elettronica, Informatica e Sistemistica - Università di Bologna

3 Centro di Ricerca sui Sistemi Elettronici per L’ingegneria dell’Informazione e delleTelecomunicazioni “Ercole de Castro” (ARCES) – Università di Bologna

Scuola di DottoratoIngegneria dell’Informazione

22-25 Settembre 2003

2

Programma

• Lunedì 22– Introduzione ai fenomeni caotici– Caratteristiche aleatorie della dinamica caotica– Caratteristiche dinamiche dei processi aleatori e visione operatoriale della

dinamica aleatoria

• Martedì 23– Approssimazioni a dimensione finita– Mappe di Markov affini a tratti– Una prima applicazione: riduzione dell'interferenza elettromagnetica– Quantizzazione e approccio tensoriale

• Mercoledì 24 (Riccardo Rovatti)– Esempi di approccio tensoriale– Una seconda applicazione: ottimizzazione delle sequenze di allargamento in

sistemi DS-CDMA

• Giovedì 25 (Riccardo Rovatti)– Quantizzazione numerabile e approccio tensoriale– Una terza applicazione: generazione di processi autosimili

3

Initiatives and Sources of Further Info

“Chaotic Electronics in Telecommunications”M.P. Kennedy, R. Rovatti, G. Setti, eds.CRC Press, Boca Raton, Florida, 2000

“Application of Nonlinear Dynamics to Electronic and Information Engineering”

M.Hasler, G. Mazzini, M. Ogorzalek, R. Rovatti, G. Setti, eds.

Numero speciale dei Proceedings of the IEEE, May 2002

G. Mazzini, R. Rovatti, G. SettiTutorial ISCAS 2001 (http://ieeexplore.ieee.org)Tutorial ISCAS 2003Tutorial Globecomm 2003

4

1. A. Lasota and M. C. Mackey, “Chaos, Fractals, and Noise” New York: Springer-Verlag, 1994.

2. M. P. Kennedy, R. Rovatti, G. Setti (Eds.), “Chaotic Electronics in Telecommnunications,” CRC Press, Boca Raton, June 2000

3. G. Keller, “On the rate of convergence to equilibrium in one-dimensional systems,” Commun. Math. Phys., vol. 96, pp. 181–193, 1984.

4. F. Hofbauer and G. Keller, “Ergodic properties of invariant measures for piecewise monotonic transformations,” Math. Zeitschrift, vol. 180, pp. 119–140, 1982.

5. V. Baladi and G. Keller, “Zeta functions and transfer operatorsfor piecewise monotone transformations,” Commun. Math. Phys., vol. 127, pp. 459–477, 1990.

6. V. Baladi and L.-S. Young, “On the spectra of randomly perturbed expanding maps,” Commun. Math. Phys., vol. 156, pp. 355–385, 1993.

7. V. Baladi, S. Isola, and B. Schmitt, “Transfer operator for piece-wise affine approximation of interval maps,” Ann. l’Inst. Henri

8. Poincaré—Physique Théorique, vol. 62, pp. 251–265, 1995.

9. N. Friedman and A. Boyarsky, “Irreducibility and primitivityusing Markov maps,” Linear Algebra Appl., vol. 37, pp. 103–117, 1981.

10. V. Baladi, “Infinite kneading matrices and weighted zeta functions of interval maps,” J. Function. Anal., vol. 128, pp. 226–244, 1995.

11. Gary Froyland “Extracting dynamical behaviour via Markov models” In Alistair Mees, editor, Nonlinear Dynamics and Statistics: Proceedings, Newton Institute, Cambridge, 1998, pages 283-324, Birkhauser, 2000

1. Michael Dellnitz, Gary Froyland, Stefan Sertl, “On the isolatedspectrum of the Perron-Frobenius operator,” Nonlinearity, 13(4):1171-1188, 2000

2. M Goetz, W. Scfwarz, “Statistical analysis of chaotic Markov systems with quantised output” Proceedings. ISCAS 2000 Geneva, 2000, pp. 229 -232 vol.5

3. M. Goetz, A. Abel, “Design of infinite chaotic polyphase sequences with perfect correlation properties” ISCAS '98. Proceedings, 1998,pp 279 -282 vol.3

4. T.Kohda, A.Tsuneda, “Statistics of Chaotic Binary Sequences”, IEEE Trans. Inf. Theory, vol. 43, pp. 104-112, 1997

5. T.Kohda, A.Tsuneda, “Explicit Evaluations of Correlation Functions of Chebyshev Binary and Bit Sequences Based on Perron-Frobenius Operator”, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E77-A, pp. 1794-1800, 1994

6. T. Kohda, H. Fujisaki, “Variances of multiple access interferencecode average against data average”vol 36 Issue: 20 , 28 Sept. 2000

7. G. Mazzini, G. Setti, R. Rovatti, “Chaotic Complex SpreadingSequences for Asynchronous DS-CDMA – Part I: System Modeling and Results,” IEEE Transactions on Circuits and Systems- Part I, vol. 44, n.10, pp.937-947, October 1997.

8. R. Rovatti, G. Setti, G. Mazzini “Chaotic Complex Spreading Sequences for Asynchronous DS-CDMA – Part II: Some Theoretical Performance Bounds” IEEE Transactions on Circuits and Systems- Part I, vol. 45, n. 4, pp. 496-506, April 1998.

Some bibliography - I

5

1. R. Rovatti, G. Setti, “On the distribution of synchronization times in coupled uniform piecewise-linear Markov maps,” IEICE Transactions on Fundamentals, vol. 81-A, n. 9, pp. 1769-1776, September 1998.

2. R. Rovatti, G. Setti, “Topological Conjugacy Propagates Stochastic Robustness of Chaotic Maps,” IEICE Transactions on Fundamentals, vol. 81-A, n. 9, pp. 1769-1776, September 1998.

3. G. Setti, R. Rovatti, G. Mazzini, “Synchronization Mechanism and Optimization of Spreading Sequences in Chaos-Based DS-CDMA Systems,” IEICE Transactions on Fundamentals, vol. 82, n. 9, September 1999.

4. G. Mazzini, R.Rovatti, G. Setti, “Interference Minimization by Auto-correlation Shaping in Asynchronous DS-CDMA Systems: Chaos-based Spreading is Nearly Optimal,” IEE Electronics Letters, vol. 35, n. 13, Jun. 24 1999, pp. 1054-1055.

5. R. Rovatti, G. Mazzini, G. Setti, “A Tensor Approach to higher-order Expectation of Quantized Chaotic Trajectories - Part I: General Theory and Specialization to Piecewise Affine MarkovSystems,” IEEE Transactions on Circuits and Systems- Part I, vol. 48, November 2000.

6. G. Mazzini, R. Rovatti, G. Setti, “A Tensor Approach to higher-order Expectation of Quantized Chaotic Trajectories - Part II: Application to Chaos-based DS-CDMA in MultipathEnvironments,” IEEE Transactions on Circuits and Systems- Part I, vol.48, November 2000.

7. R. Rovatti, G. Mazzini, G. Setti, “Enhanced Rake Receivers forChaos-Based DS-CDMA,” IEEE Transactions on Circuits and Systems- Part I, June 2001 .

8. R. Rovatti, G. Mazzini, G. Setti, “Shannon Capacities of Chaos-based and Conventional Asynchronous DS-CDMA over AWGN Channels,” IEE Electronics Letters, June 2002, pp.478-480

Some bibliography - II 1. G. Setti, G. Mazzini, R. Rovatti, S. Callegari, “Statistical

Modeling of Discrete-Time Chaotic Processes: Basic Finite Dimensional Tools and Applications”, IEEE Proceedings, May2002

2. R. Rovatti, G. Mazzini, G. Setti, A. Giovanardi, “Statistical Modeling of Discrete-Time Chaotic Processes: Andvanced Finite Dimensional Tools and Applications”, IEEE Proceedings, May2002

3. G. Mazzini, R. Rovatti, G. Setti, “Chaos-Based DS-CDMA: Measuring the Improvements”, IEEE Transactions on Circuitsand Systems – PartI, December 2001

4. R. Rovatti, G. Setti, S. Graffi “Chaos-Based FM of Clock Signals for EMI Reduction,” European Conference on Circuits Theory and Design (ECCTD’99), Stresa, August 1999.

5. G. Setti, M. Balestra, R. Rovatti, “Experimental verification of enhanced electromagnetic compatibility in chaotic fm clock signals”, in Proceedings of IEEE ISCAS’00, (Lausanne), 2000.

6. S. Callegari, R. Rovatti, G. Setti, “On the spectrum of signalsobtained by driving FM modulators with chaotic sequences”, in Proceedings of ECCTD2001, vol. II, (Helsinki), pp. 189–192, 2001.

7. S. Callegari, R. Rovatti, and G. Setti, “Chaos based improvement of EMI compliance in switching loudspeaker drivers”, in Proceedings of ECCTD2001, vol. III, (Helsinki), pp. 421–424, 2001.

8. S. Callegari, R. Rovatti, G. Setti, “Generation of Constant-Envelope Spread-Spectrum Signals via Chaos-Based FM: Theory and Simulation Results”, IEEE Transactions on Circuits and Systems- Part I, January 2003

6

Outline (Today)

• Introduction and methodology• A phenomenological introduction to chaos• Statistical approach to dynamical system theory:

• Studying chaos with densities

– “strange phenomena” in the densities evolutions

• The Perron-Frobenius operator: a method of “global linearization”– definition and properties– study of the “linearized” system

• ergodic maps and existence of a unique equilibrium point– Birkhoff ergodic theorem

• mixing maps and asymptotic stability– Bounded variation functions space

• exact maps

• The dynamical view of stochastic process

7

1 1max ( , , , )nnd d dP +…

Classical d.o.f. + some stochastic processperformance

What do we do and why should it work?

min max

1

, 1, ,s.t.

( , , ) 0 1, ,

j j j

k n

d d d j n

C d d k m

∈ = = =

…

… … constraints

degrees of freedom

1max ( , , )nP d d…min max

1

, 1, ,s.t.

( , , , ) 0 1, ,

1

?

j j j

k n

d d d j

C d d k m

n ∈ = = =

+…

… …

• when performance depends on the statisticalfeatures of some signal the system may have an“hidden” d.o.f.

• Hidden d.o.f. of this kind are often less constrained than other design parameters

8

Optimization by design of stochastic processes

performanceindex in termsof statisticalfeatures of signals

PerformanceOptimization

signals withtunable

statisticalfeatures

How do I characterize/generate them ?Is it possible by using chaos?

9

What is chaos?Definition (phenomenological): Aperiodic steady-state behavior that is not

• an equilibrium point• a periodic motion• a quasi-periodic motion

( )( ) ( ), ( )x t N x t u t=( )1 ,k k kx M x u+ =• Continuous-time: at least 3rd order system (2nd if non-autonomous)• Discrete-time: also 1-st order (with a non-invertible M)

∆kx

)(1 kk xMx =+MN∈k

[ ] [ ]: 0,1 0,1M X =

100.2 0.4 0.6 0.8 1

0.2

0.4

0.6

0.8

1

Possible steady-state behaviors - II

• Equilibrium points

)( ** xMx =

1 ( ) (1 )k k k kx M x px x+ = = −

95.1=p

10 20 30 40 50 60

0.2

0.3

0.4

1.00 =x

487.0,0 *1

*0 ≅= xx1)(' *

0 >xM

1)(' *1 <xM

11

Possible steady-state behaviors - II

• Periodic behavior (limit cycle)

,k lN kx x k l+ = ∈N4.3=p

7059.0,0 *1

*0 ≅= xx

10 20 30 40 50 60

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.2 0.4 0.6 0.8 1

0.2

0.4

0.6

0.8

1

1.00 =x 2=N

1)(' *0 >xM

1)(' *1 >xM

101010 ˆˆˆˆˆˆ xxxxxx

12

Possible steady-state behaviors - III

•Periodic behavior (limit cycle)

7175.0,0 *1

*0 ≅= xx

1.00 =x 4N =

10 20 30 40 50 60

0.4

0.6

0.8

0.2 0.4 0.6 0.8 1

0.2

0.4

0.6

0.8

1

Period n limit cycle ⇔Fixed point of the N-th iterate

54.3=p

1)(' *0 >xM

1)ˆ( 02 >xM

0 0 0ˆ ˆ ˆ ˆ( ( ( ))) ( )NN

N

x M M M x M x x= = =1)(' *

1 >xM

13

Possible steady-state behaviors - IV

•Chaos

4=p

4/3,0 *1

*0 == xx

1.00 =x

Limit cicles still exists butthey are unstable

10 20 30 40 50 60

0.2

0.4

0.6

0.8

1

0.2 0.4 0.6 0.8 1

0.2

0.4

0.6

0.8

1

1)(' *0 >xM

1)(' *1 >xM

14

Features of chaotic behavior - I

• “Complicated” time series ….

10 20 30 40 50 60

0.2

0.4

0.6

0.8

1

Chaos

20 40 60 80 100

-2

-1

1

2

Quasi-periodic behavior

( ) (2 ) (2 5 )sin sinx k k kπ π= +

Considering time series in not enough!

15

Features of chaotic behavior - II

•Power density spectrum

periodic

10 20 30 40 50 60

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.2 0.4 0.6 0.8 10

0.5

1

1.5

2

2.5

10 20 30 40 50 60

0.2

0.4

0.6

0.8

1

chaos 0 0.2 0.4 0.6 0.8 1

0.2

0.4

0.6

0.8

1

1.2

20 40 60 80 100

-2

-1

1

2

quasi-periodic0 0.2 0.4 0.6 0.8 1

0

1

2

3

4

16

Features of chaotic behavior - III

•Bounded state-space trajectory

0.2 0.4 0.6 0.8 1

0.2

0.4

0.6

0.8

1

•Sensitive dependence on initial conditions

4''0

'0 1010/,10/ −+== ππ xx

10 20 30 40 50 60

0.2

0.4

0.6

0.8

1

Chaotic Systems arenon-predicible!!

… are they also useless?

17

0 10 20 30 40 50 600

0.2

0.4

0.6

0.8

1

Can we study chaos in a better way? - I• Bended up-down map

9 0 1/ 32 313 3 1/ 3 3 / 53 3( )29 15 3/ 5 9 /117 399 81 9 /11 125 3

x xxx xxM xx xxx xx

≤ <+ − ≤ < += − ≤ < +

− ≤ ≤−

0 0.2 0.4 0.6 0.8 10

0.2

0.4

0.6

0.8

1

•Divide the interval [0,1] into l parts

[ [( 1)/ , / 1,2, ,jY i l i l j l= − =

{ }, 0,1, , 1#

k jx Y k N

N

∈ = −Compute

0 0.5 10

0.01

0.02

0.03

0.04

0.05

0 0.5 10

0.01

0.02

0.03

0.04

0.05

18

• Idea: use sets of trajectories

instead of single ones

{ }1 0 0( ) | ( )S M S y X y M x x S= = ∈ = ∧ ∈Compute

Can we study chaos in a better way? - II

• Strong regular behavior, but…

there are cases where the approach does not work!

0 10 20 30 40 50 600

0.2

0.4

0.6

0.8

''0

24214892959171 x =

0 10 20 30 40

0.2

0.4

0.6

0.8

'0

150912167 x =

0 0.5 10

0.2

0.4

0.6

0.8

1

0 0.5 10

0.05

0.1

0.15

0.2

'0S

''0S

19

Densities instead of trajectories -I

)1(4)(1 kkkk xxxMx −==+

)1(

1)(

xxx

−=

πρ

1=k

2=k

3=k

20=k

1=k

2=k

3=k

4=k

0=k 0=k

00

1

1

• The final density does not depend on the initial one

20

Densities instead of trajectories -II

1=k

2=k

3=k

20=k

1=k

2=k

3=k

0=k 0=k

00

1

1

• The final density does not depend on the initial one

21

Densities instead of trajectories -III

• Densities can be very simple functions

2=k2/121)(1 −−==+ kkk xxMx

1)( =xρ

1=k

3=k

20=k

1=k

3=k

4=k

0=k 0=k

00

1

1

2=k

22

Densities instead of trajectories -IV

• Speed of convergence to depends on the map

2=k

1) (mod kkk xxMx `1 1000)( ==+

ρ

1=k1=k0=k 0=k

00

1

1

2=k

1000

1)( =xρ

20=k

23

“Heuristic” remarks

• The final density does not depend on the initial one

• Different maps have different densities

• Speed of convergence to depends- on the map- on the initial density

ρ Tool for predicting the evolution of densities is needed

24

An alternative approach

{ } dxxdxxxdxx )(2/2/ Pr 00 ρ=+≤≤−

0ρ

0 x

dx

1 ∆kx

1kx +M

If x0 is drawn according to ρ0, which is the density of x1 =M(x0), x2 =M(x1),...?

• Chaotic map

with and k ∈N)(1 kk xMx =+

[ ] [ ]1,01,0: =XM [ ]1,00 ∈x

25

Prerequisites - I

σ-Algebra: collection A of subsets of a set X such that:

1. When

2. Sequence (finite or not) of subsets

3. (and thus )

\A X A∈ ⇒ ∈A A{ },k k kA A A∈ ⇒ ∈A A∪

X∈A \X X∅= ∈A

Measure: real valued function µ such that:

1.

2.

3. for

( ) 0A Aµ ≥ ∀ ∈A

{ },k k lA A A k l∩ ≠

( ) 0µ ∅ =

( ) ( )k kA Aµ µ=∑∪

Probability measure if

( ) 1Xµ =

Measure Space: and probability space… ( ), ,X µA

[ ]0,1 , , , nR C REx: Borel σ-algebra B on = smallest σ-algebra containing intervals

] ],1

ni

na

i→ −∞

=×R] ],a→ −∞R ] ] ] ]1 2, ,a a→ −∞ × −∞C

26

Prerequisites - II

Random variable: function ξ, (A,M,µ) probability space

1: , , ( ) ( ), ( ), ( )n nX B Bξ ξ −→ ∈ ∀ ∈A B B B such that R C R R C R

In other terms ξ assign probability to events of a probability space mapping them to suitable unions of intervalsNote: M is there… more later…

A

2R1ξ −

1ξ −

1ξ −

X

27

Prerequisites - III26 , 0, ,5

ik

e kπ

=Ex: complex random variable assuming values with equal probability. X=output of an ideal dice

62 64 contains sets=A

2R

1ξ −

28

Prerequisites - IV

k-image and k-counterimage of a set Y:

( ) { }| ( )k kM Y X y xM Yy x= ∈ = ∧ ∈ ( ) { }| ( )k kM Y X y x yM Yx− = ∈ = ∧ ∈

Measure preserving map: ( )( ) ( )1 ( )M Y Y Y Xµ µ σ− = ∀ ∈ =A

Ex: Borel σ-algebra on [0,1], n-way Bernoulli (and all other maps) is measure preserving with respect to the Lebesgue measure

1y

n

1y2y

2y

n1 1y

n

+ 2 1y

n

+ 1 1y n

n

+ − 2 1y n

n

+ −

[ [( ) [ [111 2 1 20, ( ) / , ( ) /

n

lM y y y l n y l n

−−=

= + +∪

[ [( )( )[ [( )

11

1 2 2 10

2 1 1 2

, [( ) / ( ) / ]

,

n

l

M y y y l n y l n

y y y y

µ

µ

−−

=

= + − +

= − =

∑

29

Evolution of densities: Perron-Frobenius operator)(xMy=

x

kρ

1+kρ

2x1x

y is a r.v. distributed according to kξ ρ

( )Which is the density regulating the distribution of ?M ξ

{ } { }1Pr (Pr ( ) )MM A Aξξ −∈=∈

A

{ }1

1

( )

Pr ( ) ( )k

M A

M A x dxξ ρ−

−∈ = ∫ 1( )k

A

x dxρ += ∫Note: last equality defines a density only because M is measure preserving so that Radon-Nikodym Theorem holds

Perron-Frobenius operator PM of M: define and let 1 kk M ρρ + = P [0, ]A x=

[ ]1 ( )

) ( )( k

A

M

A

k

M

x dx dx xρ ρ−

=∫ ∫P [ ]10 ([0, ])

( ) ( )x

k k

M x

M x dx x dxρ ρ−

=∫ ∫P

[ ]1 ([0, ])

( ) ( )k k

M x

M x y dyx

ρ ρ−

∂=∂ ∫P

30

Densities space

1L

D1

1=ρ

• Lebesgue norm

• Lebesgue Space

∫=X

dxxff )(1

∞<⇔∈11 and: fXff RL

Perron-Frobenius operator 11: LL →MP

=∈

∈

⇔∈ +

1

)(

1

1

ρρρ

ρ RL

D x

…its formal definition

[ ]1 ([0, ])

( ) ( ) ( ) ( ( ))M k k k

XM x

x y dy y x M y dyx x

ρ ρ ρ δ−

∂ ∂= = −∂ ∂∫ ∫P

31

…and its properties - I

1

1 1

1 1 2 2 1 1 2

([0, ])

1 1 2 2 1 1 2 2

([0, ]) ([0, ])

( ) [ ( ) ( )]

( ) ( )

M

M x

M M

M x M x

f f f y f y dyx

f y dy f y dy f fx x

α α α α

α α α α

−

− −

∂+ = + =∂

∂ ∂+ = +∂ ∂

∫

∫ ∫

P

P P

, 21 R∈∀ αα 121, L∈∀ ff• PM is a (infinite dimensional) linear operator and

21 1 2MMM Mf f= PPP

• PM has composition properties similar to M: meas. preserving 21 and MM

21

2 2

11

1 1

11

2

1

1

2

( ) ( ) ( ( ))

( )

( ) ( ) ( )

( ) ( )

M

A A A

A

M M

M M

M

M

M A

M

M

f x dx f x dx f x dx

f x dx f x dx

− −

−

−

= = =

=

∫ ∫ ∫

∫ ∫P PP

P

Note: existes since are meas. pres. In particular 1 2MMP P

21 and MM

kk

MM=P P

32

• PM is a contraction, i.e.

…and its properties - II

max( ,0), min(0, ) ,Let so that f f f f f f f f f f+ − + − + −= = − = − = +

1 1 1M f ff∀ ∈ ⇒ ≤P L

( ) M M M M M M Mf f f f f f f f+ − + − + −= − + = + =≤P P P P P P P

11

( )1

( ) ( ) ( ) ( )M M M

X XX XM

f f x dx f x dx f x dx f x dx f−

= = =≤= ∫ ∫ ∫ ∫P P P

• if and then 0≥fMP 0≥f11

ffM =P :M →P D D

Note: The PFO can be restricted to the space of densities!

…. an additional property in a minute….

1L

D1

1=ρ

0 0 if M f f≥ ≥P•

33

An important consequence: a kind of “global linearization”

∆kx

)(

times-k

)( 00 xMxMMMx kk ==

)(1 kk xMx =+

• Highly nonlinear system- “difficult” study in terms of trajectories

PM acts on probability densities as M acts on points

∆

kMk ρρ P=+1

kρ

MP

0

0 ρρρ kMMk k PP ==

• Linear system- “useful” study in terms of densities

34

• Bounded functions space, i.e.

…and its properties - III

Let measurable and the indicator functionA gA

χ=

1,f g ∞∀ ∈ ∀ ∈L L

( ) ( ) ( ) ( )M

X

M

X

f x g x dx f x g x dx=∫ ∫ UP

• Adjoint property, i.e. if

: andf f X f∞ ∞∈ ⇔ <∞L R

• Koopman operator :M ∞ ∞→U L L

M g g M=U Time push-forward

1 ( )

( ) ( ) ( ) ( )X

M

A M A

Mf x g x dx f x dx f x dx−

= =∫ ∫ ∫P P

1

1( )

( )

( ) ( ) ( ) ( ( )) ( ) ( ) ( )A M AX

M

X X M A

f x g x dx f x M x dx f x x dx f x dxχ χ −

−

= = =∫ ∫ ∫ ∫U

…It will be useful later…

35

An equivalent expression - I• Piecewise-monotonic maps

)(xMy=

x

0 0a = 1a 2a 3a 4 1a =

A

0 10 1na a a= < < < =Partition of [0,1]

' ( ) 1 expandingM x α≥ > ⇒

1,( )1, 1, , is a for

i i

ri a a

M M C r i n−

= ≥ =•

'1( ) 0 ( , ) 1, ,on i iM x a a i n−> =•2B

11 1: [ , ] ([ , ])

ii i i ii iB iB BM a a M a aφ −

− −⇒ = → =• M monotonic in each subinterval

1

1

( ) ( )n

ii

i BM A Aφ−

=

= ∩∪

1

1

1( ) ( )( )

( ) ( ) ( ) ( )i i

i

n

ii

B AB

n

M

AA

iM A

f x dx f x dx f x dx f x dxφ

φ−

=

∩∩

=

= = = =∑∫ ∫ ∫ ∫P

∪'

1

( ( )) ( )i

n

i ii B A

f y y dyφ φ= ∩

=∑ ∫

Union of mutually disjoint sets

( )ix yφ=

36

An equivalent expression - II

1

' '

1 1

1

([ , ])1'1

( )( ) ( ( )) ( ) ( ( )) ( )

( ( ))( )

( ( )) i

i

i

i

n n

M i i i ii iA

n

B

B

iM

A A

a aiA i

f x dx f y y dy f y y dy

f M yy dy

y

y

M M

χφ φ φ φ

χ−

= =

−

−=

∩

= =

=

∑ ∑∫ ∫ ∫

∑∫

P

• Since A is arbitrary

1

1

([ , ])1 ''1 ( )

( ( )) ( )( ) ( )

( )( ( )) i i

ni

M a aM xi

Mi y

f M y f xf y y

M xM M yχ

−

−

−= =

= =∑ ∑P

37

{ }Pr 2 2dy dyy y y− ≤ ≤ + =

…and a more intuitive derivation)(xMy=

x

kρ

1+kρ

2x1x

yProbability conservation constraint:

{ } { }1 1 2 21 1 1 2 2 2Pr Pr 2 2 2 2

dx dx dx dxx x x x x x− ≤ ≤ + + − ≤ ≤ +

dy

dxx

dy

dxxy kkk

22

111 )()()( ρρρ +=+ )('

)(

)('

)()(

2

2

1

11 xM

x

xM

xy kk

k

ρρρ +=+221 11 )()()( dxxdxxdyy kkk ρρρ +=+ ⇒ ⇒

1( )

( )( ) ( )

'( )k

Mk kM x y

xy y

M x

ρρ ρ+=

= = ∑PPerron-Frobenius operator PM of M for maps with “several branches”

38

Two simple examples -I

)(xMy=

x

kρ

1+kρ

2x1x

y

2' 2/12/ 21 =−== Myxyx

≤≤−<≤

=12/122

2/102)(

xx

xxxMTent Map [ ]

1 ([0 , ])

( ) ( )k k

M y

M y x dxy

ρ ρ−

∂=∂ ∫P

12

0 1 2

( ) ( )

y

k ky

x dx x dxy

ρ ρ−

∂ = + ∂ ∫ ∫

( )1 22( ) (1 )2 2k k

yyy y

y yρ ρ

∂ −∂= − −

∂ ∂

( )

( )( )

'( ) k

MM x y

xy

M x

ρρ=

= ∑P

( / 2) (1 / 2)

2 2

y yρ ρ −= +

39

Two simple examples -II

[ ]1 ([0 , ])

( ) ( )k k

M y

M y x dxy

ρ ρ−

∂=∂ ∫P

( 1)

1 ( 1)

( )

y in nn

ki i

n

x dxy

ρ−+

= −

∂ = ∂ ∑ ∫

( ) ( )1

( 1)( 1)n

ki

y in ny i

n n yρ

=

−∂ +−= +

∂∑

( )

( )( )

'( ) k

MM x y

xy

M x

ρρ=

= ∑P

1

( / ( 1) / )n

i

y n i n

n

ρ=

+ −=∑

)(xMy=

x

kρ

1+kρ

2x1x

y

nx

1mod)( xnxM =n-way Bernoulli shift

nMninyxi =−+= ' /)1(/

40

Where are we?

Are we able to obtain the regular behaviors?

∆

kMk ρρ P=+1

kρ

MP

0

0 ρρρ kMMk k PP ==

• “Equivalent” Linear system- “useful” study in terms of densities

• The final density does not depend on the initial one

• Different maps have different densities

• Speed of convergence depends on map and initial density

41

Examples of densities iteration -I

2

)2/1(

2

)2/()(

yyyM

−+= ρρρP

≤≤−<≤

=12/122

2/102)(

xx

xxxMTent Map 1mod4)( xxM =4-way Bernoulli shift

∑=

−+=4

1 4

)4/)1(4/()(

iM

iyy

ρρP

0 0.2 0.4 0.6 0.8 10

0.25

0.5

0.75

1

1.25

1.5

0 0.2 0.4 0.6 0.8 10

0.25

0.5

0.75

1

1.25

1.5

• Speed of convergence to depends on the mapρ

0( ) sin( )2x xπρ π=

42

Examples of densities iteration -II)(xMy=

x 0 0.2 0.4 0.6 0.8 10

0.5

1

1.5

2

0( ) sin( )2x xπρ π= 0( ) 2x xρ =

• Speed of convergence to depends on the initial density

• The final density does not depend on the initial one

ρ

Irregular behavior in terms of evolution of points (trajectories)Regular behavior (convergence to ) in terms of

evolution of densitiesρ

0 0.2 0.4 0.6 0.8 10

0.25

0.5

0.75

1

1.25

1.5

43

• Does a “final” density always exists in D ?

• Does a fixed point of always exists in D ?

• If it exists, is it unique ?

ρρ =MP1L

Dρ

ρ

Explaining the regularities -I

ρ

ρ

In general NObut …

Several degree of complexity in the map behavior can be defined

44

Measure preserving maps - I Theorem: (Poincarré recurrence theorem, 1899)

M

( , , )X µA

measure preserving transformation on

normalized measure space

( ) 0A Aµ∈ >A

Almost all points of A return infinitely often in A under the iteration of M

The behavior is not necessarely complicated….

( )M x x= ⇒ Any point of A never leaves A!

0 0 0Mρ ρ ρ∀ ∈ ⇒ =PD⇒

The behavior is not complicated (interesting) neither in terms of trajectories nor in terms of densities….

45

• Counterimage set of

• Ergodic maps:

– Invariant set A– The map is ergodic if and only if

Ergodic (and non- ergodic) maps - I

( ) AAM =−1

( ) ( ) 10)(1 ==⇒=− AAAAM or µµ)(xMy=

x

A

)(1 AMA −=2/1)( =Aµ Non-ergodic!

∆

∆

Are Tent map, n-way Bernoulli,…

ergodic?

[ ]1,0⊂A

( ) [ ]{ }AyxMyxAM ∈=∈=− ),(1,01

46

)(xMy=

x

Ergodic maps -II

( ) 2 (mod1)M x x=

1( )Assume invariantA M A−=•

1 1 2 2( ) ( ) if and then x A M x M x x A⇒ ∈ = ∈

1[0, ]2( ) ( )1[ ,1]2Since M M=•

( ) ( )( )

1[0, ]21( ) 2 [0, ]2 1[0, ]2

AA A

µµ µ

µ

∩= ∩ =

( ) ( )1 1[0, ] ( ) [0, ]2 2A Aµ µ µ∩ = ( ) ( )1 1[ ,1] ( ) [ ,1]2 2A Aµ µ µ∩ =

11

12

1 1( ) [0, ] ( ) [ ,1]2 2 set B B B B BM M− −∀ = ∩ = ∩

( ) ( ) ( )11 2( ) 2 2A M B A B A Bµ µ µ−∩ = ∩ = ∩

( ) ( ) ( ) dyadic interval also for union....E A E A Eµ µ µ∀ ⇒ ∩ =

( ) ( ) ( ) ( ) ( ) ( )20 0 1 or A A A A A A Aµ µ µ ε ε µ µ µ∩ − < ∀ > ⇒ = ⇔ =

47

)1(mod)10/2()( += xxM

)(xMy=

10/2x

0=k1=k2=k

3=k4=k6=k

Ergodic maps -III

• Consider 100 random points with uniform distribution in

• Dynamical behavior is still not “particularly” complex. Trajectories generating from close initial points remains reasonably closed.

]25.0,0[0 0.2 0.4 0.6 0.8 1

0 0.2 0.4 0.6 0.8 1

0 0.2 0.4 0.6 0.8 1

0 0.2 0.4 0.6 0.8 1

0 0.2 0.4 0.6 0.8 1

0 0.2 0.4 0.6 0.8 1

0 0.2 0.4 0.6 0.8 1

0 0.2 0.4 0.6 0.8 1

7=k

8=k

48

• Does a “final” density always exists in D ?

• Does a fixed point of always exists in D ?

• If it exists, is it unique ?

ρρ =MP

1L

Dρ

Explaining the regularities -I

ρρ

If M is ergodic ρ exists and is unique

• Can we say something if and on the way how ?0kM ρ ρ→P

1

00

1lim

nkM

n knρ ρ

−

→∞ =

=∑P

average convergence

0 may converge to kM ρ ρ ⇒P

1

00

( )kM

k

n

n

nnρ ρ−

=

+ − ≈∑P

border effect Main trend

But may also not converge to

(oscillating behavior…)

ρ

49

Some simple invariant densities - I

1=ρ2

)2/1(

2

)2/()(

yyyM

−+= ρρρP 2/12/11 +=⇔ ⇒

( /3) ( /3 1/6) ( /3 5/12) ( /3 3/4)3

y y y yρ ρ ρ ρ+ + + + + +

)(xMy =

x

4/9

4/3

8/9

4/9

4/3

8/9

4/10 <≤ y

( )M yρ

=

P

14/3 ≤≤ y( /3 1/6) ( /3 5/12)3

y yρ ρ+ + +1/4 3/4y≤ ≤

( /3) ( /3 3/4)3

y yρ ρ+ +

49

34

9

89+

=4 4

33

8 39

+=

Ex:

Same for n-way Bernoulli

50

Some simple invariant densities - II

1/3 1/3 1/3 0

4/3 4/3 0 1/3 1/3 1/3

4/3 4/3 0

4/9 4/9

1/3 1/3 1/3

1/3 1/3 1/3 08/9 8/9

t t

ρ

= =

Verifying the expressions of the invariant densities can be difficult..

49

34

9

89+

=4 4

33

8 39

+=

Ex:

Homework: verify that for the bended u-d map

0 0.2 0.4 0.6 0.8 10

0.2

0.4

0.6

0.8

12

2

2

80 1/ 3

3( 3)

8( ) 1/ 3 9 /11

( 3)

169 /11 1

3( 3)

xx

x xx

xx

ρ

≤ < −

= ≤ < −

≤ ≤ −

51

Some simple invariant densities - II

1/3 1/3 1/3 0

4/3 4/3 0 1/3 1/3 1/3

4/3 4/3 0

4/9 4/9

1/3 1/3 1/3

1/3 1/3 1/3 08/9 8/9

t t

ρ

= =

49

34

9

89+

=4 4

33

8 39

+=

Ex:

Homework: verify that for the bended u-d map

0 0.2 0.4 0.6 0.8 10

0.2

0.4

0.6

0.8

12

2

2

80 1/ 3

3( 3)

8( ) 1/ 3 9 /11

( 3)

169 /11 1

3( 3)

xx

x xx

xx

ρ

≤ < −

= ≤ < −

≤ ≤ −

52

Some simple invariant densities - III

Verifying the expressions of the invariant densities can be difficult..

Logistic map ( ) 4 (1 )M x x x= −

[ ]1

1/ 2 1/ 2 1 1

0 1/ 2 1/ 2 1([0 , ])

( ) ( ) ( ) ( )y

k k k k

yM y

M y x dx x dx x dxy y

ρ ρ ρ ρ−

− −

+ −

∂ ∂ = = + ∂ ∂

∫ ∫ ∫P

( ) ( ) ( ) ( )1 1 1 1 1 1 1 1(1 ) (1 ) (1 ) (1 )2 2 2 2 2 2 2 2k ky y y yy y

ρ ρ∂ ∂= − − − − − + − + −∂ ∂

( ) ( )( )1 1 1 1 1(1 ) (1 )2 2 2 24 (1 )k ky y

yρ ρ= − − + + −

−

4 (1 )y x x= −

1( )

(1 )y

y yρ

π=

−Verify that

1 1 1( )

4 (1 ) 1 1 1 11 1 1 12 2 2 2 2 2 2 2

y y y y yπ π= +

− − − − −− + + −

1 2 1( )

4 (1 ) / 4 (1 )y y y yπ π= =

− −

53

Ergodicity and some consequences

• If M is measure preserving and ergodic, and a measure space

for any observable

for almost all initial conditions x0

1

0

1

00

1lim ( ) ( )) ) ((

Nk

Nk

x x dMN

xxϕ ϕ ρ−

→∞ =

=∑ ∫1ϕ∈L

Temporal mean of an observable overa given trajectory {xk}

Expected value of the observable with respect to ρ

Birkhoff ergodic theorem

Given a set B with µ(B) > 0 and setting

For almost any x0 the proportion of time an orbit spends in B is ( )Bµ

{ }0# 0 1: ( )( )

k

B

k N M x B x dx

Nρ

≤ ≤ − ∈→∫

Bχϕ=

( ), ,X µA

54

1

0

1lim

N

k kN

k

C x xNτ τ

−

+→∞ =

= ∑

• Time series

• Compute

{ } ,1,0=kxk

∆

]1,1[]1,1[: −→−M

•Birkhoff ergodic theorem

∫∑ =−

=∞→

1

0

0

1

0

)()())((1

lim dxxxxMN

kN

kN

ρϕϕ

ϕ(.)=x ⋅ρ =1/2

1 11

0 1 1

1lim ( ) ( ) ( ) ( )/2

N

k kN

k

C x M x xM x x dx xM x dxN

τ τ ττ ρ

−

→∞= − −

= = =∑ ∫ ∫

A simple auto-correlation function -I

55

-1 -0.5 0 0.5 1

-1

-0.5

0

0.5

1

1/2 0 1/2 1

2

1 1/2 0 1/2

2 (4 3) ( 4 1) (4 1) ( 4 3)C x x dx x x dx x x dx x x dx−

− −

= + + − − + − + − +∫ ∫ ∫ ∫

-1 -0.5 0 0.5 1

-1

-0.5

0

0.5

1

1 2

0

1

12 3x

C dx−

= =∫•

•

•

0=τ

2=τ

1 0 1

1

1 1 0

2 ( ) (2 1) ( 2 1)C xM x dx x x dx x x dx− −

= = + + − +∫ ∫ ∫0

232

232

1

0

230

1

23

=

+−

+=

−

xxxx

1=τ

0=

A simple auto-correlation function -II

1( )

3 Cτ δ τ=

56

A simple example

• 10 way Bernoulli shift

Is measure preserving with respect to Lebesgue measure

Is ergodic

( ) 10 (mod 1)M x x=µ

1 101

00 10

10

1 1( ( )) ( ) ( )

10i i

iN

kA A

k i

M x x x dx dxN

χ χ ρ−

= −

→ = =∑ ∫ ∫for almost all point x0 in [0,1]

For almost all points x in [0,1] (with respect to Lebesgue measure) the frequencyof any digits in the decimal expansion of x is 1/10 (normal number)

1, 0, , 9

10 10i

i iA i

+ = = 1 1 2 3 4 5 1( ) 0. iffk k ix M x A iε ε ε ε ε ε−= = ∈ =

57

In general NObut …

Explaining the regularities -II

•The unique equilibrium point of PM in D of an ergodic map is

asymptotically stable ?

ρρρ ==∞→∞→ 0limlim k

Mk

kk

P

1L

Dρ

0ρ

∞→k

58

• A map is mixing iff for any two sets A and B

• To get some insight

• The probability (according to µ ) that a point x moves from A to B after k steps, given that tends to the probability (according to µ ) of being in B.

• Mixing map ⇒ ergodic map– Assume B is invariant and set

Mixing maps - I

( )lim ( ) ( ) ( )k

kA M B A Bµ µ µ−

→∞∩ =

( )( )lim ( )

( )

k

k

A M BB

A

µµ

µ

−

→∞

∩=

Ax∈

CBBXA == \

( ) ( ) 0lim)(lim)()( =∩=∩=∞→

−

∞→BBBMBBB C

k

kC

k

C µµµµ

mixing Invariant set

59

1−=k0=k 2−=k

4−=k5−=k

=),( yxM10,2/10)2/,2( ≤≤<≤ yxyx

10,2/12/1)2/12/,12( ≤≤≤≤+− yxyx

A

B

4/1)( =Bµ

3−=k

Mixing maps -II

Baker Transformation

60

)1(mod)10/2()( += xxM

)(1 xMy −=

10/2

x

0=k1=k2=k

3=k4=k

B

6=k

Mixing (and non-mixing) maps -III

• Consider 1000 random points with uniform distribution in ]25.0,0[

7=k

8=k

0 0.2 0.4 0.6 0.8 1

0 0.2 0.4 0.6 0.8 1

0 0.2 0.4 0.6 0.8 1

0 0.2 0.4 0.6 0.8 1

0 0.2 0.4 0.6 0.8 1

0 0.2 0.4 0.6 0.8 1

0 0.2 0.4 0.6 0.8 1

0 0.2 0.4 0.6 0.8 1

A

( ))(lim BMA k

k

−

∞→∩∃/ µ

Tent map, n-way Bernoulli,…

are mixing

… but proving mixingness is a very difficult task

61

A proof of the Birkhoff theorem for mixing maps - I• If M is measure preserving and mixing, and a measure space

for any observable

for almost all initial conditions x0

1ϕ∈L( ), ,X µA

• Since we may refer to simple functions (this will not affect the nature of the phenomenon that is linked to the nature of the map)

1ϕ∈LAϕ χ⇒ =

1

00

1( ( )) ( ) ( )

Nk

Ak A

M x x dx AN

χ ρ µ−

=

→ =∑ ∫

1

0

1

00

1lim ( ) ( )) ) ((

Nk

Nk

x x dMN

xxϕ ϕ ρ−

→∞ =

=∑ ∫

• Compute the mean square error:21

2 0

0

1( ( )) ( )

Nk

N Ak

M x AN

σ χ µ−

=

= −

∑E

Random variablevariance

• We want to show that 1

0

0

10 Pr ( ( )) ( ) 0

NNk

Ak

M x AN

ε χ µ ε−

→∞

=

∀ > − > →

∑

62

A proof of the Birkhoff theorem for mixing maps - II

1 12

0 00 0

1 1( ( )) ( ) ( ( )) ( )

N Nk j

N A Ak j

M x A M x AN N

σ χ µ χ µ− −

= =

= − −

∑ ∑E

( )( )1 1

0 02

0 0

1( ( )) ( ) ( ( )) ( )

N Nk j

A Ak j

M x A M x AN

χ µ χ µ− −

= =

= − − ∑∑E

{}

1 1

0 0 020 0

20

1( ( )) ( ( )) ( ) ( ( ))

( ) ( ( )) ( )

N Nk j j

A A Ak j

kA

M x M x A M xN

A M x A

χ χ µ χ

µ χ µ

− −

= =

= −

− +

∑∑ E E

E

( )Aµ

( )Aµ ( )1 1

20 02

0 0

1( ( )) ( ( )) ( )

N Nk j

A Ak j

M x M x AN

χ χ µ− −

= =

= − ∑∑ E

Measure of points that are in A after j and k iterations

( )( )1 1

22

0 0

( ) (1

() )k jN N

k j

M A M AAN

µµ− −

=

− −

=

= ∩ −∑∑

63

A proof of the Birkhoff theorem for mixing maps - III

( )( )1 1

22

0 0

1( ) ( ) ( )

N Nk j

k j

M A M A AN

µ µ− −

− −

= =

= ∩ −∑∑

• We need to compute the double sum Similar to the definition of mixing…

j k=j k>

j k<

j

k( )( )

12

02

( ) ( ) ( )1 N

j j

j

M A MN

A Aµ µ−

− −

=

∩ −

= ∑

( )( )11

( ) 2

1 0

( ) ( ( )) ( )jN

k j k k

j k

M A M M A Aµ µ−−

− − − −

= =

∩ −+∑∑

( )( )1 1

( ) 2

1 0

( ) ( ( )) ( )N k

j k j j

k j

M A M M A Aµ µ− −

− − − −

= =

∩+

−∑∑

1

021

1

10

1 1 22 ( as 2) 0

NN

lN

l NllN N

NNN

lα α αα α− −

→

==

∞ = ≤ + − → →

+ ∑∑

meas pres

( ( )) ( )jM A Aµ µ− =

Identical

• Tschebyscheff bound 21

0 00

1for almost all Pr ( ( )) ( ) 0

NNk N

Ak

x M x AN

σχ µ εε

−→∞

=

− > ≤ →

∑

64

1d

1ξ 2ξ 3ξ 4ξ 5ξ0 1

2d3d

4d

f

The bounded variation space -I

≤<<<≤−= ∑=

+≥

10:)()(supvar 211

11

m

m

jjj

mfff ξξξξξ …

• Variation of a function f(x)

4321var ddddf +++= for PW constant f1

'

0

var ( )f f x dx∫∼ for smooth f

Bounded Variation (BV) norm

fff BV

var1+=

Bounded variation space

[ ]BV

BV

: 0,1ff

f

∈ ⇔ <∞

RL

BV 1

BV 1

f f>

⇒ ⊂L L

65

eigenvalues eigenspaces

The bounded variation space -II

BVBV LL:MP

ffM λ=PC∈λ λE∈f

• Consider the spectrum of the linear operator

{ }ρ=∩DE1

• If M is mixing and expanding ( )

- with finite dimensional eigenspace

- isolated eigenvalues

- is an eigenvalues of PM

1' >M

essr<∀ γγ,li

i,,2,11 =<γ

essrmixr

1=λ][Re λ

][Im λ

1γ

2γ4γ

3γ

γ11 =λ

10 <≤< mixess rr

Asymptotic stability11 <<⇒≠ mix rλλ

1/

ess

1lim sup

k

kkx

rDM→∞

=

66

The bounded variation space -III

k0 0 BV miBV x 0

M

kk

C rρ ρ ρ →∞− ≤ →P

Speed of convergence to equilibrium

Difficult to estimatein general

Way of convergence depends on initial density and map!

How can we show this?

• Computing the statistical features of chaotic sequences is generally a very difficult task

[ ]1 0 mx2 2 1 i1 2( ) ( ) ( ) ( ) ( ) ( ) sup sup kk k

X X

C E rx x x x dx x x dxϕ ϕ ϕ ρ ϕ ρ ϕ ϕ= − ≤Λ∫ ∫

21 2 , ([0,1])ϕ ϕ∀ ∈ LFor mixing maps M, only bounds can be achieved, i.e.

Remark:

Uncorrelationfor large k

67

Mixing maps properties - I

k0 0 0 0BVBV BVBV mix

M

k k k C rρ ρ ρ ρ ρ− = ≤ ≤P Q Q

• For mixing maps the PFO can be decomposed as

1M = +ΠP Q

1 ( )X

f f x dxρΠ = ∫ kind of projection of the invariant eigenspacef∀ ∈ BVL 1E1.

k kCr≤QV mixB

where for operators1

supf

f

f==

KK BV

BVBV

2.

1 0Π =Q3.1

0 0 0 0 0 0 0

0

1 1

1

( )kk k k kM x dxρ ρ ρ ρ ρ ρ ρρ

=

Π Π+ = + += = ∫Q QP Q

68

Mixing maps properties - II

[ ]1 0 2 1 2 1 2( ) ( ) ( ) ( ( )) ( ) ( ) ( ) ( )kM

kk

X X

E x x x M x x dx x x x dxϕ ϕ ϕ ϕ ρ ϕ ϕ ρ= = =∫ ∫ U

{ }2 1 2 1 11( ) [ ( )] ( ) [ ] [ ] ( )X

k k

X

Mx x dx x x dxϕ ϕ ρ ϕ ϕ ρ ϕ ρ= = +Π =∫ ∫P Q

Koopman operatorKoopman adjoint of PFO

PFO decomposition for mixing maps

2 12 1 ( ) [ ]( )( ) ( ) ( ) ( )X X

k

X

x x y y dy d x dx x xϕ ϕ ϕϕ ρ ρρ

+

⇒∫ ∫ ∫ Q

[ ] 1 21 0 2 2 1( ) ( ) (( ) ( ) ( ) [ ]( )) ( )X

kk

X

k

X

x x dx x xC E x dxx x x dxϕ ρ ϕ ρϕ ϕ ϕ ϕ ρ= − = ∫∫ ∫ Q

2 1 2 1 2 1 B mixV1 BVsup [ ] sup [ ] supk k krϕ ϕ ρ ϕ ϕ ρ ϕ ϕ ρ≤ ≤ ≤Q Q

69

• The unique equilibrium point of PM in D of an ergodic map is

asymptotically stable ?

ρρρ ==∞→∞→ 0limlim k

Mk

kk

P

If M is mixing and expanding (|M’|>1) the system is asymptotically stable

Explaining the regularities -II

• A map is chaotic if it is at least mixing

1L

D ρ

0ρDL ∩BV

70

“Heuristic” remarks

• The final density does not depend on the initial one

• Different maps have different densities

• Speed of convergence to depends- on the map- on the initial density

ρ

Ergodic

( )

( )( )

'( )MM x y

f xf y

M x=

= ∑P

k0 0 mix 0

M

kk

C rρ ρ ρ →∞− ≤ →P

71

Additional examples: ergodic map -I

• Chunk of 1000 random points with uniform distribution in ]1.0,1.0[]1.0,1.0[ ×

1=k0=k 2=k

3=k4=k5=k

( ) 1mod3,2),( yxyxM ++=

72

Additional examples: mixing map -II

• Chunk of 1000 random points with uniform distribution in ]1.0,1.0[]1.0,1.0[ ×

1=k0=k 2=k

3=k4=k5=k

( ) 1mod2,),( yxyxyxM ++=

73

Additional examples -III

• Chunk of 1000 random points with uniform distribution in

( ) 1mod3,3),( yxyxyxM ++=

1=k0=k 2=k

3=k4=k5=k

]1.0,1.0[]1.0,1.0[ ×

74

• Image set of

• Exact maps:

• Exact map ⇒ Mixing map

Exact (and non- exact) maps - II

1))((lim0)( =⇒>∞→

AMA k

k µµ

[ ]1,0⊂A

( ) [ ]{ }AxxMyyAM ∈=∈= ),(1,0

Proving exactness is easier

than proving mixingness… but how?

)(xMy=

10/2x

0=k1=k2=k

3=k4=k

A

0 0.2 0.4 0.6 0.8 1

0 0.2 0.4 0.6 0.8 1

0 0.2 0.4 0.6 0.8 1

0 0.2 0.4 0.6 0.8 1

0 0.2 0.4 0.6 0.8 1

4/1))(())(()( ==== AMAMA k µµµ

75

Is it enough?

performanceindex in termsof statisticalfeatures of signals

PerformanceOptimization

signals withtunable

statisticalfeatures

How do I characterize/generate them ?Is it possible by using chaos

• Proving mixingness is a very difficult task, for exactness it is easier, but how?

• Computing the invariant density and isnot easy (usually we have verified with PM )

• Computing the statistical features of chaotic sequences is generally a very difficult taskIn general only bounds….

[ ]1 0 m2 1 2 ix( ) ( ) sup sup kk kC E x x rϕ ϕ ϕ ϕ= ≤Λ

ρrmix

Not enough for engineering purposes!

76

• Can the statistical approach be used to collect information on a single trajectory ?

)()( 00 xxx −=δρ

Statistical “nature”of the associate system

If M is ergodic and measure preserving there is a unique ρ(and Birkoff theorem holds )

Even if M is exact (mixing) asymptotic stability is not guaranteed

The statistical approach cannot be usedto track single trajectories

⇒∈ 10 )( Lxρ

⇒∉ BVL)(0 xρ

1L

D

ρ

)( 0xx −δ

DL ∩BV

77

Nonlinear dynamics and statistics - IRandom variable: function ξ, (A,M,µ) probability space

1: , ( ) ( )X B Bξ ξ −→ ∈ ∀ ∈A B such that R RProperty: ξ1, ξ2, …,ξk define a stationary process if

11( ) ( ( ))k

k x M x Mξ ξ −= with measure preserving

11ξ −

RX

RX

1kξ −

kM

Stationary processes have an “intrinsic mapping” which preserves probability (measure), so that I can forget the time instant, if I use the right even instead of x

1( )kM x−

{ } ] ]( ){ }1( ) Pr Pr ,k k kF x x xξ ξ ξ −= < = −∞ =

] ]( ){ } ] ]( ){ } 1

1 1( 1)1 1Pr , Pr , ( )kM x x F xξξ ξ− −− − −∞ = −∞ =

78

Statistics and operatorsRandom process with memory 1

1 1 1 1 1 1( ( ) | ( ) , , ( ) ) ( ( ) | ( ) )n n n n n n n nf t x t x t x f t x t xξ ξξ ξ ξ ξ ξ− − − −= = = = = =

If the process is stationary, the joint probability density can be expressed as a function of the transition probability only! And not also on the single pdf

0 1

1

10

( ( ) , ( 1) , , ( ) )

( ( ) | ( 1) ) ( ( ) )

n

n

j j nj

f t x t x t n x

f t j x t j x f t n x

ξ

ξ ξ

ξ ξ ξ

ξ ξ ξ−

−=

= − = − = =

− = − − = − =∏

( , ) ( ( ) | ( 1) )K x y f t x t yξ ξ ξ= = − =

, , , 1 , 1 ,( ) ( , ) ( , ) ( ) ( , ) ( )t t t t tf f x y dy K x y f y dy K x y f y dyξ ξ ξ ξξ − −= = =∫ ∫ ∫

( , ) ( ( )) completely deterministic....K x y x M yδ= − Birkhoff….