approccio statistico all'analisi di sistemi caotici e ...approccio statistico all'analisi...
TRANSCRIPT
![Page 1: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/1.jpg)
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
![Page 2: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/2.jpg)
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
![Page 3: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/3.jpg)
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
![Page 4: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/4.jpg)
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
![Page 5: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/5.jpg)
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
![Page 6: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/6.jpg)
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
![Page 7: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/7.jpg)
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
![Page 8: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/8.jpg)
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?
![Page 9: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/9.jpg)
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 =
![Page 10: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/10.jpg)
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
![Page 11: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/11.jpg)
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
![Page 12: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/12.jpg)
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
![Page 13: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/13.jpg)
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
![Page 14: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/14.jpg)
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!
![Page 15: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/15.jpg)
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
![Page 16: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/16.jpg)
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?
![Page 17: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/17.jpg)
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
![Page 18: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/18.jpg)
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
![Page 19: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/19.jpg)
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
![Page 20: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/20.jpg)
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
![Page 21: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/21.jpg)
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
![Page 22: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/22.jpg)
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
![Page 23: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/23.jpg)
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
![Page 24: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/24.jpg)
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
![Page 25: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/25.jpg)
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
![Page 26: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/26.jpg)
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
![Page 27: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/27.jpg)
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ξ −
![Page 28: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/28.jpg)
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
µ
µ
−−
=
= + − +
= − =
∑
![Page 29: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/29.jpg)
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
![Page 30: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/30.jpg)
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
![Page 31: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/31.jpg)
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
![Page 32: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/32.jpg)
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•
![Page 33: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/33.jpg)
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
![Page 34: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/34.jpg)
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…
![Page 35: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/35.jpg)
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φ=
![Page 36: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/36.jpg)
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
![Page 37: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/37.jpg)
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”
![Page 38: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/38.jpg)
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ρ ρ −= +
![Page 39: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/39.jpg)
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(/
![Page 40: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/40.jpg)
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
![Page 41: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/41.jpg)
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πρ π=
![Page 42: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/42.jpg)
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
![Page 43: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/43.jpg)
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
![Page 44: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/44.jpg)
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….
![Page 45: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/45.jpg)
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
![Page 46: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/46.jpg)
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µ µ µ ε ε µ µ µ∩ − < ∀ > ⇒ = ⇔ =
![Page 47: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/47.jpg)
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
![Page 48: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/48.jpg)
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…)
ρ
![Page 49: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/49.jpg)
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
![Page 50: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/50.jpg)
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
ρ
≤ < −
= ≤ < −
≤ ≤ −
![Page 51: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/51.jpg)
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
ρ
≤ < −
= ≤ < −
≤ ≤ −
![Page 52: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/52.jpg)
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π π= =
− −
![Page 53: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/53.jpg)
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
![Page 54: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/54.jpg)
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
![Page 55: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/55.jpg)
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τ δ τ=
![Page 56: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/56.jpg)
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ε ε ε ε ε ε−= = ∈ =
![Page 57: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/57.jpg)
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
![Page 58: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/58.jpg)
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
![Page 59: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/59.jpg)
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
![Page 60: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/60.jpg)
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
![Page 61: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/61.jpg)
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
ε χ µ ε−
→∞
=
∀ > − > →
∑
![Page 62: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/62.jpg)
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
µµ− −
=
− −
=
= ∩ −∑∑
![Page 63: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/63.jpg)
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
σχ µ εε
−→∞
=
− > ≤ →
∑
![Page 64: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/64.jpg)
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
![Page 65: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/65.jpg)
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→∞
=
![Page 66: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/66.jpg)
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
![Page 67: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/67.jpg)
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
![Page 68: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/68.jpg)
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
![Page 69: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/69.jpg)
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
![Page 70: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/70.jpg)
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
![Page 71: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/71.jpg)
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 ++=
![Page 72: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/72.jpg)
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 ++=
![Page 73: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/73.jpg)
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[ ×
![Page 74: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/74.jpg)
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 µµµ
![Page 75: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/75.jpg)
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!
![Page 76: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/76.jpg)
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
![Page 77: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/77.jpg)
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ξξ ξ− −− − −∞ = −∞ =
![Page 78: Approccio Statistico all'Analisi di Sistemi Caotici e ...Approccio Statistico all'Analisi di Sistemi Caotici e Applicazioni all'Ingegneria dell'Informazione ... in Telecommnunications,](https://reader030.vdocumenti.com/reader030/viewer/2022040321/5e51b266bb614c5f912c8be6/html5/thumbnails/78.jpg)
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….