Random Sequences [PhD Thesis]

✍ Scribed by M. van Lambalgen

• Publisher: University of Amsterdam
• Year: 1987
• Tongue: English
• Leaves: 185
• Category: Library

✦ Synopsis

This is a PhD Thesis written by M. van Lambalgen under supervision of Prof. Dr. Johan van Benthem.

The discussion in the pages that follow is therefore concentrated on two main questions:

1. Is a mathematical definition of random sequences possible and if so, why should one want to give such a definition?

2. Given the fact that various definitions have been proposed, does it make sense to ask for criteria which allow us to choose between them?

✦ Table of Contents

M. van Lambalgen “Random Sequences” (PhD Thesis, 1987) ......Page 1
Preface ......Page 4
Contents ......Page 6
1 Introduction ......Page 8
2.1 Introduction ......Page 13
2.2.1 Methodological considerations ......Page 15
2.2.2 Kollektivs (informal exposition) ......Page 17
2.2.3 Strict frequentism: “Erst das Kollektiv, dann die Wahrscheinlichkeit” ......Page 18
2.2.4 Structure and task of probability theory ......Page 22
2.3.1 The axioms ......Page 23
2.3.2 Some consequences of the axioms ......Page 26
2.3.3 Do Kollektivs exist? ......Page 28
2.4 The use of Kollektivs ......Page 31
2.4.1 The fundamental operations: definition and application ......Page 32
2.4.2 Necessity of Kollektivs ......Page 36
2.4.3 Strong limit laws ......Page 38
2.5.1 Lawlike selections ......Page 40
2.5.2 The contextual solution ......Page 45
2.6.1 Fréchet’s philosophical position ......Page 48
2.6.2.2 Ville’s construction ......Page 50
2.7 Conclusions ......Page 58
Notes to Chapter 2 ......Page 60
3.1 Introduction ......Page 62
3.2.1 Randomness via probabilistic laws ......Page 64
3.2.2 Recursive sequential tests ......Page 67
3.2.3 Total recursive sequential tests ......Page 68
3.2.4 An appraisal and some generalisatins ......Page 72
3.3 Probabilistic laws ......Page 74
3.4 Martingales ......Page 77
3.5.1 Types of statistical tests ......Page 85
3.5.2 Effective statistical tests ......Page 89
3.5.3 Discussion ......Page 90
3.6 Conclusion ......Page 92
Notes to Chapter 3 ......Page 93
4.1 Introduction ......Page 95
4.2 Place selections from a modem perspective ......Page 96
4.3 Preliminaries ......Page 97
4.4 Effective Fubini theorems ......Page 99
4.5 Proof of the principle of homogeneity ......Page 106
4.6 New proof of a theorem of Ville ......Page 109
4.7 Digression: the difference between randomness and 2-randomness ......Page 120
Note to Chapter 4 ......Page 121
5 Kolmogorov complexity ......Page 122
5.1.1 Kolmogorov complexity ......Page 123
5.1.2 Chaitin’s modification ......Page 125
5.1.3 Conditional complexity ......Page 129
5.1.4 Information, coding, relative frequency ......Page 131
5.1.5 Discussion ......Page 134
5.2 Kolmogorov’s program ......Page 135
5.3 Metamathematical considerations on randomness ......Page 138
5.3.1 Complexity and incompleteness ......Page 139
5.3.2 Discussion ......Page 142
5.4 Infinite sequences: randomness and oscillations ......Page 144
5.4.1 Randomness and complexity ......Page 145
5.4.2 Downward oscillations ......Page 146
5.4.3 Upward oscillations ......Page 149
5.4.4 Monotone complexity ......Page 151
5.5 Complexity and entropy ......Page 152
5.5.2 Metric entropy ......Page 153
5.5.3 Topological entropy ......Page 158
5.5.4 Kamae entropy ......Page 163
5.6.1 Deterministic sequences ......Page 164
5.6.2 Admissibility and complexity ......Page 166
Notes to Chapter 5 ......Page 167
6.3 Measures on 2^ω ......Page 169
6.4 Computability ......Page 170
6.5 Ergodic theory ......Page 171
References ......Page 173
Samenvatting (Dutch summary) ......Page 179
Stellingen ......Page 182
Back cover ......Page 185