Ergodic theory is hard to study because it is based on measure theory, which is a technically difficult subject to master for ordinary students, especially for physics majors. Many of the examples are introduced from a different perspective than in other books and theoretical ideas can be gradually absorbed while doing computer experiments. Theoretically less prepared students can appreciate the deep theorems by doing various simulations. The computer experiments are simple but they have close ties with theoretical implications. Even the researchers in the field can benefit by checking their conjectures, which might have been regarded as unrealistic to be programmed easily, against numerical output using some of the ideas in the book. One last remark: The last chapter explains the relation between entropy and data compression, which belongs to information theory and not to ergodic theory. It will help students to gain an understanding of the digital technology that has shaped the modern information society.
Author(s): Geon Ho Choe
Series: Algorithms and Computation in Mathematics
Edition: 1
Publisher: Springer
Year: 2005
Language: German
Pages: 474
Cover......Page 1
Algorithms and Computation in Mathematics Volume 13......Page 2
Computational Ergodic Theory......Page 4
3540231218......Page 5
Preface......Page 8
Acknowledgements......Page 12
Contents......Page 14
1.1.1 Sets and functions ......Page 22
1.1.2 Metric spaces ......Page 23
1.2.1 Measure ......Page 25
1.2.2 Lebesgue integration ......Page 27
1.3.1 Perron–Frobenius Theorem ......Page 32
1.3.2 Stochastic matrices ......Page 34
1.4.1 Compact abelian groups ......Page 35
1.4.2 Characters ......Page 37
1.4.3 Fourier series ......Page 38
1.4.4 Endomorphisms of a torus ......Page 39
1.5 Continued Fractions ......Page 41
1.6.1 Independent random variables ......Page 42
1.6.3 Statistical laws ......Page 44
1.7.1 What are random numbers? ......Page 46
1.7.2 How to generate random numbers ......Page 48
1.8 Basic Maple Commands ......Page 49
1.8.2 Set theory and logic ......Page 50
1.8.3 Arithmetic ......Page 52
1.8.4 How to plot a graph ......Page 53
1.8.5 Calculus: differentiation and integration ......Page 55
1.8.6 Fractional and integral parts of real numbers ......Page 56
1.8.7 Sequences and printf ......Page 57
1.8.8 Linear algebra ......Page 58
1.8.9 Fourier series ......Page 60
1.8.10 Continued fractions I ......Page 61
1.8.11 Continued fractions II ......Page 62
1.8.12 Statistics and probability ......Page 63
1.8.14 Random number generators in Maple ......Page 65
1.8.15 Monte Carlo method ......Page 66
2.1 Invariant Measures ......Page 68
2.2 Other Types of Continued Fractions ......Page 77
2.3 Shift Transformations ......Page 80
2.4 Isomorphic Transformations ......Page 81
2.5 Coding Map ......Page 87
2.6 Maple Programs ......Page 91
2.6.1 The logistic transformation ......Page 92
2.6.2 Chebyshev polynomials ......Page 94
2.6.3 The beta transformation ......Page 97
2.6.4 The baker’s transformation ......Page 99
2.6.5 A toral automorphism ......Page 100
2.6.6 Modified Hurwitz transformation ......Page 101
2.6.7 A typical point of the Bernoulli measure ......Page 102
2.6.8 A typical point of the Markov measure ......Page 103
2.6.9 Coding map for the logistic transformation ......Page 105
3.1 Ergodicity ......Page 106
3.2 The Birkhoff Ergodic Theorem ......Page 110
3.3 The Kronecker–Weyl Theorem ......Page 118
3.5 Borel’s Normal Number Theorem ......Page 120
3.6 Continued Fractions ......Page 121
3.7 Approximation of Invariant Density Functions ......Page 124
3.8 Physically Meaningful Singular Invariant Measures ......Page 126
3.9.1 The Gauss transformation ......Page 133
3.9.2 Discrete invariant measures ......Page 134
3.9.3 A cobweb plot ......Page 135
3.9.4 The Kronecker-Weyl Theorem ......Page 136
3.9.5 The logistic transformation ......Page 137
3.9.6 An unbounded invariant density and the speed of growth at a singularity ......Page 139
3.9.7 Toral automorphisms ......Page 141
3.9.8 The Khinchin constant ......Page 142
3.9.9 An infinite invariant measure ......Page 144
3.9.10 Cross sections of the solenoid ......Page 146
3.9.11 The solenoid ......Page 147
3.9.13 The Hénon attractor......Page 151
3.9.14 Basin of attraction for the Hénon attractor......Page 152
4.1 Mixing Transformations ......Page 154
4.2 The Central Limit Theorem ......Page 159
4.3 Speed of Correlation Decay ......Page 164
4.4.1 The Central Limit Theorem: σ > 0 for the logistic transformation......Page 168
4.4.2 The Central Limit Theorem: the normal distribution for the Gauss transformation ......Page 169
4.4.4 Correlation coefficients of Tx = 2x mod 1 ......Page 172
4.4.5 Correlation coefficients of the beta transformation ......Page 173
4.4.6 Correlation coefficients of an irrational translation mod 1 ......Page 174
5.1 Absolutely Continuous Invariant Measures ......Page 176
5.2 Boundary Conditions for Invariant Measures ......Page 177
5.3 Kac’s Lemma on the First Return Time ......Page 180
5.4 Ergodicity of Markov Shift Transformations ......Page 186
5.5 Singular Continuous Invariant Measures ......Page 191
5.6 An Invertible Extension of a Transformation on an Interval ......Page 193
5.7.1 Piecewise defined transformations ......Page 194
5.7.2 How to sketch the graph of the first return time transformation ......Page 195
5.7.3 Kac’s lemma for the logistic transformation ......Page 196
5.7.4 Kac’s lemma for an irrational translation mod 1 ......Page 197
5.7.5 Bernoulli measures on the unit interval ......Page 199
5.7.6 An invertible extension of the beta transformation ......Page 200
6.1 Rotation Number ......Page 204
6.2 Topological Conjugacy and Invariant Measures ......Page 209
6.3 The Cantor Function and Rotation Number ......Page 214
6.4 Arnold Tongues ......Page 215
6.5 How to Sketch a Conjugacy Using Rotation Number ......Page 216
6.6 Unique Ergodicity ......Page 217
6.7 Poincaré Section of a Flow......Page 219
6.8.1 The rotation number of a homeomorphism of the unit circle ......Page 220
6.8.2 Symmetry of invariant measures ......Page 221
6.8.3 Conjugacy and the invariant measure ......Page 222
6.8.5 The Cantor function as a cumulative density function ......Page 223
6.8.6 Rotation numbers and a staircase function ......Page 225
6.8.7 Arnold tongues ......Page 226
6.8.8 How to sketch a topological conjugacy of a circle homeomorphism I ......Page 227
6.8.9 How to sketch a topological conjugacy of a circle homeomorphism II ......Page 228
7.1 Mod 2 Normal Numbers ......Page 232
7.2 Skew Product Transformations ......Page 234
7.3 Mod 2 Normality Conditions ......Page 239
7.4 Mod 2 Uniform Distribution for General Transformations ......Page 242
7.5 Random Walks on the Unit Circle ......Page 243
7.6 How to Sketch a Cobounding Function ......Page 247
7.7.1 Failure of mod 2 normality for irrational translations mod 1 ......Page 250
7.7.2 Ergodic components of a nonergodic skew product transformation arising from the beta transformation ......Page 252
7.7.3 Random walks by an irrational angle on the circle ......Page 253
7.7.4 Skew product transformation and random walks on a cyclic group ......Page 254
7.7.5 How to plot points on the graph of a cobounding function ......Page 255
7.7.6 Fourier series of a cobounding function ......Page 256
7.7.7 Numerical computation of a lower bound for n||nθ||......Page 257
8.1 Definition of Entropy ......Page 258
8.2 Entropy of Shift Transformations ......Page 263
8.3 Partitions and Coding Maps ......Page 266
8.4 The Shannon–McMillan–Breiman Theorem ......Page 269
8.5 Data Compression ......Page 273
8.6 Asymptotically Normal Distribution of (-log P_n)/n......Page 274
8.7.1 Definition of entropy: the logistic transformation ......Page 275
8.7.2 Definition of entropy: the Markov shift ......Page 276
8.7.3 Cylinder sets of a nongenerating partition: Tx = 2x mod 1 ......Page 277
8.7.4 The Shannon–McMillan–Breiman Theorem: the Markov shift ......Page 279
8.7.5 The Shannon–McMillan–Breiman Theorem: the beta transformation ......Page 281
8.7.6 The Asymptotic Equipartition Property: the Bernoulli shift ......Page 282
8.7.7 Asymptotically normal distribution of (-log P_n)/n: the Bernoulli shift......Page 286
9.1 The Lyapunov Exponent of Differentiable Maps ......Page 290
9.2 Number of Significant Digits and the Divergence Speed ......Page 299
9.3 Fixed Points of the Gauss Transformation ......Page 301
9.4 Generalized Continued Fractions ......Page 303
9.5 Speed of Approximation by Convergents ......Page 307
9.6 Random Shuffling of Cards ......Page 311
9.7.1 The Lyapunov exponent: the Gauss transformation ......Page 313
9.7.2 H_{n,k}: a local version for the Gauss transformation......Page 314
9.7.4 The divergence speed: a local version for the Gauss transformation ......Page 315
9.7.6 Number of correct partial quotients: validity of Maple algorithm of continued fractions ......Page 316
9.7.7 Speed of approximation by convergents: the Bernoulli transformation ......Page 318
10.1 Singular Values of a Matrix ......Page 320
10.2 Oseledec’s Multiplicative Ergodic Theorem ......Page 323
10.3 The Lyapunov Exponent of a Differentiable Mapping ......Page 331
10.4 Invariant Subspaces ......Page 336
10.5 The Lyapunov Exponent and Entropy ......Page 339
10.6 The Largest Lyapunov Exponent and the Divergence Speed ......Page 342
10.7.1 Singular values of a matrix ......Page 344
10.7.2 A matrix sends a circle onto an ellipse ......Page 345
10.7.3 The Lyapunov exponents: a local version for the solenoid mapping ......Page 346
10.7.4 The Lyapunov exponent: a global version for the Hénon mapping......Page 349
10.7.5 The invariant subspace E_1 of the Hénon mapping......Page 350
10.7.6 The invariant subspace E_2 of the Hénon mapping......Page 351
10.7.7 The divergence speed: a local version for a toral automorphism ......Page 352
10.7.8 The divergence speed: a global version for Hénon mapping......Page 353
11.1 Stable and Unstable Manifolds of Fixed Points ......Page 354
11.2 The Hénon Mapping......Page 357
11.3 The Standard Mapping ......Page 360
11.4 Stable and Unstable Manifolds of Periodic Points ......Page 361
11.5.1 A stable manifold of the Hénon mapping......Page 366
11.5.2 An unstable manifold of the Hénon mapping......Page 369
11.5.3 The boundary of the basin of attraction of the Hénon mapping......Page 370
11.5.4 Behavior of the Hénon mapping near a saddle point......Page 374
11.5.5 Hyperbolic points of the standard mapping ......Page 376
11.5.6 Images of a circle centered at a hyperbolic point under the standard mapping ......Page 378
11.5.7 Stable manifolds of the standard mapping ......Page 379
11.5.8 Intersection of the stable and unstable manifolds of the standard mapping ......Page 382
12.1 The First Return Time Formula ......Page 384
12.2 L^p-Convergence......Page 388
12.3 The Nonoverlapping First Return Time ......Page 390
12.4 Product of the Return Time and the Probability ......Page 397
12.5 Symbolic Dynamics and Topological Entropy ......Page 398
12.6.1 The first return time R_n for the Bernoulli shift......Page 402
12.6.2 Averages of (logR_n)/n and Rn for the Bernoulli shift......Page 403
12.6.3 Probability density function of (logR_n)/n for the Bernoulli shift......Page 404
12.6.4 Convergence speed of the average of logR_n for the Bernoulli shift......Page 406
12.6.5 The nonoverlapping first return time ......Page 407
12.6.6 Probability density function of R_nP_n for the Markov shift......Page 409
12.6.7 Topological entropy of a topological shift space ......Page 410
13.1 Hausdorff Dimension ......Page 412
13.2 Recurrence Error ......Page 414
13.3 Absolutely Continuous Invariant Measures ......Page 415
13.4 Singular Continuous Invariant Measures ......Page 419
13.5 The First Return Time and the Dimension ......Page 421
13.6 Irrational Translations Mod 1 ......Page 424
13.7 Maple Programs ......Page 429
13.7.2 The logistic transformation ......Page 430
13.7.3 The Hénon mapping......Page 432
13.7.4 Type of an irrational number ......Page 433
13.7.5 An irrational translation mod 1 ......Page 435
14.1 Coding ......Page 438
14.2 Entropy and Data Compression Ratio ......Page 440
14.3 Huffman Coding ......Page 444
14.4 Lempel–Ziv Coding ......Page 446
14.5 Arithmetic Coding ......Page 449
14.6.1 Huffman coding ......Page 450
14.6.2 Lempel–Ziv coding ......Page 454
14.6.3 Typical intervals arising from arithmetic coding ......Page 457
References ......Page 460
Index ......Page 470
