Permutation Complexity in Dynamical Systems (eBook)

Ordinal Patterns, Permutation Entropy and All That

José Amigó (Autor)

eBook Download: PDF

2010 | 2010
X, 280 Seiten
Springer Berlin (Verlag)
978-3-642-04084-9 (ISBN)

Infos

The study of permutation complexity can be envisioned as a new kind of symbolic dynamics whose basic blocks are ordinal patterns, that is, permutations defined by the order relations among points in the orbits of dynamical systems.

Since its inception in 2002 the concept of permutation entropy has sparked a new branch of research in particular regarding the time series analysis of dynamical systems that capitalizes on the order structure of the state space. Indeed, on one hand ordinal patterns and periodic points are closely related, yet ordinal patterns are amenable to numerical methods, while periodicity is not.

Another interesting feature is that since it can be shown that random (unconstrained) dynamics has no forbidden patterns with probability one, their existence can be used as a fingerprint to identify any deterministic origin of orbit generation.

This book is primarily addressed to researchers working in the field of nonlinear dynamics and complex systems, yet will also be suitable for graduate students interested in these subjects. The presentation is a compromise between mathematical rigor and pedagogical approach. Accordingly, some of the more mathematical background needed for more in depth understanding has been shifted into the appendices.

Inhalt

Preface 8
Contents 14
1 What Is This All About? 17
1.1 Patterns, Complexity, and Entropy 17
1.1.1 Information Theory 17
1.1.2 Symbolic Dynamics 20
1.1.3 Dynamical Systems 25
1.1.4 Computer Science 31
1.1.5 Cellular Automata 34
1.2 Admissible and Forbidden Ordinal Patterns 37
2 First Applications 45
2.1 Entropy Estimation 45
2.2 Permutation Complexity 49
2.3 Estimation of Control Parameters from Symbolic Sequences 53
2.4 Characterizing Synchronization 59
3 Ordinal Patterns 65
3.1 Symbol Patterns 66
3.2 Order Relations 68
3.3 Ordinal Patterns Defined by Maps 70
3.4 Properties of the Ordinal Patterns 73
3.4.1 Invariance Under Order Isomorphism 73
3.4.2 Growth of Forbidden Patterns with Length: Outgrowth Patterns 76
3.4.3 Robustness Against Noise in Deterministic Time Series 79
4 Ordinal Structure of the Shifts 84
4.1 Ordinal Patterns and the Shift Maps 84
4.2 Forbidden Patterns for One-Sided Shifts 86
4.3 Forbidden Patterns for Two-Sided Shifts 96
5 Ordinal Structure of the Signed Shifts 99
5.1 Ordinal Patterns and the Tent Map 99
5.1.1 A State-Dependent Shift Approach to the Tent Map 99
5.1.2 The Interval Structure of the Sets P 103
5.2 Ordinal Patterns and the Signed Shifts 105
6 Metric Permutation Entropy 119
6.1 The Metric Permutation Entropy of a Finite-State Process 120
6.2 Permutation Metric Entropy of Maps 128
6.3 On the Definition of Metric Permutation Entropy for Maps 132
6.4 Numerical Issues 136
7 Topological Permutation Entropy 139
7.1 Topological Permutation Entropy of Sources 139
7.2 Constrained Sequences 141
7.3 Topological Permutation Entropy of Maps 145
7.4 Relation Between Topological Entropy and Topological Permutation Entropy 147
7.5 Estimating Topological Entropy 150
7.6 Existence of Forbidden Ordinal Patterns 152
7.7 Numerical Simulations 154
8 Discrete Entropy 160
8.1 Discrete Entropy 161
8.2 The Infinite Limit 165
8.3 Discrete Topological Entropy 169
9 Detection of Determinism 172
9.1 Dynamical Robustness Against Observational Noise 173
9.2 Detection of Determinism I: Number of Missing Ordinal Patterns 175
9.3 Detection of Determinism II: Distribution of Visible Ordinal Patterns 179
9.4 A Benchmark 181
9.5 Numerical Simulations 182
9.5.1 The Lorenz Map 183
9.5.2 The Delayed Hénon Map 185
10 Space--Time Dynamics 189
10.1 Spatially Extended Systems 189
10.1.1 Cellular Automata 190
10.1.2 Coupled Map Lattices 192
10.2 Applications of Permutation Complexity to Spatiotemporal Dynamics 194
10.2.1 Topological Entropy of CA 194
10.2.2 Complexity Classes of Elementary CA 198
10.2.3 Phases of CMLs 202
10.2.4 Spatiotemporal Regularity of CMLs 205
11 Conclusion and Outlook 207
A Mathematical Framework 210
A.1 Dynamical Systems 210
A.2 Shift Systems 217
A.3 Stochastic Processes and Sequence Spaces 222
B Entropy 224
B.1 Shannon Entropy 224
B.1.1 The Entropy of a Discrete Random Variable 224
B.1.2 The Entropy Rate of a Discrete-Time Finite-State Stochastic Process 228
B.2 Kolmogorov--Sinai Entropy 230
B.2.1 Deterministic Systems 230
B.2.2 Random Systems 234
B.3 Topological Entropy 237
B.3.1 Generalities 237
B.3.2 Topological Entropy of One-Dimensional Maps 242
References 246
Index 256

Produkt-Details

• Erscheint lt. Verlag: 20.3.2010
• Reihe/Serie: Springer Series in Synergetics
• Reihe/Serie: Springer Series in Synergetics
• Zusatzinfo: X, 280 p. 13 illus. in color.
• Verlagsort: Berlin
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik
• Themenwelt: Mathematik / Informatik ► Mathematik
• Themenwelt: Naturwissenschaften ► Physik / Astronomie ► Astronomie / Astrophysik
• Themenwelt: Naturwissenschaften ► Physik / Astronomie ► Theoretische Physik
• Themenwelt: Technik
• Schlagworte: discrete entropy • Dynamical Systems • Nonlinear Dynamics • ordinal patterns • permutation entropy • topological entropy
• ISBN-10: 3-642-04084-5 / 3642040845
• ISBN-13: 978-3-642-04084-9 / 9783642040849