Permutation Complexity in Dynamical Systems (eBook)

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