RANDOM SEQUENCES ACADEMISCH PROEFSCHRIFT TER VERKRIJGING VAN DE GRAAD VAN DOCTOR AAN DE UNIVERSITEIT VAN AMSTERDAM, OP GEZAG VAN DE RECTOR MAGNIFICUS, DR. S.K. THODEN VAN VELZEN, HOOGLERAAR IN DE FACULTEIT DER TANDHEELKUNDE, IN HET OPENBAAR TE VERDEDIGEN IN DE AULA DER UNIVERSITEIT (OUDE LUTHERSE KERK, SINGEL 411, HOEK SPUI) OP WOENSDAG 16 SEPTEMBER 1987 TE 13.30 UUR DOOR MICHIEL VAN LAMBALGEN GEBOREN TE KRIMPEN AAN DE IJSSEL 1 Promotores: Prof. Dr. J.F.A.K. van Benthem Prof. S.J. Doorman M.Sc. 2 Tout a dejà été éprouvé et expérimenté à mille réprises, mais souvent sans avoir été dit, ou sans que les paroles qui le disent subsistent, ou si elles le font, nous soient intelligibles et nous émeuvent encore. Comme les nuages dans le ciel vide, nous nous formons et nous dissipons sur ce fond d'oubli. Marguerite Yourcenar Archives du Nord 3 Preface The research on the foundations of probability reported here was part of project 22 – 110 of the Dutch Foundation for Scientific Research ZWO, whose support is gratefully ackowledged. Some of the central concerns of this essay took shape in a long afternoon stroll in Salzburg with Roger Cooke, who also intensely supervised their subsequent development. In spite of the heat generated by our debates, they have resulted in a state of low entropy in which few differences of opinion remain. I owe a special debt to Johan van Benthem, who steered me toward mathematical logic long ago. The example of his technical acumen and systematic philosophizing has inspired me ever since. His already overburdened schedule notwithstanding, he took over part of my teaching duties during the last phase of the writing. I am grateful to Joop Doorman, whose insistence on a philosophical justification of what was originally a collection of rather technical results, finally produced Chapter 2. Lastly, I thank Mike Keane and Guus Balkema for mathematical assistance. The cover was designed by Hans Sprangers. 4 Contents 1 Introduction 1 2 Roots of randomness: von Mises' definition of random sequences 6 2.1 Introduction 6 2.2 The frequency interpretation of probability 8 2.2.1 Methodological considerations 8 2.2.2 Kollektivs (informal exposition) 10 2.2.3 Strict frequentism: "Erst das Kollektiv, dann die Wahrscheinlichkeit" 11 2.2.4 Structure and task of probability theory 15 2.3 Axiomatising Kollektivs 16 2.3.1 The axioms 16 2.3.2 Some consequences of the axioms 19 2.3.3 Do Kollektivs exist? 21 2.4 The use of Kollektivs 24 2.4.1 The fundamental operations: definition and application 25 2.4.2 Necessity of Kollektivs 29 2.4.3 Strong limit laws 31 2.5 Making Kollektivs respectable: 1919 – 1940 33 2.5.1 Lawlike selections 33 2.5.2 The contextual solution 38 2.6 The Geneva conference: Fréchet's objections 41 2.6.1 Fréchet's philosophical position 41 2.6.2 Formal objections 43 2.6.2.1 Inconsistency 43 2.6.2.2 Ville's construction 43 2.7 Conclusions 51 Notes to Chapter 2 53 3 A new start: Martin-Löf's definition 55 3.1 Introduction 55 3.2 The definitions of Martin-Löf and Schnorr 57 3.2.1 Randomness via probabilistic laws 57 3.2.2 Recursive sequential tests 60 3.2.3 Total recursive sequential tests 61 3.2.4 An appraisal and some generalisations 65 3.3 Probabilistic laws 67 3.4 Martingales 70 3.5 Randomness via statistical tests 78 3.5.1 Types of statistical tests 78 3.5.2 Effective statistical tests 82 3.5.3 Discussion 83 3.6 Conclusion 85 Notes to Chapter 3 86 4 Place selections revisited 88 5 4.1 Introduction 88 4.2 Place selections from a modern perspective 89 4.3 Preliminaries 90 4.4 Effective Fubini theorems 92 4.5 Proof of the principle of homogeneity 99 4.6 New proof of a theorem of Ville 102 4.7 Digression: the difference between randomness and 2–randomness 113 Note to Chapter 4 114 5 Kolmogorov–complexity 115 5.1 Complexity of finite strings 116 5.1.1 Kolmogorov–complexity 116 5.1.2 Chaitin's modification 118 5.1.3 Conditional complexity 122 5.1.4 Information, coding, relative frequency 124 5.1.5 Discussion 127 5.1.6 Digression: resource–bounded complexity 128 5.2 Kolmogorov's program 128 5.3 Metamathematical considerations on randomness 131 5.3.1 Complexity and incompleteness 132 5.3.2 Discussion 135 5.4 Infinite sequences: randomness and oscillations 137 5.4.1 Randomness and complexity 138 5.4.2 Downward oscillations 139 5.4.3 Upward oscillations 142 5.4.4 Monotone complexity 144 5.5 Complexity and entropy 145 5.5.1 Dynamical systems 146 5.5.2 Metric entropy 146 5.5.3 Topological entropy 151 5.5.4 Kamae–entropy 156 5.6 Admissible place selections 157 5.6.1 Deterministic sequences 157 5.6.2 Admissibility and complexity 159 Notes to Chapter 5 160 6 Appendix: notation and definitions 162 6.1 Notation for sequences 162 6.2 Topology on 2w 162 6.3 Measures on 2w 162 6.4 Computability 163 6.5 Ergodic theory 164 References 166 Samenvatting (Dutch summary) 172 6 7 1 Introduction It may be taken for granted that any attempt at defining disorder in a formal way will lead to a contradiction. This does not mean that the notion of disorder is contradictory. It is so, however, as soon as I try to formalize it. Hans Freudenthal 0111000101001000....... is an initial segment of a long sequence produced by tossing a coin. In its broadest outline, the subject of this thesis is the mathematical description of the sequences produced by random processes (such as coin tossing), which will be called random sequences. The tantalizing motto, taken from Freudenthal [29], expresses a negative verdict on this enterprise. But meanwhile it raises a no less interesting question: How can a non- contradictory concept necessarily defy formalisation? Clearly, the two definite articles in the phrase "the mathematical description of the sequences produced by random processes" present a host of problems. There might not be such a description, as Freudenthal thinks; or it might be completely trivial, the reason being that all we can say a priori on the sequences produced by, say, coin tossing is, that these are sequences of zeros and ones. On the other hand, there do exist various definitions of random sequences; perhaps even too many. 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? Even apart from its usefulness, the possibility of providing a definition of randomness has often been doubted. Here is a grab-bag of some of the a priori reasons which have been adduced for this conviction: – As soon as you can define randomness, it ceases to be true randomness; –␣ Randomness is a property of processes, not of the sequences generated by such processes; – It is characteristic of a random process that it may generate any sequence. For the moment, we shall leave these a priori arguments unanalyzed. The first person to discuss systematically the possibility, and indeed the necessity, of a definition of random sequences was Richard von Mises, who provided an axiomatisation of probability theory with "random sequence" as a primitive term. He argued, as did later 8 Kolmogorov, that, if probability is interpreted as relative frequency, then the applicability of probability theory to real phenomena (which is amply verified) entails that these phenomena must have certain properties of randomness, and he proposed to take these properties as basic for a definition of random sequences (other properties being optional). A definition of randomness is therefore necessary to explain the applicability of probability theory and a minimal set of properties random sequences have to satisfy can be deduced from its rules, a priori reasons for the impossibility of such a definition notwithstanding. But in a philosophical analysis we must of course investigate the apparent conflict between compelling physical reasons pro and a priori reasons contra a mathematical definition of randomness. Although in the thirties, but also in recent years, there has been a lively commerce in definitions of randomness, our second question, namely: Do there exist criteria to choose between these definitions?, has not been explicitly discussed in the literature. To be sure, there have been discussions among partisans of various schools, the Geneva conference on the foundations of probability (1937) being a notable example. But one is struck by the sheer monotony of these discussions, the same arguments pro and con being repeated over and over again, without noticible effects upon the opinions of the discussants. We propose to break this stalemate by analyzing possible sources for the lack of mutual comprehension so clearly displayed. The conclusion of our analysis will be that von Mises, around whose axiomatisation of probability theory the discussion centered, had views on the foundations of probability and of mathematics in general, which were not shared, but also not fully understood, by his critics. His view on the foundations of mathematics, usually expressed only implicitly, was shaped by his work as an applied mathematician and is a mixture of constructivism and a tendency to introduce bold concepts whenever the description of real phenomena seems to necessitate it. From this mixture results what one might call an inhomogeneous mathematical universe, which is a far cry from the very homogeneous set theoretical universe that inspired some of the objections of his critics. Unfortunately, these assumptions were not made explicit in the debate. Von Mises' views on the foundations of probability did, of course, figure explicitly and prominently in the debate; but its critics did not show a reciprocal awareness of their own assumptions, thereby successfully creating the impression that, while von Mises' view was unnecessarily complicated, theirs was simplicity itself. We believe that this debate, if analyzed correctly, points to the conclusion that different (objective) interpretations of probability lead to different requirements for random sequences. Hopefully, this point of view is helpful in understanding the debate that raged between von Mises and his critics; and if it directs the reader away from bickering about definitions of randomness and toward the deeper questions of the foundations of probability, it has fulfilled its purpose. 9 These two main questions determine much of the technical work in Chapters 3 to 5. Given that there exist different types of definitions, each with its own minor variants, we must investigate how these definitions are related extensionally. Some of these relationships are well know, e.g. that between randomness in the sense of Martin-Löf and definitions involving (variants of) Kolmogorov complexity. In these cases, the novelty of our treatment consists solely in introducing new proof techniques. But other relations have been studied less thoroughly, notably that between von Mises' semi-formal definition, based on so called admissible place selections , and the other types. There are obvious reasons for this lack of attention. The fact that von Mises' definition is not quite formal renders a comparison with the other definitions, which are rigorous in the modern sense, difficult; and often the need for such a comparison is not felt acutely because, say, Martin-Löf's definition is considered to be an improvement on von Mises' proposal, rather than an alternative, based on radically different principles. We therefore have to study ways in which to make von Mises' definition precise; moreover, these attempts to instill precision should be based as much as possible upon his own philosophical premises. This problem has not been solved entirely, but the results that have been obtained, do enable us to effect a rigorous comparison between von Mises' definition and the other types. So far, we have been concerned with extensional relationships between different types of definitions. But the exact meaning and justification of the definitions is no less important. The rationale behind von Mises' definition is studied extensively in Chapter 2. It turns out that it is completely justified on von Mises' own interpretation of probability, to be called strict frequentism . His opponents, on the other hand, usually start from a very different interpretation of probability, the propensity interpretation, and it is this interpretation which inspires those modern definitions of randomness which, following Martin-Löf, characterise randomness as the satisfaction of certain statistical tests. The choice of the particular type of test employed by Martin-Löf is, in our opinion, debatable, and the conclusion of the discussion is, in a nutshell, that whereas von Mises' definition is philosophically rigorous, but technically less so, with Martin-Löf's definition it is just the other way around. The most promising approach to the characterisation of randomness appears to be the one inaugurated by Kolmogorov, using a notion of complexity for finite sequences. Philosophically, it stands midway between the definitions of von Mises and of Martin-Löf. Kolmogorov accepts von Mises' view that an analysis of the conditions of applicability of probability theory necessarily leads to the concept of a random sequence (although they differ in the place they allot to random sequences in the formal structure of probability theory). But while von Mises requires of random sequences only those properties which make the deductions of probability theory go through, Kolmogorov goes further and in a sense explains, 10