3. Seminar work-outs 4. Reports of meetings Texts which are out of print but still in demand may also be considered if they fall within these categories. The timeliness of a manuscript is more important than its form, which may be unfinished or tentative. Thus, in some instances, proofs may be merely outlined and results presented which have been or will later be published elsewhere. Publication of Lecture Notes is intended as a service to the international mathematical community, in that a commercial publisher, Springer-Verlag, can offer a wider distribution to documents which would otherwise have a restricted readership. Once published and copyrighted, they can be documented in the scientific literature. - Manuscripts Manuscripts are reproduced by a photographic process; they must therefore be typed with extreme care. Symbols not on the typewriter should be inserted by hand in indelible black ink. Corrections to the type-script should be made by sticking the amended text over the old one, or by obliterating errors with white correcting fluid. Should the text, or any part of it, have to be retyped, the author will be reimbursed upon publication of the volume. Authors receive 75 free copies. The typescript is reduced slightly in size during reproduction; best results will not be obtained unless the text on any one page is kept within the overall limit of 18 x26.5 cm (7 x 10 %2 inches). The publishers will be pleased to supply on request special stationery with the typing area outlined. Manuscripts submitted must amount to at least 100 pages. Manuscripts in English, German or French should be sent to Prof. Dr. A. Dold, Mathematisches Institut der Universität Heidelberg, Tiergartenstraße or Prof. Dr. B. Eckmann, Eidgenössische Technische Hochschule, Zürich. Lecture Notes in Physics Bisher erschienen/Already published Vol. 1: J. C. Erdmann, Wärmeleitung in Kristallen, theoretische Grund-lagen und fortgeschrittene experimentelle Methoden. II, 283 Seiten. 1969. DM 20,- Vol. 2: K. Hepp, Théorie de la renormalisation. Ill, 215 pages. 1969. DM 18,- Vol. 3: A. Martin, Scattering Theory: Unitarity, Analytic and Crossing. IV, 125 pages. 1969. DM 14,- Vol. 4: G. Ludwig, Deutung des Begriffs physikalische Theorie und axiomatische Grundlegung der Hilbertraumstruktur der Quantenmechanik durch Hauptsätze des Messens. XI, 469 Seiten.1970. DM 28,- Vol. 5: M. Schaaf, The Reduction of the Product of Two Irreducible Unitary Representations of the Proper Orthochronous Quantummechanical Poincaré Group. IV, 120 pages. 1970. DM 14,- Vol., 6: Bargmann. Representations in Mathematics and Physics. Edited by gmann. V, 340 pages. 1970. DM 24,- Vol. 7: R. Balescu, L. 1. Lebowitz, I. Prigogine, P. Résibois, Z. W. Salsburg, Lectures in Statistical Physics. V, 181 pages. 1971. DM 18,- Vol.8: Proceedings of the Second International Conference on Numerc Methods in Fluid Dynamics. Edited by M. Holt. IX, 462 pages. 1971. A collection of informal reports and seminars Edited by A. Dold, Heidelberg and B. Eckmann, Zürich 218 Claus Peter Schnorr Universität Saarbrücken, Saarbrücken/Deutschland Zufälligkeit und Wahrscheinlichkeit Eine algorithmische Begründung der Wahrscheinlichkeitstheorie Springer-Verlag Berlin - Heidelberg • New York AMS Subject Classifications (1970): 02E10, 02E15, 02F20, 60A05, 68A20 ISBN 3-540-05566-5 Springet Verlag Berlin • Heidelberg • New York ISBN 0-387-05566-5 Springer-Verlag New "York • Heidelberg • Berlin This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically those of translation, reprinting, re-use of illustrations, broadcasting, reproduction by photocopying machine or similar means, and storage in data banks. Under § 54 of the German Copyright Law where copies are made for other than private use, a fee is payable to the publisher, the amount of the fee to be determined by agreement with the publisher. © by Springer-Verlag Berlin Heidelberg 1971. Library of Congress Catalog Card Number 74-171873. Printed in Germany. Offsetdruck: Julius Beltz, Hemsbach/Bergstr. Inhaltsübersic'r1t Vorwort und Einleitung 1 Erstes Kapitel: Vorläufige Einführung des Kollektivs unter Berücksichtigung der historischen Entwicklung 4 1. Kritik der Map-Wahrscheinlichkeitstheorie 5 2. Der naive Begriff des Kollektivs nach VON MISES 10 3. Erste Ansätze zur widerspruchsfreien Definition der Kollektive und ihre Kritik durch VILLE . . . . 21 Zweites Kapitel: Eine Obermenge der statistischen Zufallsgesetze (Zufallsfolgen im Sinne von MARTIN- LÖF) 29 4. Hyperzufällige Folgen 32 5. Hyperzufällige Folgen und das Prinzip vom aus-geschlossenen Spielsystem 38 6. Charakterisierung hyperzufälliger Folgen durch Invarianzeigenschaften 45 7. Weitere Einwände gegen den Begriff der Zufalls-folge im Sinne von MARTIN-LOF 52 Drittes Kapitel: Die statistischen Zufallsgesetze (Endgültige Definition der zufälligen Folgen) 60 8. Charakterisierung der Zufallsfolgen durch konstruktive Nullmengen nach L.E.J. BROUWER 63 9. Charakterisierung von Zufallsfolgen durch das Prinzip vom ausgeschlossenen Spielsystem 70 10. Darstellung des starken Gesetzes der großen Zahlen durch Martingale • • • • • • 78 11. Invarianzeigenschaften von Zufallsfolgen 83 12. Charakterisierung der Zufallsfolgen durch Invarianzeigenschaften 89 13. Einige modifizierte Spielsysteme 92 14. Zufallsfolgen als optimale Folgen für die Bank 98 15. Die Programmkomplexität nach KOLMOGOROFF 107 lY Viertes Kapitel: Klassifikation der Zufallsgesetze nach ihrer Ordnung und ihrer algorithmischen Komplexität (Theorie der Pseudozufallsfol- gen) 120 16. Die Ordnung eines Zufallsgesetzes 123 17. Zufallsgesetze von exponentieller Ordnung , 129 18. Voraussagbare und quasi-rekursive Folgen 140 19. Durch endliche Automaten darstellbare Zufallsgesetze 146 20. Raum- und Zeitkomplexität rekursiver Funktionen 150 21. Die Komplexität von Zufallsgesetzen und der Zufallsgrad von Folgen 159 22. Invarianzeigenschaften der Komplexitäteklassen von Pseudozufallsfolgen 169 Fünftes Kapitel: Zufallsfolgen zu allgemeinen Wahrscheinlichkeitsräumen 173 23. Berechenbare Wahrscheinlichkeitsmaße auf {0,1} 173 24. Verteilungsunabhängige Sequentialtests 176 25. Verteilungsunabhängige Invarianzeigenschaften von Zufallsfolgen 183 26. Zufallsfolgen zu Wahrscheinlichkeitsmaßen auf R 192 I Anhang über rekursive Funktionen 200 II Bezeichnungen und Abkürzungen 202 III Stichwortverzeichnis 205 IV Literaturverzeichnis 209 Zufälligkeit und Wahrscheinlichkeit (Ein Ansatz zur Neubegründung der Wahrscheinlichkeitstheorie.) Vorwort und Einleitung Die Problematik um den Begriff der Zufallsfolge war, nachdem erste Ansätze u.a. von VON MISES, TORNIER, WALD, CHURCH und VILLE nicht zum Ziel führten, fast in Vergessenheit geraten. Erst nachdem die logischen Begriffe der Rekursivität bzw. der Berechenbarkeit Eingang in weite Kreise von Mathematikern gefunden hatten, wurde das Interesse in jüngster Zeit, angeregt durch neue Ansätze, wieder wach. Die Bedeutung der vorliegenden Theorie liegt sicher darin, daß sie Hinweise zur Konstruktion von Pseudozufallsfolgen und somit zur Simulation von Zufallsprozessen gibt. Es ist zu hoffen, daß damit der Schlüssel gefunden ist, die noch nicht präzisierten Monte-Carlo-Methoden mathematisch exakt zu behandeln. Verlockend an dieser Theorie ist aber auch die Brücke, welche zwischen der klassischen Wahrscheinlichkeitstheorie und der mathematischen Logik geschlagen wird, die notwendigerweise zur Verknüpfung von statistischen und algorithmischen Argumenten führt. Diese Notwendigkeit, verschiedene Denkweisen miteinander zu verbinden, bereitete aber anfänglich große Schwierigkeiten. Spätestens nach den Arbeiten von VILLE [49] (1939) und CHURCH [6] (1941) waren einerseits die wahrscheinlichkeitstheoretischen, andererseits die logischen Grundlagen zur endgültigen Klärung des Begriffes der Zufallsfolge gegeben. Denn die VILLE'sche Formulierung des Prinzips vom ausgeschlossenen Spielsystem, welche durch Martingale ausgedrückt wird, führt, wenn man noch in geeigneter Weise konstruktivisiert, zu diesem Be-griff. Es ist daher erstaunlich, daß dieser - so gesehen - relativ kleine Schritt erst dreißig Jahre später in SCHNORR [40] erfolgte. Dieser letzten Arbeit gingen Artikel von KOLMOGOROFF [21], CHAITIN [4] und MARTIN-LÖF [27] voraus, welche aufbauend auf der algorithmischen Denkweise unter Benutzung des Konzepts der Kompliziertheit von Rechenprozessen scheinbar völlig neue Vorstellungen von regellosen Folgen eröffneten. Diese Artikel lassen zunächst keinen formalen Zusammenhang mit den eingangs genannten Arbeiten erkennen. Es ist das Ziel dieses Buches, diese Zusammenhänge zwischen den verschiedenen Zugängen zum Begriff der Zufälligkeit herauszuarbeiten. Es zeigt sich, daß die VON MISES'sche Idee der Invarianzeigenschaften (in der Form von Auswahlregeln), das Prinzip vom ausgeschlossenen Spielsystem sowie die Gedanken von L.E.J. BROUWER zu einer konstruktiven Maßtheorie jeweils zu äquivalenten Definitionen der Zufälligkeit führen. Es erschien mir sinnvoll, in Kapitel I den historischen Ausgangspunkt kurz zu erläutern. In Kapitel II wird die Definition der Zufalls-folgen nach MARTIN-LÖF behandelt. Es werden weitere äquivalente Darstellungen dieses Zufallsbegriffes angegeben, um die hierin zugrunde gelegte Willkür sichtbar zu machen. In den Kapiteln III und IV, dem Kernstück des Buches, findet sich nicht nur eine zusammenfassende Darstellung meiner früheren Arbeiten, sondern auch eine Reihe noch nicht veröffentlichter Resultate. Z.B. wird durch die Sätze (15.9) und (15.10) eine noch nicht bekannte Charakterisierung der zufälligen Folgen durch ihre Programmkomplexität gegeben. Durch Satz (17.8) wird der VON MISES'sche Ansatz in der CHURCH'schen Fassung harmonisch in die Theorie eingebettet. In Paragraph 24 werden Zufallsfolgen durch verteilungsunabhängige Invarianzeigenschaften (in Analogie zu den VON MISES'schen Auswahlregeln) beschrieben. Dem vorliegenden Buch ging eine Vorlesung voraus, die ich im Sommer 1970 an der Universität Saarbrücken gehalten habe. Das Buch istinsofern unvollständig, als im wesentlichen nur binäre Zufallsfolgen behandelt werden. Denn ein vollständiger Aufbau der klassischen Wahrscheinlichkeitstheorie ist im Rahmen einer konstruktiven Maßtheorie ohne weiteres möglich, Dies wird in Paragraph 26 angedeutet. Eine ausführliche Darstellung der konstruktiven Maßtheorie würde jedoch den Rahmen dieser Abhandlung sprengen. Ich danke allen, welche durch wertvolle Ratschläge und durch ihr Interesse die Arbeit an diesem Buch vorangetrieben haben. Insbesondere danke ich den Herren H. Stimm, P. Krebs und P. Fuchs für das Durchlesen der Korrekturen und vor allem Fräulein Wagner für das sorgfältige Tippen des Manuskripts. C.P. Schnorr Saarbrücken, Juni 1971 Erstes Kapitel Vorläufige Einführung des Kollektivs unter Berücksichtigung der historischen Entwicklung In Paragraph 1 legen wir dar, daß auch vom Standpunkt der heute fib-lichen Maß-Wahrscheinlichkeitstheorie eine Präzisierung des Begriffs der Zufallsfolge wünschenswert ist. Diese ist notwendig, wenn man die wohlbekannte Schwierigkeit überwinden will, den maßtheoretischen Wahrscheinlichkeitsbegriff physikalisch zu interpretieren. Andererseits kann man erwarten, daß auf der Grundlage der Zufälligkeit auch bisher nicht behandelte Problemstellungen wie die Simulation von Zufallsprozessen in den Rahmen der Wahrscheinlichkeitstheorie einbezogen werden können. In Paragraph 2 behandeln wir den historischen Ansatz zur Präzisierung der Kollektive, wie ihn VON MISES 1919 entwarf. Wir gehen kurz auf die Vorstellungen ein, die diesem Konzept zugrunde liegen, und zeigen die wesentlichen Probleme auf, welche durch diesen Ansatz aufgeworfen werden. An diesen offenen Fragen orientierte sich dann die weitere Entwicklung in den 30-er Jahren, deren wichtigste Züge wir in Para-graph 3 schildern. Sie ist dadurch gekennzeichnet,daß durch die Ergebnisse vor allem von WALD zwar eine widerspruchsfreie Fassung des Kollektivbegriffs gelang, jedoch stellte VILLE im Jahre 1937 durch seine Kritik den VON MISES'schen Zugang zum Begriff der Zufallsfolge noch ein-mal grundsätzlich in Frage. - 5 - 1. Kritik der Maß-Wahrscheinlichkeitstheorie Wir wollen hier kurz erläutern, inwieweit die klassische Maß-Wahrscheinlichkeitstheorie unbefriedigend ist. Der Leser, dem die mit der Interpretation des Begriffs der Wahrscheinlichkeit zusammenhängende Problematik bekannt ist, kann diesen Paragraphen überschlagen. Wir geben kurz die übliche axiomatische Grundlegung der Wahrscheinlichkeitstheorie an. Definition (1.1) Ein Wahrscheinlichkeitsraum ist nach KOLMOGOROFF [20] ein Tripel 0 = (X,3,4) mit folgenden Eigenschaften: (1) X ist eine Menge, der Stichprobenraum. (2) 3 ist eine a-Algebra von Teilmengen von X, welche die leere Menge 0 enthält. Die Elemente von 3 heißen Ereignisse oder meßbare Mengen. 3 ist also ein System von Teilmengen von X, so daß mit A und B auch die Vereinigung A UB, der Durchschnitt A033 und die Komplemente Ao, Bc in 3 liegen. Mit einer Folge (AiJ iEN) mit AiE F liegt auch iéN Ai in 3. (3) 4:3 - R ist ein nicht negatives, a-additives, normiertes Maß. Da-bei ist R die Menge der reellen Zahlen. D.h., für die Funktion 4:3 R gilt u(A) z 0(A e3), ferner u(X) = 1 und µ(ieN Ai) = 1 u(A.) sofern Aie3 und Ain A. = 0 (i4j). iaN µ(A) heißt die Wahrscheinlichkeit von A. µ heißt ein Wahrscheinlichkeitsmaß, oder kurz Verteilung. Im folgenden nehmen wir stets an, daß µ zusätzlich ein Lebesguemaß ist. D.h., aus A E.3 mit µ(A) = o und BcA folgt stets B e3 und somit µ(B) = o. Bekanntlich läßt sich jedes Wahrscheinlichkeitsmaß zu einem Lebesguemaß erweitern. Das obige Axiomensystem wurde 1933 von KOLMOGOROFF vorgeschlagen und hat sich nicht zuletzt wegen seiner syntaktischen Einfachheit ge- A - 6 - - 7 - genüber anderen Vorstellungen durchgesetzt. Inhaltlich jedoch sind diese Axiome wohl weniger einfach. Die Wahrscheinlichkeit µ(A) be-deutet soviel wie den Grad der Gewißheit des Ereignisses A. Dieser Grad der Gewißheit eines Ereignisses wird als eine jedem Ereignis zukommende Grundeigenschaft aufgefaßt, ähnlich dem Gewicht, der Ausdehnung und der Farbe von Körpern. Man wird sicherlich zugeben, daß der Grad der Gewißheit, sofern er sich nicht durch einfachere Begriffe erläutern Läßt, nicht sehr anschaulich ist. Z.B. ist unklar, was der Grad der Gewißheit 1/2 für ein einmaliges Ereignis bedeutet. Die Interpretation des Wahrscheinlichkeitsbegriffes, so argumentiert man, liegt eben außerhalb der mathematischen Aufgabenstellung. Dennoch legt man implizit meist die Vorstellung zugrunde, daß Ereignisse mit einem hohen Grad der-Gewißheit häufig auftreten, während solche mit einem kleinen Grad der Gewißheit recht selten sind. Diese mehr anschauliche Interpretation der Wahrscheinlichkeit kommt aber in den Kolmogoroff'schen Axiomen nicht zum Ausdruck. Sie kann daher auch nicht aus ihnen abgeleitet werden. Um dies zu erläutern, diskutieren wir kurz das starke Gesetz der großen Zshlen.Hierzu benötigen wir den Begriff des Produktraumes 5. Zu einem Wahrscheinlichkeitsraum ( = (X,3,4) definiert man in kanonischer Weise den (abzählbar unendlichen) Produktraum C1 = Dabei ist X''' die Menge der abzählbar unendlichen Folgen über X. Für z a X~ schreiben wir z = z1z2...z.... mit zie X. Mit X* bezeichnen wir die Menge aller endlichen Folgen mit Elementen aus X. AeX*,sei die leere Folge. Die Aneinanderreihung einer Folge x e X* und y e X*ur wird als Produkt xy geschrieben. Dies impliziert in natürlicher Weise ein Produkt ABcr von Mengen AcX* und Bcr. Die c-Algebra 3 von 5 und das Maß werden folgendermaßen defi- niert. Zu einer Menge A c 3* (damit gilt A c X*) bezeichnet [Al = AXE def die von A erzeugte Zylindermenge. wird auf den Zylindermengen de-finiert durch n [x1x2...xn] = II µ(xi) (x1x2...xn E3*) i=1 und die Forderung der c-Additivität. Die Gesamtheit der von den end-lichen Mengen A3.* erzeugten Zylindermengen 8 = { [A]cf 1 A endliche Teilmenge von 3* } def bildet eine Mengenalgebra und ist c-additiv auf $. Damit läßt sich 1 auf eindeutige Weise zu einem Lebesguemaß er-weitern. Eine Menge CcX's heiße meßbar bzgl. µ, wenn es Folgen (Aili EN) von endlichen Mengen Ai 3* und (B1~i e N) mit Bi 3* gibt, so daß für alle i EN: CU[Ai] - Cf[Ai] c [Bi], µCBi] 5 2-i. In diesem Falle existiert lim µ[Ai] und ist von der Wahl der Folgen Ai und Bi unabhängig. Diesen Grenzwert definiert man als das Maß µ(C) von C. Die meßbaren Mengen bilden dann eine c-Algebra 3 und ist c-additiv auf 5. Damit ist der Produktraum 5 = (X,3,µ) beschrie-ben. Zu AcX bezeichne im folgenden XA X [0, 1) die charakteristische Funktion von A. Die partielle Funktion H : 3 x -*R werde definiert durch n lim n -l E XA(zi), falls dieser Grenzwert existiert n i=1 sonst sei H(A,z) undefiniert. H(A,z) _ - 8 - - 9 - Das starke Gesetz der großen Zahlen besagt nun, daß µ {zee'IH(A,z) = µ(A)}= 1 für alle A e3. Inhaltlich sagt dieses Gesetz folgendes aus. Die relative Häufigkeit, mit der die Glieder zi einer unendlichen Folge z in der Menge A liegen, konvergiert mit dem Grad der Gewißheit 1 gegen die Wahrscheinlichkeit µ(A) von A. Man sagt hierzu, daß die Relation H(A,z) = µ(A) für fast alle zE Xm erfüllt ist. Diese Sprechweise ist suggestiv und erweckt den Eindruck, daß die Menge der Folgen, welche obige Relation erfüllen, groß gegenüber ihrem Komplement ist. Diese Aussage Läßt sich aber nicht mathematisch präzisieren, denn beide Mengen haben i.a. die-gleiche Mächtigkeit. Der Grad der Gewißheit 1 der Menge {z e rIH(A,z) = µ(A)} bezieht sich nur auf das Produktmaß zu µ. Er nimmt für andere Maße auch den Wert 0 an. Dies alles zeigt, daß sich eine tieferliegende und einsichtigere Interpretation des Grades der Gewißheit aus den KoLmogoroff'schen Axiomen nicht ableiten läßt. Dennoch ist es wünschenswert, sich um eine weitergehende Klärung der Wahrscheinlichkeitsgesetze zu bemühen. Dieses bessere Verständnis der Natur der Wahrscheinlichkeit kann nicht durch neue Erkenntnisse und Sätze innerhalb der klassischen Wahrscheinlichkeitstheorie selbst gewonnen werden. Dies ist nur möglich, indem man den Grad der Gewißheit nicht mehr axiomatisch beschreibt und der Theorie voranstellt, sondern indem man ihn aus einem neuen tieferliegenden und unserer Anschauung besser zugänglichen Grundbegriff ableitet. Dieser neue fundamentale Begriff sind Zufallsfolgen von Ereignissen. Von diesen Zufallsfolgen hat man im Gegensatz zum Grad der Gewißheit eine konkrete Vorstellung, denn uns sind aus der Natur physikalische Phänomene bekannt, von denen wir zumindest annehmen, daß es Zufallsprozesse sind. Hat man einmal den Begriff der Zufallsfolge geklärt, dann kann man die Wahrscheinlichkeit eines Ereignisses definieren als den Grenzwert der relativen Häufigkeit, mit der dieses Ereignis in der Zufallsfolge auftritt. Dieser Begriff der Wahrscheinlichkeit hat dann eine wohl präzisierte physikalische Interpretation. Wir werden zeigen, daß man auf diese Weise zu einer Theorie kommt, die die klassische Wahrscheinlichkeitstheorie inhaltlich (dagegen nicht formal) enthält, in der sich aber darüber hinaus auch wichtige Fragestellungen behandeln lassen, die der klassischen Theorie nicht zugänglich sind. Hierunter fällt insbesondere die Simulation von Z_,fallsprozessen. Der so erzielte Fortschritt in der Wahrscheinlichtkeitstheorie kommt darin zum Ausdruck, daß ein Teil der bisher auermathematischen Problematik des Wahrscheinlichkeitsbegriffes den exakten Methoden der Mathematik zugeführt wird. Dieser Fortschritt wird dadurch er-kauft, daß der Weg zur formalen Definition der Wahrscheinlichkeit länger und steiniger wird. Der neue Grundbegriff der Zufallsfolge muß zu-nächst gut fundiert und in seiner Bedeutung geklärt werden. Wir werden viel Mühe darauf verwenden zu zeigen, daß es sich hier um einen wirklich fundamentalen, mathematischen Begriff handelt. -1o- - 11 - 2. Der naive Begriff des Kollektivs nach VON MISES Der im folgenden behandelte naive Begriff des Kollektivs (Zufalls-folge) wurde von VON MISES in seinen Grundzügen bereits um 1919 entwickelt. Ähnlich wie die naive Mengenlehre enthält er einen trivialen Widerspruch. Trotzdem wollen wir hier auf diesen Begriff eingehen, weil er einen wesentlichen Teil unserer Grundkonzeption in einfacher Weise wiedergibt. Als VON MISES seinen Ansatz zur Grundlegung der Wahrscheinlichkeitstheorie vorlegte, mußte er zwischen zwei grundsätzlich verschiedenen Auffassungen von Wahrscheinlichkeit unterscheiden. Unter den Phänomenen, die landläufig mit der Vokabel Wahrscheinlichkeit bedacht werden, kristallisieren sich zwei große Kreise heraus. (1) Die subjektive Wahrscheinlichkeit Beispiele: die Wahrscheinlichkeit von Zeugenaussagen und gesetzlichen Urteilen. Die Wahrscheinlichkeit für die Existenz von Menschen außerhalb der Erde. Die Wahrscheinlichkeit für die Landung Cäsars in England. Als charakteristische Eigenschaften dieser Beispiele kann man folgendes nennen. Das betrachtete Ereignis (Tatbestand) ist von seiner Natur aus einmalig und mit anderen Ereignissen (Tatbeständen) unvergleichbar. Es ist nicht gedacht, daß die betreffende Wahrscheinlichkeit 1 oder 0 ist, je nachdem, ob der Tatbestand richtig ist oder nicht. Die Wahrscheinlichkeit hängt vielmehr von der individuellen Betrachtungsweise ab. Man kann sie nicht objektiv messen. (2) Wahrscheinlichkeit als relative Häufigkeit von Ma.ssenerscheinun Beispiele: Das Auftreten einer Kombination beim Würfeln. Die Häufigkeit von Todes- (Krankheits-) fällen in großen Gruppen von Menschen. Physikalische Massenerscheinungen, wie z.B. das Verhalten von Atomen, Molekülen. Atomare Prozesse. Wir werden uns nur mit dem zweiten Typ von Wahrscheinlichkeit beschäftigen. Gemeinsam an diesen Beispielen ist, daß sie sich auf unbegrenzt wiederholbare gleichartige (oder ähnliche) Massenerscheinungen beziehen. Daher nennen wir diese noch mathematisch zu charakterisierenden Erscheinungen Kollektive. Z.B. läßt sich der Wurf mit einem Paar guter Würfel praktisch fast unbegrenzt wiederholen, wenn man davon absieht, daß sich die Würfel allmählich abnutzen. Den Versicherungen steht ein Heer von Versicherungsnehmern zur Verfügung, um die Todes- (Krankheits-) rate abzuschätzen. Bei den chemischen (atomaren) Prozessen wirkt eine unermeßliche Zahl gleichartiger Moleküle (Elementarteilchen) mit. Um die genannten Erscheinungen näher zu untersuchen, betrachten wir ein besonders charakteristisches Beispiel, den Münzwurf. Dabei identifizieren wir Kopf mit 1 und Zahl mit O. Was beinhaltet nun unsere Vorstellung, daß 0 und 1 die Wahrscheinlichkeit 1/2 haben? Es ist eine Erfahrungstatsache, daß bei vielen langen Wurffolgen die relative Häufigkeit von 0 und 1 im allgemeinen nahe bei 1/2 liegt. Andererseits weiß man, daß immer wieder Teilfolgen auftreten, die überwiegend aus Einsen (bzw. Nullen) bestehen. Die Situation ändert sich, wenn man nicht mehr viele, Lange Wurfserien betrachtet, sondern wenn man eine einzige Wurfserie unbegrenzt fortführt. Hier lehrt die Erfahrung, daß in einer solchen unendlichen, binären Folge z = z1z2...zn... die man durch fortgesetztes Werfen einer Münze erhält, die relative n Häufigkeit n 21 z. des Auftretens der 1 sich allmählich gegen 1/2 i=1 stabilisiert. Die Differenz n In-1 2 z. - 1/21 i=1 1 wird mit wachsendem n beliebig klein. Es ist ein eindrucksvolles Spiel, diese vielfach belegte Erfahrungstatsache nachzuvollziehen. en VON MISES faßte dieses Phänomen in einer seiner Grundannahmen zusammen: (1) Für eine unendliche Wurffolge z e{0,1}°° gilt: Tatsächlich läßt sich die Annahme der Konvergenz der relativen Häufigkeit empirisch nicht vollständig belegen. Denn wir verfügen stets nur über endliche, wenn auch sehr lange Wurfserien. Aber unsere Erfahrung mit fortgesetzten Wurffolgen legt die Vermutung der Konvergenz nahe. So spricht z.B. die Erfahrung der Spielbanken und Lotterieunter-nehmen in nicht geringem Maße für die Annahme stabiler Werte der relativen Häufigkeiten. Die Spielbanken in Monte Carlo und anderenorts führen in millionenfacher Wiederholung dasselbe Spiel immer wieder aus. Sie berechnen ihre Gewinnaussichten aufgrund der Annahme fester Grenzwerte der relativen Häufigkeiten und fühlen sich sehr wohl dabei. Daß gelegentlich eine Bank gesprengt wird, spricht nicht gegen diese Voraussetzung. Wichtig ist nur, daß sich nach aller Erfahrung der Gesamtgewinn seit Bestehen der Bank in der erwarteten Größenordnung hält. Kein vernünftiger Mensch wurde ohne diese Annahme eine Spiel-bank betreiben.ge erraten. Wie aber soll nun die innere Unregelmäßigkeit der Wurffolgen er-faßt werden? VON MISES hatte hierzu folgende Idee. Er wollte die Regellosigkeit einer Folge dadurch sichern, daß er den Ausschluß eines auf die Dauer Gewinn bringenden Spielsystems forderte. Was stellte sich VON MISES unter einem Spielsystem vor? VON MISES faßte im wesentlichen den Fall ins Auge, daß ein Spieler auf systematische Weise eine unendliche Teilfolge einer Zufallsfolge bildet. VON MISES forderte, daß in einer solchen Teilfolge 0 und 1 wieder die relative Grenzhäufigkeit 1/2 haben. Interpretiert man z.B. 1 als Treffer und 0 als Niete, so bedeutet dies, daß ein Spieler durch systematische Auswahl der Spielgänge, an denen er sich beteiligt, die relative Häufigkeit seiner Treffer und Nieten nicht verändern kann. Wir kommen nun zur Formulierung der Auswahlregeln. Im folgenden sei X eine beliebige Menge. X*(Xc°) sei die Menge aller endlichen (unendlichen) Folgen über X, AeX* sei die leere Folge. Zu z 6X'' bezeichne z(n) die Anfangsfolge der Länge n. Definition (2.1) Unter einer Auswahlregel (bzgl. X) verstehen wir eine Abbildung p: X* {0,1). n Lim n -l 2= z. = 1/2. n i=1 i ordnen wir in eindeutiger Weise eine Abbil- Es ist leicht einzusehen, daß feste relative Grenzhäufigkeiten Einer Auswahlregel allein noch nicht unserer Vorstellung von unendlichen Wurffolgen ent- dung X* 0: X* sprechen. Z.B. schließt es unsere Erfahrung aus, daß eine periodische zu durch Folge, etwa 1010101010 1010.... als Wurffolge auftritt. Es ist ihre innere Regelmäßigkeit, die unserer Vorstellung von Zufallsfolgen widerspricht. Eine solche Struktur einer Wurffolge würde ein fortgesetztes Wettspiel über die i-te Komponente der Folge sinnlos erscheinen Lassen. Denn nach einer gewissen Anzahl von Würfen wird ein Spieler sicher das Bildungsgesetz der Fol- 0(xa) = j 0(x)a p(x) = 1, ` 0(x) P(x) = O. für alle x E X*, a E X. * - 4 - - 7 - Weiter ordnen wir einer Auswahlregel m eine partielle Funktion x- wie folgt zu. Der Definitionsbereich D(0- ) sei gegeben durch D(4) = fz E 7 I4(z(n))I ist unbeschränkt mit n}. wird wie folgt definiert: 0- (z) E 4(z(n))r (z ED(4),nE N). Nun können wir den Begriff des Kollektivs, so wie er VON MISES vorschwebte, formulieren. Es sei jedoch darauf hingewiesen, daß es bis auf triviale Fälle solche Kollektive überhaupt nicht gibt. XA bezeichne weiterhin die charakteristische Funktion zu einer Menge AcX. Definition (2.2) Ein Kollektiv über X ist eine Folge z EX , für die es eine Abbildung 2X -• R gibt, so dap für alle AcX und für alle Auswahlregeln X* -• (0,1} mit zE D(4) folgendes gilt: n -1 E 'Lim n XA$(z)~ = µ(A)• n i=1 µ(A) heißt dann die Wahrscheinlichkeit von A bezüglich des Kollektivs z. Diese Forderung besagt, da.ß die relative Häufigkeit, mit der die Glieder von 0(z) in A liegen, stets existiert und gleich µ(A) ist, sofern nur 0(z) erklärt ist. Diese Definition der Wahrscheinlichkeit hat den Vorzug der Anschaulichkeit. Einige formale Eigenschaften des Wahrscheinlichkeitskalküls lassen sich auf dieser Basis anschaulich begründen. Es folgt unmittelbar das Korollar (2.3) Ist z ein Kollektiv über X, dann ist die zugehörige Funktion µ a.dditiv, nicht negativ und es gilt µ ;X) = 1. Für endliche X ist µ somit eine Verteilung. Im folgenden betrachten. wir nur Kollektive zu einer Verteilung µ. Ein erster Widerspruch im Kollektivbegriff offenbart sich in dem Lemma (2.4) Gibt es zu einer Verteilung µ ein x E X mit 0 < µ(x) < 1, dann gibt es kein Kollektiv zu µ. Beweis: Angenommen zE X* sei ein Kollektiv zu µ. Wegen µ(x) > 0 enthalt z unendlich oft die Komponente x. Dann gibt es eine Auswahlregel. q): X* ~ f0,1}, die aus z genau die Komponenten x auswählt. Es gilt also if)(z) = xxx....x Wegen µ(x) < 1 kann z kein Kollektiv zu µ sein. Unabhängig von dem obigen Widerspruch gibt es noch weitere prinzipielle Schwierigkeiten im Zusammenhang mit dem Konzept der relativen Häufigkeit, wenn man unendliche Mengen X betrachtet. Ist X abzählbar unendlich, so muß man die a-Additivität des wie in (2.2) definierten µ zusätzlich fordern, weil sie i.a. nicht gesichert ist. Ferner gilt für überabzählbare X das Lemma (2.5) Sei c= (X,ü,p) ein Wahrscheinlichkeitsraum mit µ(x) = 0 für alle n x E X . Dann gibt es keine Folge zE X mit lim n 1 xA(zi) n i=1 für alle A E S. Beweis: Angenommen es gäbe ein z mit obiger Eigenschaft. Setze A = f z i l i E N}. Dann ist A E 3, denn 3 ist eine a-Algebra. Weil p a-additiv ist, gilt µ(A) = O. Nach Konstruktion gilt aber n lim n 1 XA(zi) = 1 im Widerspruch zu µ(A) = O. n i=1 Will man am Konzept der relativen Häufigkeit festhalten, so folgt aus obigem Lemma, daß man den Begriff des Wahrscheinlichkeitsraumes i.a. abschwächen muß. Da man auf die o-Additivität von p nicht verzichten will, suchte man das Mengensystem 3 einzuschränken. Lange X°° Z - 16 - Zeit glaubte man, daß nur den JORDAN-PEANO meßbaren Mengen eine Wahrscheinlichkeit i.S. der relativen Häufigkeit zukomme. Dies sind diejenigen meßbaren Mengen (Ereignisse), deren Rand (bei einer vorgegebenen Topologie) das Maß 0 hat. Die Meinung, daß nur den JORDANPEANO meßbaren Mengen eine Wahrscheinlichkeit als relative Grenzhäufigkeit zukomme, wurde von TORNIER [48 ] vertreten und von VILLE [49 ] und WALD [51 ] übernommen. Dies wurde aber bedeuten, daß ein großer Teil der Maß-Wahrscheinlichkeitstheorie nicht in die Häufigkeitstheorie eingegliedert werden kann. Eine unserer Hauptaufgaben wird es sein, diese scheinbar grundsätzlichen Schwierigkeiten zu überwinden. Ungeachtet der obigen Widersprüche eignen sich die Kollektive gut dazu, einige Rechenregeln und Begriffe der Wahrscheinlichkeitstheorie anschaulich zu interpretieren, so z.B. die Additionsregel, die Produktregel und die bedingten Wahrscheinlichkeiten. Die zugehörigen Operationen an Kollektiven nannte VON MISES die Mischung, die Verbindung und die Teilung. VON MISES war der Ansicht, daß die Hauptaufgabe der Wahrscheinlichkeitstheorie darin besteht, solche Operationen zu untersuchen, die aus gegebenen Kollektiven neue erzeugen, und dann die Verteilung dieser abgeleiteten Kollektive zu bestimmen. I. Die Mischung Eine Abbildung g: X - Y läßt sich in eindeutiger Weise fortsetzen zu einer Abbildung . g: X ~ YW durch g(z)i = g(zi) (i E N, z er). Sei z6X''e ein Kollektiv zur Verteilung ein neues Kollektiv ist. Die zugehörige neue Verteilung µ': 2Y R ergibt sich durch µ'(A) = µ g-1(A). def - 17 - Diese Regel nennt man die Additionsregel für Wahrscheinlichkeiten. Man sagt g(z) geht durch Mischung aus z hervor, denn man hat in X Elemente (Merkmale) zu Klassen zusammengefaßt. Als Beispiel betrachten wir das Würfeln. Es ist dann X = {1,2,...,6}mit µ(i) = 6-1,i = 1,...,6. Sei g: X (gerade, ungerade) die Funktion mit g(1) = g(3) = g(5) = ungerade, g(2) = g(4) = g(6) = gerade. Es ergibt sich also z.B. als Wahrscheinlichkeit für gerade: µ'(gerade) = 4(2) + 4(4) + 4(6) = 1/2. II. Die Verbindung Sei Xn die Menge aller n-Tupel über X. Dann werde die bijektive Abbildung nn: X (X )-definiert durch (nn(z))k = (zk•n+1' zk•n+2' ••'' zk•n+n)' Ist z EXm ein Kollektiv zur Verteilung µ, dann ist nn(z) E(X) ein neues Kollektiv. Die zugehörige Verteilung µ' ergibt sich durch n µ'(a1, .... an) = II µ(ai) i=1 für alle (a„ ... , a,) E Xn. Dies ist die sogenannte Produktregel. Als Beispiel betrachten wir wieder das Würfeln. Es sei die Wahrscheinlichkeit zu berechnen, mit der bei gleichzeitigem Werfen drei-er idealer Würfel die Kombination (3,2,1) auftritt. Nach der Produktregel gilt für die Wahrscheinlichkeit, daß der erste Würfel 3, der zweite 2 und der dritte Würfel 1 zeigt: = 4(3) • µ(2) • µ(1) = 6-3. Daraus folgt: dann folgt, daß g (z) EYm µ, - 18 - 4'(3,2,1) = 4(3,2,1) + 4(2,1,3) + 4(1,3,2) + 4(1,2,3) + 4(2,3,1) + 4(3,1,2) = 6-2. III. Die Teilung Wir betrachten eine Teilmenge AcX. Zu dieser Inklusion bezeichne g: X Av(A) die Abbildung mit: Le falls a e A g(a) A sonst. g setzen wir fort zu einer partiellen Abbildung g: XW A"" mit Definitionsbereich D(g) = (z e X' I zi e A für unendlich viele i) und der Definition: - 19 - hieraus: 4(2IA) = 4'(2) = 4(2) 4(A)-1 = 1/3. IV. Auswahlregeln als Invarianzeigenschaften von Kollektiven Auch die Auswahlregeln selbst erzeugen eine Operation, die gegebene Kollektive in neue überführt. Im Unterschied zu den vorangehenden Operationen haben die neugebildeten Kollektive hier die gleiche Verteilung wie die vorangehenden. Um dies zu beweisen, zeigen wir, daß das Produkt zweier partieller Funktionen 01° 02: X° ~ die von Auswahlregeln p1, p2: X* (0,1) erzeugt werden, ebenfalls von einer Auswahlregel erzeugt wird. Die zu 01°02 gehörige Auswahlregel P1,2 werde wie folgt definiert: :P1 02 (x)=1, T2(x) = 1 0 sonst. g(z) = 11 g(z.) (zeD(g)). i=1 Ist nun z ein Kollektiv zu einer Verteilung 4 mit 4(A)>0, dann folgt, daß g(z)E A"" ein neues Kollektiv ist. Für die neue Verteilung 4': 2A R gilt: 4'(B) = 4(B)4(A)-1. Zu CcX nennt man 4'(CnA) die bedingte Wahrscheinlichkeit von C bzgl. A und schreibt 4'(CnA) = 4(CIA). Es gilt dann 4(CIA) = 4(°.A) 4(A) Bedingte Wahrscheinlichkeiten ergeben sich also durch tUbergang zu einem neuen Kollektiv mittels der Operation der Teilung. Betrachten wir als Beispiel wieder den idealen Würfel. Gesucht sei die Wahrscheinlichkeit der 2 unter der Voraussetzung, daß eine gerade Zahl auftritt. Es sei A = (2,4,6). Es gilt 4(A) = 1/2 und Man verifiziert sofort, daß die Auswahlregel p1,2 die partielle Funktion 01002 erzeugt. Funktionen 01, 02: X" Xw erzeugen. P2 sei fest, cpi durchlaufe alle Auswahlregeln. Sei nun z ein Kollektiv zur Verteilung 4 mit zE D(i2). Für jede partielle Funktion 01: X~ ~ X mit 02(z) E D(41) gilt dann: lim n 1 ~ XA (01o02(z))i = 4(A) (AcX). n i=1 Denn die partielle Funktion 010 02 wird selbst von einer Auswahlregel erzeugt. Daraus folgt, daß (-2(z) ebenfalls ein Kollektiv zur Verteilung 4 ist. Die von den Auswahlregeln erzeugten partiellen Funktionen f: X°" ~ X~ stellen also hinsichtlich der Eigenschaft einer Folge, Zufallsfolge zu sein, invariante Transformationen dar. Diese partiellen Funktionen bilden nämlich Kollektive zu einer festen Vertei- Es seien nun pi, p2: X* (0,1) Auswahlregeln, die partielle - 20 - lung stets wieder auf Kollektive der gleichen Verteilung ab. Der VON MISES'sche Ansatz kann daher als Versuch gesehen werden, Kollektive durch invariante Transformationen zu charakterisieren. Die Definition (2.2) kann in äquivalenter Weise wie folgt formuliert werden. Definition (2.2)' Die Menge der Kollektive zu einer Verteilung µ auf X ist die größte Menge M c X , für die folgendes gilt: n (1) lim n-1 E xA(zi) = 41(A) n i=1 (z E M, A c X). (2) Für jede Auswahlregel m gilt: T(M fl D(4)) c M. Diese Idee, Kollektive durch invariante Transformationen zu charakterisieren, wird sich an späterer Stelle bei unserer Suche nach einer befriedigenden Definition der Kollektive noch als fruchtbar er-weisen. - 21 - 3. Erste Ansätze zur widerspruchsfreien Definition der Kollektive und ihre Kritik durch VILLE Der in Lemma (2.4) aufgezeigte Widerspruch im VON MISES'schen Konzept wurde bald erkannt. In der Folge begann die Suche nach Möglichkeiten, diesen Widerspruch zu beheben. Naturgemäß dachte man zu-nächst daran, den Begriff der Regellosigkeit einzuschränken. Eine re-Lativ scharfe Einschränkung der Regellosigkeit wurde von COPELAND (1928) mit dem Begriff der admissible numbers vorgeschlagen. Von ihnen nahm COPELAND an, daß sie bereits hinreichend regellose Eigenschaften hätten. Mit anderen Definitionen wurde die gleiche Klasse von Folgen unter dem Namen Nachwirkungsfreie Folgen von POPPER (1935) und unter dem Namen Normale Folgen von REICHENBACH (1935) eingeführt. Für diese Klasse von Folgen hat sich auch vielfach die Bezeichnung Bernouillifolgen eingebürgert. Bei der vorläufigen Diskussion der Kollektive beschränken wir uns nun stets auf den Fall X = {0,1) und ^ < µ(0) < 1. Eine Folge z E X** heißt Bernouillifolge zur Verteilung p, wenn für alle w E X* folgendes gilt: 1 n (B) lim n- l XX*w(z(i))= [w]. n i=1 Das heißt, der Grenzwert der relativen Häufigkeit, mit der ein Wort w als Teilwort in z auftritt, existiert für jedes Wort w und ist gleich der Wahrscheinlichkeit von [w] bzgl. der Produktverteilung zu p. Wir wollen nun zeigen, daß man die Bernouillifolgen durch eine Klasse von Auswahlregeln charakterisieren kann. Zu w E X* bezeichne w • : X* {0,1} diejenige Auswahlregel, die gegeben ist durch: Tw(v) __ 1 v E X*w 0 v X*w - 25 - D.n. ein Glied wird genau dann ausgewählt, wenn es auf ein Teilwort w folgt. Sei 2i eine Menge von Auswahlregeln p: X* {0,1) undµ eine Ver- teilung auf X = (0,1) mit 0 < 4(0) < 1. Eine Folge z E X~ heißt ein Kollektiv zu 21 und µ, wenn für alle E 21 mit zED() folgendes gilt: _1 n lim n > 4(z)i = 4(1). R(21,4) c X** sei die Menge aller Kollektive n i=1 zu 2I und I.L. Mit der Bezeichnung 2[c = {pw I w E X*) lassen sich die Bernouillifolgen wie folgt charakterisieren: Satz (3.1) z E X'' ist genau dann eine Bernouillifolge zu µ, wenn z E R(210,41. Beweis: (I) Angenommen z erfüllt (B) für alle w E X*, also insbesondere für w und w1 E X*. Wegen [w] 4 0 gilt dann zunächst z E D (~w) und aus der Relation (B) für w und w1 folgt unter Benutzung von durch leichte Rechnung, daß die relative Häufigkeit, mit der Teilwort w eine 1 folgt, gerade gegen 4(1) konvergiert, d.h. lim n -l yl w(z)i = 4(1). n i=1 (II) Sei z E R(2I0,µ). Wir beweisen für z die Relation (B) durch Induktion über die Länge von w. Für w = A ist (B) trivial. Sei nun (B) für w bereits bewiesen. Dann gilt insbesondere z E D(-1p-w), und somit gilt nach Definition von R(2i0,4): lim n 1 X[a)(4)w(z)i) = µ(a) a= 0,1. n i-1 Unter Benutzung der Induktionsannahme folgt: n tim n 1 ~ XX*wa z(i) = n i=1 n µ(a) lim n 1~ XX*w z(i) = µ[wa] (a = 0,1), q.e.d. n i=1 Die Existenz der Bernouillifolgen wird durch folgenden Satz gesi- chert: Satz (3.2) Für jedes aufzählbare System von Auswahlregeln 21 und jede Verteilung µ auf X gilt: R(21,4) 4 0. Es gilt schärfer, fast alle Folgen sind in R(L,µ), d.h. R(21,4) = 1. Der erste Teil des Satzes wurde zuerst von WALD [50] bewiesen. WALD zeigte ferner, daß R(2(,4) die Mächtigkeit des Kontinuums hat. Im Falle 0 < 4(0) < 1 ist dies eine Folgerung aus µ R(21,4) = 1. Uns interessiert im folgenden nicht nur das Resultat dieses Satzes, sondern ebenso die von uns zum Beweis benutzte Methode. Eine partielle Funktion H: X' Xe° heiße maßverkleinernd bzgl. einer Verteilung auf X*0, wenn für alle meßbaren C c X~ folgendes gilt: H-1(C) '- µ(C)• Lemma (3.31 Die von einer Auswahlregel p erzeugte partielle Funktion 1p: X'e ist maiverkleinernd bz •l. 'eder Produktverteilun• µ auf X''. Beweis: Zunächst zeigen wir, daß die Urbilder C-1[x] der von den endlichen Folgen x erzeugten Zylindermengen meßbar sind. Wir definie- zu x E X*: Yx = (w E X* I 4(w) = x und p(w) = 1). Es gilt dann-1[x] c [Yx] und weiter µ[w]4 0 auf ein es gilt: ren - Z4 - - Z7 - 4)-1[x] = 1 I U [Y ]• n E N w E Xn xw Da die meßbaren Mengen eine a-Algebra bilden und ferner jede Zylinder-menge meßbar ist, folgt, daß auch-1[x] meßbar ist. Nun zeigen wir durch Induktion über die Länge von x: (i) [Yx] µ [x]. Für x = A ist (i) trivial, denn es gilt [A]= X''. Sei (i) nun für x bewiesen und a E X. Aus der Definition von Yx folgt unmittelbar, daß Yxa c Yx a X* und somit [Yxa ] c [Yx a]. Aus der Induktionsannahme und der Produkteigenschaft von folgt sodann: [xa]= [x] µ(a) Z [Yx] µ(a) = [Yxa] Z µ [Yxa]. Damit ist (i) für alle x E X* bewiesen. Wegen-1[x] c [Yx] folgt aus (i): (T)-1[x] µ [x] (x E X*). Hieraus folgt, weil a-additiv ist: µ [A] [A] (A c x*). Durch eine Standardkonstruktion kann man diese Ungleichung nun auf alle meßbaren Mengen C c Xm übertragen q.e.d. Beweis zu (3.2): Wir benutzen das starke Gesetz der großen Zahl, welches in Paragraph 9 noch explizit bewiesen wird. Mit der Bezeichnung 9t = XW - [z E X lim n-1 zi = µ(1)) n i=1 lautet dieses Gesetz: (9t) = O. Nach Definition von R(91,4) gilt: R(91,4) = X°° v ii;-I(M). cp E 91 Weil 91 aufzänlbar ist und weil alle partiellen Funktionen mit cp E 91 maßverkleinernd sind, folgt R(91,µ) = 1. Damit ist (3.2) bewiesen. Eine besondere Rolle werden im folgenden noch die maßinva.rianten partiellen Funktionen H: spielen. heißt maßinvariant bzgl. einer Verteilung auf X'', wenn H-1(C) = µ(C) für alle meßbaren C c X. Lemma (3.3) impliziert das Korollar (3.4) Sei 0: X X eine von einer Auswahlregel cp erzeugte partielle Funk- tion, für die µ D(T)) = 1 erfüllt ist. Dann ist c maßinvariant bzgl. der Produktverteilung µ. Beweis: Weil 0 maßverkleinernd ist, gilt für jedes meßbare C c (1) i'li-l(c) µ(C) (2) µ (T-1(X- - C) µ(X- - C). Wegen µ 4--1(X0) = µ D(4) = 1 muß dann in (1) und (2) sogar Gleichheit gelten. Insbesondere sind damit die von den Auswahlregeln erzeugten totalen Funktionen T: X~ - XW maßinvariant bzgl. jeder Produktverteilung auf X~. Das gleiche gilt für die partiellen Funktionen 4w: X die von den Auswahlregeln pw erzeugt werden. Denn es gilt t a' = 1 für jede Produktverteilung µ. Auf die Maßinvarianz der von den Aus- wahlregeln erzeugten totalen Funktionen 0: Xm wies als erster DOOB (1936) hin. Wir bemerken noch, daß man gewisse Klassen R(91,4) von Kollektiven auch durch Invaria.nzeigenscha.ften charakterisieren kann. Eine Klasse 9t von Auswahlregeln heißt abgeschlossen gegenüber Komposition, wenn mit cp, E 2i stets ein y in 21 ist mit T 7 = F. Aus Paragraph 2 Ab- schnitt IV wissen wir, daß die Menge aller Auswahlregeln abgeschlossen gegenüber Komposition ist. Die Kollektive zu diesen Auswahlregeln lassen sich wie folgt durch Invarianzeigenschaften charakterisieren. Satz (3.5) Die Menge 2i von Auswahlregeln sei abgeschlossen gegenüber Komposition. Dann ist R(1,4) die größte Menge M c mit n (1) lim n -l E zi = 1/2 n i=1 (2) 4(M fl D(i)) c M für alle E S. Der Beweis ist trivial. Aufgrund des Satzes (3.2) glaubte man, der Charakterisierung der Kollektive einen wesentlichen Schritt. nähergekommen zu sein. CHURCH [ 6 ] schlug vor, die aufzdhlba.r vielen, möglichen Auswahlregeln als die rekursiven Auswahlregeln zu spezifizieren. Dabei heißt eine Auswahlregel cp rekursiv, wenn die Funktion cp: X* {0,1) rekursiv ist (zu "rekursiv" siehe [10,17,19 ] ). Es sei Wr die Menge der rekursiven Auswahlregeln. CHURCH schlug also vor, die Folgen in R('r,4) als Kollektive zur Verteilung 4 zu betrachten. Die Folgen in R(Er,4) ha-ben einige vernünftige Eigenschaften. R(21r,4) Läßt sich durch invariante Transformationen charakterisieren, denn Ur ist abgeschlossen gegenüber Komposition. Ferner kommen die Kollektive zu 9Ir unserer intuitiven Vorstellung von Regellosigkeit insoweit nahe, als diese Folgen selbst nicht rekursiv sind. Eine Folge z E heißt rekursiv, wenn {n l zn = 1) eine rekursive Menge ist. Korollar (3.6) Die im CHURCH'schen Sinne zufälligen Folgen sind nicht rekursiv. Beweis: Sei z E rekursiv. Die Auswahlregel cpi: X* - {0,1) (i = 0,1) definiere man durch zlxl + 1 = sonst. Da z rekursiv ist, folgt cpi rekursiv. Es gilt entweder z E D((T'0) oder z E D(t1). 40(z) besteht nur aus Nullen und $1(z) nur aus Einsen. Wegen 0 < 4(1) < 1 kann z somit nicht in R(41r,4) liegen. Dem Glauben, daß die Kollektive im Sinne von CHURCH allen unseren intuitiven Vorstellungen von Zufallsfolgen entsprechen, setzte ein Beispiel von VILLE im Jahre 1939 ein Ende. In der klassischen Maß-Wahrscheinlichkeitstheorie wurde bereits 1924 eine wesentliche Verschärfung des starken Gesetzes der großen Zahl bewiesen, welche die Art der Konvergenz der relativen Häufigkeit näher spezifiziert. Dieses Gesetz vom iterierten Logarithmus lautet in unserem Fall (X = {0,1)): n zi - n 4(1) fz E X~ 1 'ER i=1 =c+)1 1 c n ) D 42 n log log n Dabei ist D die Streuung der Zufallsvariablen, in unserem Fall D = '4(1) - 42(1) . Das Gesetz vom iterierten Logarithmus läßt er- warten, daß für jede Zufallsfolge die Relation n z. - n 4(1) 't-im i=1 =O1 4 n D /2 n log log n erfüllt ist. Demgegenüber hat VILLE folgendes gezeigt: Satz [49 ] Sei W ein abzählbares System von Auswahlregeln und f: N N eine monotone Funktion mit lim n 1f(n) = 0 und lim f(n) = . Dann gibt es n n ein K E N und ein z E R(1,4), so daß für alle n folgendes gilt: O s n 1 zi - 4(1) s n (1 + f(n)). i=1 i qpi(x) = In allen Anfangsstücken dieser Folge z kommt die 1 häufiger vor als die O. Setzt man für die Funktion f z.B. f(n) = [Log n] ([ ] sei die größte ganze Zahl kleiner gleich), dann folgt n zi - n4(1) Um 1=1 n D 12 n log log n Der Schwankungsbereich der relativen Häufigkeit von 0 und 1 ist dann geringer, als das Gesetz vom iterierten Logarithmus angibt. Von einigen Anhängern der VON MISES'schen Ideen wurde in der Folge-zeit bestritten, daß dem Gesetz vom iterierten Logarithmus eine physikalische Bedeutung zukomme. Sie argumentierten, daß dieses Gesetz in einem formalen Kalkül abgeleitet wurde, den man experimentell nicht bestätigen könpe. Zweites Kapitel Eine Obermenge der statistischen Zufallsgesetze (Zufallsfolgen im Sinne von MARTIN-LÖF) Angeregt durch die Untersuchungen von KOLMOGOROFF [21] griff MARTIN-LÖF 1966 [27] die Diskussion um den Begriff der Zufallsfolge wieder auf und rückte einen Gesichtspunkt in den Vordergrund, der im Ansatz bereits in der Arbeit von VILLE [49 ] steckt. Die ersten widerspruchsfreien Modelle für Zufallsfolgen von COPELAND, WALD und CHURCH scheitern daran, daß die Eigenschaften dieser Folgen sich nicht mit den Erwartungen decken, die man aus der herkömmlichen Maß-Wahrscheinlichkeitstheorie ableitet. Die von dieser Seite erwarteten Eigenschaften von Zufallsfolgen wie z.B. das starke Gesetz der großen Zahlen und das Gesetz vom iterierten Logarithmus entsprechen Nullmengen in X'''. Wenn man daher das Erfülltsein dieser Fastüberallgesetze als Kriterium für die Verträglichkeit mit der üblichen Wahrscheinlichkeitstheorie ansieht, ist es nur natürlich, diesem Umstand von vorn-herein in der Definition der Zufallsfolgen Rechnung zu tragen. Die sich so anbietende Charakterisierung der Zufallsfolgen lautet grob gesprochen wie folgt. Eine Folge z E XW ist genau dann zufällig, wenn sie alle Fastüberallgesetze der Wahrscheinlichkeitstheorie erfüllt. Aus dieser Sicht liegt das Problem nun darin, den Begriff des Fast-Uberallgesetzes (FÜG) zu formalisieren. Vernünftigerweise kann man nicht jede Nullmenge in X''' als ein statistisches Gesetz ansehen, denn ein statistisches Gesetz muß man notwendigerweise explizit angeben. Damit muß die zugehörige Nullmenge auf konstruktive Weise, d.h. mittels Algorithmen dargestellt werden. Die Notwendigkeit dieser Forde- = 0. i -30- rung sieht man auch wie folgt ein. Es gibt keine Folge z E X'', die in keiner Nullmenge liegt. Betrachtet man jedoch nur solche Nullmengen, die auf eine bestimmte Weise durch Algorithmen dargestellt werden, so sind diese Nullmengen aufzählbar. Diese Nullmengen definieren somit eine Menge vom Maß 1, nämlich die Menge aller Folgen, die in keiner dieser Nullmengen liegt. Diese Folgen können als Zufallsfolgen bezüglich des betrachteten Types einer konstruktiven Nullmenge angesehen werden. MARTIN-LÖF schlug in [ 27] eine Präzisierung der Fastüberallgesetze in der Form von rekursiven Sequentialtests vor. Die so definierten Zufallsfolgen nennen wir hyperzufällig. Es ist dies der erste Ansatz zum Begriff der Zufälligkeit, der alle statistischen Zufallsgesetze wie das Gesetz der großen Zahlen und das Gesetz vom iterierten Logarithmus berücksichtigt. Um den Begriff der hyperzufälligen Folge voll zu erfassen, diskutieren wir in diesem Kapitel verschiedene Zugänge zu diesem Begriff. In Paragraph 4 behandeln wir den Ansatz von MARTIN-LÖF über rekursive Sequentialtests, in Paragraph 5 eine Definition der hyperzufälligen Folgen durch Spielsysteme. In den Paragraphen 6 und 7 findet sich eine Charakterisierung der hyperzufälligen Folgen durch Invarianzeigenschaften. Die verschiedenen äquivalenten Beschreibungen hyperzufälliger Folgen zeigen, daß sich diese Folgen in vieler Hinsicht wie ideale Zufallsfolgen verhalten, und rechtfertigen die These, daß diese Folgen ideale Zufallsfolgen sind. Bei allen drei der obengenannten Definitionen der hyperzufälligen Folgen wird deutlich, daß von diesen Folgen Eigenschaften verlangt werden, die zwar mit Rechenprozessen zusammenhängen, die jedoch nicht in effektiver Weise in diesen zum Ausdruck kommen. Die Definition des rekursiven Sequentialtests liefert zum Beispiel keinen Hinweis, wie das entsprechende Fastüberallgesetz an einer vorgegebenen Folge effek- - - tiv nachzuprüfen ist. Einem statistischen Gesetz kommt aber nur dann eine physikalische Bedeutung zu, wenn man explizit angeben kann, wie dieses Gesetz nachgeprüft werden soll. Damit ist nicht gesichert, ob allen Eigenschaften, die man von hyperzufälligen Folgen verlangt, eine physikalische Bedeutung zukommt. Die Invarianzeigenschaften von hyper-zufälligen Folgen sind Funktionen, die i.a. nicht "effektiv" im intuitiven Sinne sind. Bei der Beschreibung hyperzufälliger Folgen durch Spielsysteme werden die Einsätze eines Spielers durch Funktionen aus-gedrückt, die ebenfalls i.a. nicht berechenbar und somit auch nicht effektiv sind. Daneben wird in der. Beschreibung hyperzufälliger Folgen durch Spielsysteme noch eine besondere Unsymmetrie sichtbar, welche in Paragraph 8 näher untersucht wird. Durch Beseitigung dieser Unsymmetrie gelangt man zu einem schärferen Konzept der Zufallsfolge. Die Nullmengen im Sinne von MARTIN-LÖF sind nicht die allgemeinsten Nullmengen, welche konstruktiv beschreibbar sind. Vielmehr kann man ohne große Schwierigkeit Konzepte für "nicht effektive" Zufallstests entwickeln, die alle Folgen beliebig hoher Klassen der KLEENE Hierarchie als nicht zufällig ablehnen. Diese Möglichkeit, immer schärfere Konzepte konstruktivistischer Zufallstests zu entwickeln, legt es nahe, daß nicht die Menge derjenigen Nullmengen entscheidend ist, die sich in irgendeiner Form durch Algorithmen beschreiben lassen, sondern daß es auf die Menge der effektiv nachprüfbaren statistischen Zufallseigenschaften ankommt. Die-se statistischen Zufallsgesetze werden in Kapitel III charakterisiert. 4. Hyperzufällige Folgen Wir behandeln nun den Vorschlag MARTIN-LÖF's zur Definition von Zufallsfolgen. MARTIN-LÖF schlug vor, den herkömmlichen Begriff der Nullmenge auf eine spezielle Weise zu konstruktivisieren und die so definierten "konstruktiven" Nullmengen als FÜG'e zu interpretieren. Diese "konstruktiven" Nullmengen i.S. von MARTIN-LOF nennen wir re-kursive Nullmengen. Das charakteristische an diesem Konzept ist die Existenz einer universellen rekursiven Nullmenge, die alle anderen rekursiven Nullmengen umfaßt. Es sei X = [0,1} und µ die Gleichverteilung auf X, d.h. 4(0) = 4(1) = 1/2. Wir betrachten auf X" das Produktmaß und die Produkttopologie zur diskreten Topologie auf X. D.h. B c ist genau dann offen, wenn B Zylindermenge ist, also B = [A] für ein geeignetes A c X*. Definition (4.1) B c X" heißt rekursiv offen (r.o.), wenn es ein rekursiv aufzählba.-res A c X* gibt mit B = [A]. 2 c X" soll nun genau dann eine rekursive Nullmenge sein, wenn man beliebig kleine rekursiv offene Umgebungen von 2 effektiv angeben kann. Definition (4.2) 2 c ist eine rekursive Nullmenge, wenn es eine rekursiv aufzähl- bare Menge Y c N x X* gibt mit (1) [Yi] s 2-i (i E N), (2) 2 c (;)N [Yi]. Dabei sei Yi = (x E X* I (i,x) E Y). Y heißt ein rekursiver Sequentialtest zu 2. Die von Y erzeugte rekursive Nullmenge ist 2y = i`E1N [Yi]. Man sagt, die Folgen in 7ty bestehen den rekursiven Sequentialtest Y nicht. Da Y rekursiv aufzähl- bar ist, sind die Umgebungen [Yi] von 2y rekursiv offen. In Analogie zu den p.r. Funktionen gilt nun folgendes Aufzählungstheorem für die rekursiven Sequentialtests. Satz (4.3) Die Menge aller rekursiven Sequentialtests ist rekursiv aufzählbar. Das heißt, es gibt eine rekursiv a.ufzählba.re Menge Y c N x N x X*, so daß Yi = {(n,x) (i,n,x) E Y) mit i E N alle rekursiven Sequentialtests durchläuft. Beweis: Da die-rekursiv aufzählbaren Mengen gerade die Definitionsbereiche der p.r. Funktionen sind, folgt aus dem Aufzählungstheorem für die p.r. Funktionen (siehe Anhang), daß es eine rekursiv aufzählbare Menge Y c N x N x X* gibt, so daß Yi mit i E N alle rekursiv aufzählbaren Teilmengen von N x X* durchläuft. Da Y nicht leer ist, kann man eine rekursive Funktion 'n: N -' N x N xX* konstruieren mit h- (N) = Y. - Wir ändern nun Y rekursiv so ab, daß aus allen Projektionen Yi rekursive Sequentialtests werden. Es bezeichne Yim) = {x E X* I (i,n,x) E j U m (j)). 'n ändern wir rekursiv ab zu einer rekursiven Funktion h: N N x N x X* U (I). Dabei sei I ein noch unbenutztes Symbol. h(m) falls 'n(m) = (i,n,x) mit µ[Vim)] s 2-n sonst. Es bezeichne Y = h(N) - {I}. Dann ist nach Konstruktion jede Projektion Yi ein rekursiver Sequentialtest,und alle rekursiven Sequentialtests kommen unter den Yi vor, q.e.d. Sei Y c N x N xX* eine rekursive Aufzählung aller rekursiven Sequentialtests. Dann wird durch h(m) = U. Y kYN k,i+k+1 ein rekursiver Sequentialtest II c N x X* definiert. Denn U ist rekursiv aufzählbar, und es gilt: uCIIi]-s L [Yk,i+k+1] k E N s ~ 2-i-j s 2-i j=1 U hat die besondere Eigenschaft, daß für test Yk der Aufzählung folgendes gilt: [Yi+k+1] c [Ui] (i E N). Somit ergibt sich der folgende Satz (4.4) Es gibt einen rekursiven Sequentialtest II c N x X*, so daß es zu jedem rekursiven Sequentialtest Y c N z X* ein k E N gibt mit [Yi+k] c [Ui] (i E N). Ein solcher rekursiver Sequentialtest heißt universell. jeden rekursiven Sequentialtest Y. folgt für die von U erzeugte Nullmenge RU das Korollar (4.5) Ist U ein universeller rekursiver Sequentialtest, dann enthält TU jede rekursive Nullmenge. RU heißt die universelle rekursive Nullmen-~i• Definition (4.6) Die Folgen in R. = - R hei en h n def U p YPerzufällig. Korollar (4.7) µ(Rh) = 1, d.h. fast alle Folgen sind hyperzufällig. Wir zeigen nun eine erste Eigenschaft von hyperzufälligen Folgen, die wir intuitiv von jeder Zufallsfolge erwarten. Satz (4.8) Keine hyperzufällige Folge ist rekursiv. Beweis: Wir zeigen, daß es zu jeder rekursiven Folge z E X~ einen re-kursiven Sequentialtest gibt, den die Folge z nicht besteht. Zu einer rekursiven Folge z E X''' definieren wir einen rekursiven Sequential-test Y c N xX* wie folgt: Yi = (z(i)). Y ist rekursiv aufzählbar, und es gilt [Yi] = µ[z(i)] = 2-i. Nach Konstruktion gilt weiter z E ii [Yi] . iEN Mit Korollar (4.8) ist also gezeigt, daß es keine rekursive Folge im Komplement der universellen rekursiven Nullmenge Tu gibt. Damit ist es aber auch fraglich, ob man RU als ein statistisches Gesetz an-sehen kann. Denn dies hieße ja, daß man zu diesem statistischen Gesetz keine Folge konstruieren kann, die es erfüllt. Andererseits liegt es nahe zu erwarten, daß die effektive Nachprüfbarkeit eines FUG'es, was immer wir darunter verstehen, es gerade gestattet, solche Folgen zu konstruieren, die das FUG erfüllen. Gerade deshalb, weil wir das starke Gesetz der großen Zahlen dadurch nachprüfen können, indem wir die Anzahl der Nullen und Einsen in den Anfangsabschnitten vergleichen können, ist es möglich, Folgen zu konstruieren, die das starke Gesetz der großen Zahlen erfüllen, etwa die Folge 01010101.... Was soll es aber überhaupt heißen, das zu einer rekursiven Nullmenge zugehörige FUG nachzuprüfen? Sei Y c N x X* ein rekursiver Sequentialtest. Zu x E X* und i E N bedeutet der Wert 21xl µ([Yi] fl [x]) jeden rekursiven Sequential- /-) [Yi] iEN Für einen universellen rekursiven Sequentialtest U gilt c n [Ui] für iEN Also die Wahrscheinlichkeit dafür, daß eine unendliche Folge, die mit x beginnt, in der r.o. Umgebung [Yi] der rekursiven Nullmenge MY = N [Y.] liegt. Dieser Wert sagt also etwas darüber aus, inwie- weit die Anfangsfolge x dem zu M, zugehörigen FtG entspricht. Ist der Wert hoch, dann entspricht x eben diesem FÜG in relativ geringem Maße. Nun haben wir aber bei der Definition rekursiver Sequentialtests keineswegs gefordert, daß man diese Werte effektiv berechnen kann. Tat- sächlich ist dies, wie wir noch sehen werden, im allgemeinen und ins-besondere für einen universellen rekursiven Sequentialtest auch nicht der Fall. Daher ist nicht gesichert, daß alle Eigenschaften, die formal von hyperzufälligen Folgen verlangt werden, auch physikalisch interpretierbar sind. Wir benutzen im folgenden eine Normierungsmöglichkeit für rekursive Sequentialtests. Eine Menge A c X* heißt prefix-frei, wenn A n AXX* = 0. D.h. kein Wort von A ist Prefix (Vorsilbe) eines anderen. Das interessante an den prefix-freien Mengen ist, daß für jede solche Menge A folgendes gilt: µ[A] = Z xEA Lemma (4.9) Man kann zu jeder rekursiv aufzählbaren Menge A c X* eine prefix-freie, rekursive Menge B c X* so konstruieren, daß [Al = [B]. Beweis: Zu jeder rekursiv aufzählbaren Menge A c X* kann man eine re-kursive Funktion h: N - X* U [I] konstruieren mit A = h(N) n X. Das Zeichen ist notwendig zur Darstellung der leeren Menge. Wir bezeich- nen An = U h(i) n X. Die Länge der längsten Folge in An sei r(n). isn Wir setzen r(n) = 0, wenn An = 0. Die charakteristische Funktion XB: X* - {0,1} von B wird wie folgt definiert: XB(x) = 0 für alle x, so daß Ixi i r(n) + n für alle n E N. XB(x) mit IxI = r(n) + n wird rekursiv wie folgt bestimmt: Für IxI = r(0): ti x = h(O) 0 sonst, für Ixl = r(n) + XB(x) 1 x E An X* - An-1X* Aus der Konstruktion folgt, ner gilt für alle n [An] = [BX* n Xr(n)+n]. Daraus folgt [A] = [B], q.e.d. Wendet man obiges Lemma auf rekursive Sequentialtests an, gibt sich das Korollar (4.10) Zu jedem rekursiven Sequentialtest Y c NxX* kann man einen rekursiven Sequentialtest Y - c N x X* mit My = Ti so konstruieren, daß Y - eine rekursive Teilmenge von N x X* und Yi - für alle i prefix-frei ist. Will man den Begriff des rekursiven Sequentialtests Y verschärfen, was eines unserer Ziele ist, dann genügt es also nicht zu fordern, daß Y rekursive Teilmenge von N XX* ist, selbst wenn man zusätzlich fordert, daß alle Yi prefix-frei sind. Wir werden im Folgenden von einem vorgegebenen rek. Sequentialtest Y c NxX* auch ohne ausdrücklichen Hinweis stets annehmen, daß Y cNxX* eine rekursive Menge ist. XB(x) = n, n 0 sonst. daß B rekursiv und prefix-frei ist. Fer- so er- l~+ 5. Hyperzufällige Folgen und das Prinzip vom ausgeschlossenen Spielsystem Historisch sind die Begriffe Wahrscheinlichkeit und Zufälligkeit eng mit den Glücksspielen verbunden. Man hat allgemein die Vorstellung, daß ein Spieler bei einem Glücksspiel auf die Dauer nicht gewinnen kann, sofern dem Spiel eine echte Zufallsfolge zugrundeliegt und die Auszahlungsbedingungen auf Chancengleichheit beruhen. Wir wiesen schon darauf hin, daß auch das VON MISES'sche Modell des Kollektivs an einem solchen Spielmodell orientiert ist. Nun wollen wir die hyper-zufälligen Folgen durch das Prinzip vom ausgeschlossenen Spielsystem charakterisieren. Ein Spiel in unserem naiven Sinne soll gegeben sein durch zwei Funktionen Bi: X* R+ i = 0,1 Dabei sei R+ die Menge der nicht negativen reellen Zahlen. Bezogen auf eine unendliche Folge z E bedeutet Bi(z1...zn) den Einsatz, den der Spieler nach Kenntnis der ersten n Glieder der Folge auf das Ereignis n+1 = i setzt. Die Einsatzfunktionen Bi (i = 0,1) erzeugen aus einem Anfangs-vermögen V(A) E R eine Vermögensfunktion V: X* -' R. Dabei bedeutet V(z1...zn) das Vermögen nach den ersten n Spielrunden, wenn der Zufallsgenerator mit z1z2...zn beginnt. Das Vermögen ändert sich von der n-ten zur n+1-ten Spielrunde wie folgt: V(z1z2...zn+1) = V(z1z2...zn) + E. (2 bi 1=0,1 zn+1 i Dabei ist bk das Kroneckersymbol. Die Auszahlungsbedingung (A) bedeutet, daß der gesetzt hat, zurückerhält und dazu noch den gleichen Betrag als Prämie. Der auf das nicht eintretende Ereignis gesetzte Betrag geht ihm verloren. Hieraus folgt für das Vermögen V die Funktionalgleichung (M) V(x) =2-1 V(xo) +2-1 V(x1) (x E X*). Diese Gleichgewichtsbedingung drückt aus, daß das Vermögen nach der n-ten Spielrunde gleich dem Erwartungswert für das Vermögen nach der (n+1)-ten Spielrunde ist. Funktionen V: X* ~ R mit (M) heißen Martin-gale oder auch Vermögensfunktionen. (M) nennen wir die Martingaleigenschaft. Martingale wurden im Zusammenhang mit Zufallsfolgen zum ersten Mal von VILLE [49 ] betrachtet. Lemma (5.1) Jedes Martingal V: X* ~ R wird von geeigneten Einsatzfunktionen aus dem Anfangsvermögen V(A) erzeugt. Beweiss Man setze Bi(x) = 2-1 V(xi). Dann gilt mit der Bezeichnung 0 = 1, 1 = 0: V(x) + ~ (2 b: - 1) Bi(x) i=0,1 = V(x) + 2-1V(xj) - 2-1V(xj) = V(xj) (j=0,1). Also ist die Auszahlungsbedingung (A) für diese Einsatzfunktionen er-füllt. V wird somit von obigen Einsatzfunktionen erzeugt. Wir bemerken noch, daß man die Einsatzfunktionen natürlich so abändern kann, daß sie nicht negativ sind. z (A) - 1) Bi(z1z2...zn). Spieler den Einsatz, auf das eintretende Ereignis er den -40- Allgemein ist es in Spielbanken üblich, daß ein Spieler während des Spiels keine Schulden bei der Bank machen darf, d.h. er darf nie mehr einsetzen, als sein augenblickliches Vermögen beträgt. Wir fordern daher im folgenden die Einsatzbedingung (E) B0(x) + B1(x) s V(x) (x E X*). Die Bedingung (E) sichert gerade, daß V nicht negativ ist. Ist andererseits V nicht negativ, so sind Bi(x) = 2-1V(xi) i = 0,1 Einsatzfunktionen, dieVerzeugen. Aus der Martingal-Eigenschaft folgt, daß B0 und B1 dann (E) erfüllen. Von einer Zufallsfolge z wird man erwarten, daß ein Spieler auf die Dauer in einem Spie' über z nicht gewinnen kann, d.h., daß sein Vermögen beschränkt bleibt. Natürlich muß man verlangen, daß die Einsatzfunktionen in irgendeiner Form konstruktiv sind. Wir betrachten zunächst einen sehr weiten Typ von konstruktiven Einsatzfunktionen und zeigen, daß die hyperzufälligen Folgen durch Spiele mit solchen Einsatzfunktionen charakterisiert werden. Definition (5.2) Eine Funktion F: X* ~ R heißt subberechenbar, wenn es eine rekursive Funktion g: N x X* ~ Q gibt mit (1) g(i,x) s g(i+1,x) (i E N, x E X*), (2) Lim g(i,x) = F(x) (x E X*). i Eine Funktion F: X* ~ R ist berechenbar im üblichen Sinn genau dann, wenn F und -F subberechenbar sind. Genau die berechenbaren Funktionen sind im intuitiven Sinne effektiv. Das Hauptresultat dieses Paragraphen ist der Satz (5.3) Eine Folge z E X's ist genau dann hyperzufällig, wenn es kein subbe- rechenbares Martingal V: X* ~ R+ gibt mit Lim V(z(n)) = n Aus dem Satz folgt sofort das Korollar (5.4) Eine Folge z ist genau dann hyperzufällig, wenn bei jedem Spiel über z mit subberechenbaren Einsatzfunktionen, die (E) erfüllen, das Vermögen beschränkt bleibt. Zum Beweis ziehen wir ein Lemma vor. Zu V: X* ~ R+ bezeichne V(k) = { ), E X* V(x) > Id. Zu A c X* sei A = [x E A 1 x AXX*). A ist die Menge aller Folgen in A, die nicht Fortsetzung einer kürzeren Folge in A sind. Für A c X* gilt stets (i) µ [A] = 5EL 2-Ixl+ xEA und für jede Vermögensfunktion V: X* R+ gilt (ii) 2-lylV(y) V(x) 2-lxl (y E x*, A c x*). xEA fl yX* Nun beweisen wir das Lemma (5.5) Für ein Martingal V: X* ~ R+ und k > 0 gilt stets: µ[V(k) n yX*] s V(y) ü[y]k-1 (y E X*). Beweis: Es gilt wegen (i), (ii): 2-lylV(y) z Z V(x)2-ixl z k 2-Ixt xEV~ xEV(k)lyX* nyx = k [v(k) f1 yX*]. Wir bemerken noch, daß wir zum Beweis von (5.5) nur einen Teil der (M) ausnutzten, nämlich die Ungleichung V(x) 2 1/2 (V(xO) + V(x1)). Zu einem Martingal V: X* ~ R+ bezeichnen wir: - 4Z - 7tV = [z E Xmllim V(z(n)) = .} = %1 [V(n)]. n nE N Aufgrund von Lemma (5.5) ist 7tV eine Nullmenge, denn es gilt [P(n)] = [V(n) n AX*] s V(A) n-1 Ein Martingal V: X* R+ und die zugehörige Nullmenge 7tV sind in einer besonders sinnfälligen Weise miteinander verknüpft. Die Größe des Wertes V(x) gibt gerade an, inwieweit die Folge x dem Fastüberallgesetz entspricht, das durch die Nullmenge 7tV gegeben ist. Große Werte V(x) bedeuten, daß x diesem Fastüberallgesetz wenig entspricht. Dieser Zusammenhang läßt sich durch Lemma (5.5) noch präzisieren. Sei V(A)>1. Dann ist für jedes m E N,[V(k) n XmX*] eine Umgebung von 7tv, und ihre Größe kann man abschätzen durch [V(k) n XmX*] s k-1. Zu x E X* bedeutet µ [V(k) n xX*] die Wahrscheinlichkeit dafür, daß eine Folge, die mit x beginnt, in der Umgebung [V(k) n XlxlX*] von %v liegt. Lemma (5.5) besagt, daß man diese Wahrscheinlichkeit mit Hilfe des Funktionswertes V(x) abschätzen kann. Da dies für alle k > 0 gilt, enthält der Wert V(x) eine Bewertung der Folge x hinsichtlich beliebig kleiner Umgebungen von %v. Beweis von (5.3): (I) Angenommen z E XW ist hyperzufällig, und V: X* ~ R+ ist ein subberechenbares Martingal. Man wähle k E N so, daß k > V(A). Dann definieren wir einen rekursiven Sequentialtest Y c N xX* durch: Yi = Ex E X*IV(x) > 2ik}. Aus V subberechenbar folgt Y rekursiv aufzählbar. Lemma (5.5) impliziert, daß Y ein rekursiver Sequentialtest ist. Es gilt 9ty = Rv. (II) Angenommen es gelte im V(z(n)) < 00 für jedes subberechenbare n Martingal V: X* ~ R+. Sei Y c N xX* ein rekursiver Sequentialtest mit Yi n YiXX* = 0 (i E N). Nun definieren wir ein Martingal V: X* ~ R+ durch - Yl V(b) = L._ i ( L 2-IaI + XYiXX*(b))• iEN baEYi / ist subberechenbar, weil Y rekursiv aufzählbar ist. Wir zeigen, daß / die Eigenschaft (M) erfüllt. Für j E X liefert bja E Yi folgende Beiträge zu V(b) den Beitrag i 2-ljal zu V(bj)_den Beitrag i 2-lal zu V(bj) den Beitrag 0 Für diese Beiträge gilt die Relation (M): i 2-I5al___ 2-1(i 2-lal + 0). b E Yi liefert folgende Beiträge zu V(b) den Beitrag i (innere Summe) zu V(bO) den Beitrag i (Xy xX*(b0) i zu V(bl) den Beitrag i (XyXX*(b1). Schließlich liefert b E YiXX* jeweils den Beitrag i zu V(b), V(bO), V(bl) und zwar durch Xy xX*. Da für alle Summanden von V(b), V(bO), V(b1) einzeln die Relation (M) gilt, genügt V selbst der Relation (M). Die Bedingung Yi n YiXX* = 0 impliziert V(A) = Ti 5[Y] s li 2-i. iEN 1 iEN Damit sind alle fierte V(b) endlich, und es ist gezeigt, daß V: X* R+ ein subberechenbares Martingal ist. Angenommen, es gelte z E ILf. Zu i E N gibt es dann ein n E N mit z(n) E Yi. Es folgt V(z(n)) 2 i. Also impliziert z E 7ty die Relation Tim V(z(n)) = im Widerspruch zur Annahme. Somit ist z hyperzufällig, n q.e.d. Die Darstellung der rekursiven Nullmengen durch subberechenbare - 44 - Martingale macht es deutlich, daß man diese Nullmengen nicht durchweg als effektiv nachprüfbare Fastüberallgesetze deuten kann. Zu einer endlichen Folge x gibt der Wert V(x) zwar an, inwieweit die Folge x dem zu RV gehörigen Fastüberallgesetz entspricht. Je größer V(x) ist, desto weniger erfüllt die Folge x dieses Gesetz. Aber der Wert V(x) kann i.a. nicht effektiv bestimmt werden, denn er ist nur subberechenbar. Es liegt also nahe, daß zur Charakterisierung der effektiv nach-prüfbaren Zufallseigenschaften nur berechenbare Martingale V: X* R+ in Betracht kommen. Naturgemäß wird man ein Fastüberallgesetz für be-sonders wichtig halten, wenn man eine zugehörige Vermögensfunktion V auf einfache Weise berechnen kann. Zum Abschluß des Kapitels zeigen wir noch, daß sich der Äquivalenzsatz (5.3) nicht ändert, wenn man TIE durch lim ersetzt. D.h. wenn es ein subberechenbares Martingal V: X* R+ gibt mit lim V(z(n)) = n dann gibt es auch ein subberechenbares Martingal V: X* - R+ mit lim V(z(n)) _ n Satz (5.6) Es gibt ein subberechenbares Martingal V: X* R+, so daß {z E X Ilim V(z(n)) = .0} die universelle rekursive Nullmenge ist. n Beweis: Es sei U c N x X* ein rekursiver Sequentialtest zur universellen rekursiven Nullmenge Mu. U sei so normiert, daß Ui fl UiXX* = 0 (i E N). Wir betrachten das zu U gehörige Martingal V: X* R+, das wie im Beweis zu (5.3) definiert ist: V(b) = ~ ( E2-lal iEN baEU + XUXX*(b)). Sei z E Mu = i?N [Ui]. Dann gibt es zu jedem i E N ein n E N, so daß z(n) E Ui. Daraus folgt V(z(m)) i für alle m i n. Da dies für alle i gilt, folgt die Behauptung. 6. Charakterisierung hyperzufälliger Folgen durch Invarianzeigenschaften Wir wiesen bereits darauf hin, daß man den VON MISES'schen Ansatz zur Definition der Kollektive auch unter dem Gesichtspunkt der Invarianzeigenschaften sehen kann. Eine Folge sollte nämlich genau dann zufällig sein, wenn sie das starke Gesetz der großen Zahlen erfüllt und wenn durch Anwendung von Stellenauswahlen aus dieser Folge stets wieder Zufallsfolgen entstehen. Nachdem aus der VILLE'schen Kritik hervorging, daß die rekursiven Stellenauswahlen nicht zur Charakterisierung aller Zufallseigenschaften ausreichten, versuchte man, den Begriff der Auswahlregel zu verallgemeinern. So kann man z.B. die Glieder der Folgen zuerst permutieren und dann eine Auswahlregel anwenden. D.h. die Glieder werden nicht mehr notwendigerweise in der Reihen-folge ihres Auftretens in der Folge ausgewählt. Solche verallgemeinerten Stellenauswahlen wurden von KOLMOGOROFF [22 ] und LOVELAND [24 ] betrachtet. (Siehe auch Beispiel [2] in Paragraph 11.) Sofern man diese verallgemeinerten Stellenauswahlen immer so vornimmt, daß ein Glied stets ohne Ansehen des Gliedes selbst ausgewählt wird (also nur in Abhängigkeit von den übrigen Gliedern), sind die so erzeugten partiellen Transformationen von X" maßverkleinernd bezüglich jedes Produktmaßes. Dies beweist man mit einer ähnlichen Argumentation, wie wir sie hinsichtlich der VON MISES'schen Auswahlregeln benutzten(siehe (3.3)). Damit folgt nach der gleichen Schlußweise wie zum Beweis von Satz (3.2), daß es zu abzählbar vielen solcher Transformationen stets Kollektive gibt, die das starke Gesetz der großen Zahlen erfüllen und durch diese Transformationen stets wieder in solche Kollektive abgebildet werden. Wir wollen nun diesen Zusammenhang in seiner Umkehrung betrachten 40 - und zeigen, daß alle stetigen, maßverkleinernden, partiellen Funktionen H: Xm ~ f, die zusätzlich in einem sehr schwachen Sinne konstruktiv sind, stets hyperzufällige Folgen wieder in solche abbilden. Andererseits lassen sich die hyperzufälligen Folgen durch diese Invarianzeigenschaften auch charakterisieren. Eine partielle Funktion Hs X* X* heißt monoton, wenn H(xy) E H(x)X* für alle x,xy E D(H). Einer partiellen, monotonen Funktion H: X* ~ 1* ordnen wir in eindeutiger Weise eine partielle Funktion H: Xm Xm zu, indem wir defi- nieren: D(H) = [H-1(XnX*)], nEN K H(z) E [H(z(i))] (z E D(H), z(i) E D(H)). D(H) besteht aus allen Folgen z E Xm, so daß es zu jedem n E N ein i gibt mit IH(z(i))l > n. Durch H ist H in eindeutiger Weise bestimmt. Wir sagen, H werde von H erzeugt. Dabei können verschiedene partielle, monotone Funktionen H dieselbe partielle Funktion H erzeugen. Wir wollen nun zeigen, daß die von den partiellen, monotonen Funktionen H: X* ~ X* erzeugten partiellen Funktionen H: Rm Xm im wesentlichen die partiellen, stetigen Funktionen von Xm nach Xm sind. Wir erinnern daran, daß eine Funktion H: Xm ~ Xm genau dann stetig ist, wenn das Urbild H-1 [A] einer offenen Menge [A] stets wieder offen ist. Eine partielle Funktion H: Xm ~ Xm ist genau dann stetig (bzgl. der durch die Inklusion D(H) c Rm auf D(H) induzierten Topologie), wenn es zu jeder offenen Menge [A] c Xm eine offene Menge [B] c Xm gibt mit H-1 [A] _ [B] fl D(H). Lemma (6.1) Eine partielle Funktion F: Xm ~ Xm ist genau dann stetig, wenn es- 41 eine partielle, monotone Funktion H: X* ~X* gibt mit (1),(2). (1) D(F) c D(H) (2) F(z) = H(z) (z E D(F)). Beweis: (I) Es sei H: X* ~ X* eine partielle, monotone Funktion. Dann gilt ff-1 [A] = [H 1(AX*)] fl D(H) für alle A c X*. Damit ist stetig und somit auch jede Einschränkung von H. (II) Sei F: Xm ~ Xm eine partielle stetige Funktion. Dann gibt es zu jedem y E X* eine Menge A c X*, so daß F-1[y] = [A] fl D(F). Ferner kann man A stets in dem Sinne "klein" wählen, daß [a] fl D(F) 4 0 für alle a E A. Beachtet man, daß [A] = [AX] für alle A c A*, dann gibt es zu jedem y E X* eine Menge Ay c X*, so daß F-1(y) = [Ay] n D(F) (y E X*), [a] fl D(F) 4 0 (a E Ay), (y E X*, x E XX*). Nun definiere man die partielle Funktion H: X* ~ X* wie folgt: H(b) = y (b E Ay). Nach Konstruktion ist H: X* ~ X* eine partielle, monotone Funktion mit D(H) D D(F) und H(z) = F(z) für alle z E D(F). Definition (6.2) Eine partielle Funktion Xm Xm heiße subberechenbar stetig (sb. s.), wenn H von einer partiell rekursiven, monotonen Funktion H: X* X* erzeugt wird. Es zeigt sich, daß die strengere Forderung H rekursiv nicht zu einer Verschärfung von (6.2) führt. Mit einer ähnlichen Konstruktion, wie wir sie zum Beweis des Lemmas (4.9) benutzten, beweist man das Ayx c AyXX* -48- Lemma (6.3) Es gibt einen Algorithmus, der zu jeder partiell rekursiven, monotonen Funktion H: X* X* eine rekursive, monotone Funktion HI: X* ~ X* konstruiert mit Fit=H. Beweis: H sei gegeben durch eine rekursive Funktion h: N ~ X*xX* U [I) mit h(N) fl X* x X* ={(x,y) I H(x) = y). Zu x E X* bezeichne (a E X* x X* sei gegeben als a = (al,a2)) A(x) = U H(x(i)) fl U h(i)2 islxl islxl Die Funktion X* - X* berechne man nun rekursiv wie folgt: Falls A(x) + 0, setze man H1(x) = y mit !yl = max lzl und y E A(x). zEA(x) In diesem Fall wählt man also die längste Folge in A(x). Falls A(x)=O, setze man H1(x)=A. Nach Konstruktion gilt dann H=Hl. Dagegen ergibt sich eine Verschärfung von (6.2), wenn man verlangt, daß die Längen IH(z(n))l für alle z E D(IR) mit n in konstruktiver Wei-se gegen unendlich konvergieren. Dies führt zum Begriff der berechenbar stetigen (b.s.) Funktion H: Xe Xe0. Einer rekursiven, monotonen Funktion H: X* X* und einer rekursiven Funktion h: N N ordnen wir wie folgt eine berechenbar stetige, partielle Funktion Hh: X ~ X~ zu: D(Rh) = (z E Xe0 ~ IH(z(h(n)))jz n (n E N)}. Hh(z) = H(z) (z E D(Hh)). h ist ein Stetigkeitsmodul zu Hh. Definition(6.4) Eine partielle Funktion F: X" ~ X" heißt berechenbar stetig, wenn es eine rekursive, monotone Funktion H: 1* ~ X* und eine rekursive Funktion h: N N gibt mit F = Hh. Wir bemerken noch, daß die obigen Klassen von partiellen Funktionen abgeschlossen gegenüber Zusammensetzung sind. Seien H,G: X* X* zwei rekursive, monotone Funktionen, dann ist HG ebenfalls rekursiv und monoton, und es gilt HG = HG . Seien zusätzlich h und g: N ~ N rekursive Funktionen, dann gilt: HhGg = HG (hg). D.h. die Zusammen- setzung der Stetigkeitsmoduln von I-I und G: X° Xm ist Stetigkeitsmodul von-737. Es zeigt sich nun, daß hyperzufällige Folgen durch partielle, sub-berechenbar stetige, maßverkleinernde Funktionen stets wieder in hyper-zufällige Folgen abgebildet werden. Hierzu erweitern wir den Begriff "maßverkleinernd" geringfügig. Eine Funktion H: Xe0 ~ Xe0 heiße maßbeschränkt, wenn es ein K E N gibt, so daß für alle meßbaren A c folgendes gilt: R -1(A) . K µ(A). Satz (6.5) Sei h X°° ~ Xe0 eine partielle, sb.s. und maßbeschränkte Funktion. Dann gilt F(Rh fl D(F)) c Rh. Zum Beweis ziehen wir ein Lemma vor. Lemma (6.6) Sei 2 c X°° eine rekursive Nullmenge und H: Xe ~ X°° eine partielle, sb.s. und maßbeschränkte Funktion, dann ist H-1(2) ebenfalls eine re-kursive Nullmenge. Beweis: Sei Y c N x X* ein rekursiver Sequentialtest zu 2 und H: X* ~ X* eine partiell rekursive, monotone Funktion, die H erzeugt. Es gelte H-1(A) < 2kµ(A) -50- für alle meßbaren A c X. Den rekursiven Sequentialtest zu 7-1(2) definieren wir durch Yi = H-1(Yi+kX*) (i E N). Es gilt dann [Yi] = [H-1(Yi+kX*)]£ µ 7-1 CYi+kl ¢ 2k [ i+k] S 2-i. ist rekursiv aufzählbar, weil Y rekursiv aufzählbar und weil H partiell rekursiv ist. Somit ist Y ein rekursiver Sequentialtest. Nach Konstruktion gilt: H-1 [Yi+k] c [Yi] (i E N). Daraus folgt 7-1(2) c My, also ist 7-1(2) eine rekursive Nullmenge. Beweis zu (6.5): Angenommen, es gilt 7(z) 4 Rh für ein z E Rh. Dann gibt es eine rekursive Nullmenge 72 c mit H(z) E T. Es folgt z E 7-1(2). Da 7-1(9) nach Lemma (6.6) ebenfalls eine rekursive Nullmenge ist, ergibt sich ein Widerspruch zur Annahme z E Rh. Wir verschärfen den Satz (6.5) und zeigen, daß man die hyperzufälligen Folgen durch Invarianzeigenschaften charakterisieren kann. Satz (6.7) Für jede rekursive Folge x E X° gilt: Eine Folge z ist genau dann hyperzufällig, wenn es keine partielle, subberechenbar stetige und maßverkleinernde Funktion H: f° X°° gibt mit H(z) = x. Beweis: (I) Aus z E Rh folgt nach (6.5), daß H(z) nicht rekursiv ist. (II) Sei z 4 Rh. Dann gibt es einen rekursiven Sequentialtest Y mit z E 2y. O.B.d.A. nehmen wir an, daß Yi+1 c YiX* (i E N). Es genügt, eine partielle, sb.s. maßverkleinernde Funktion H: X~ X zu konstruieren, so daß H(My) = (x). Man definiert hierzu die p.r., monotone Funktion H: X* X* durch H(u) = x(i) für alle u E Yi. Es gilt dann: D(H) = n [Yi]. iE N - 7 - Die so erzeugte partielle Funktion 7 ist subberechenbar stetig und maßverkleinernd. Es gilt R(2y) _ {x}. Abschließend weisen wir darauf hin, daß die subberechenbar stetigen Funktionen und somit die Invarianzeigenschaften der hyperzufälligen Folgen nicht effektiv im intuitiven Sinne sind. Effektiv im intuitiven Sinne sind dagegen die berechenbar stetigen Funktionen. Es erhebt sich somit die Frage, welche Klasse von Folgen durch solche "effektiven" Invarianzeigenschaften charakterisiert wird. Diese Frage wird in den Paragraphen 11 und 12 beantwortet. Die Charakterisie- rung der hyperzufälligen Folgen durch Invarianzeigenschaften in (6.7) ist inhaltlich trivial. Eine eigenständige Bedeutung erlangt dieser Zugang zum Begriff der Zufälligkeit erst, wenn man sich auf "effektive" Zufallstests beschränkt. - 72 - 7. Weitere Einwände gegen den Begriff der Zufällig- keit im Sinne von MARTIN-LOP Die Zufallsfolgen im Sinne von MARTIN-LÖF werden durch subberechenbare Martingale V: X* -. R+ charakterisiert. Die algorithmische Struktur dieser Martingale ist nicht symmetrisch. Es gibt keinen naheliegenden Grund, subberechenbare Martingale V denjenigen Martingalen V vorzuziehen, für die -V subberechenbar ist. Es erhebt sich daher die Frage, welche Zufallseigenschaften durch die letztere Klasse von Martingalen erfaßt werden. Definition (7.1) Ein Martingal V: X* -. R+ ist ein (0)-Test, wenn -V subberechenbar ist. Tv = (z E X I m V(z(n)) = oo} ist die Menge der Folgen, die def n den (0)-Test V nicht bestehen. Eine Folge z E XW heiße (0)-zufällig, wenn sie jeden (0)-Test be-steht. Wir behandeln nun die Frage, ob die (0)-zufälligen Folgen mit den hyperzufälligen Folgen übereinstimmen. Es erscheint als eine Schwäche des Konzepts der Zufälligkeit im Sinne von MARTIN-LOP, daß dies nicht der Fall ist. Darin drückt sich nämlich ein Mangel an Symmetrie in diesem Konzept aus. Satz (7.2) Es gibt (0)-zufällige Folgen, die nicht hyperzufällig sind. Zunächst beweisen wir folgendes Lemma (7.3) Sei V ein (0)-Test und a > 0 rational. Dann gibt es eine rekursive Folge z E so daß V(z(n)) < V(A) + a (n E N). Das heißt z 4 %v. - JJ Beweis: Der (0)-Test V sei gegeben durch die rekursive Funktion g: N x X* -. Q, so daß g(i,x) z g(i + 1,x) und lim g(i,x) = V(x). i Sei b eine rationale Zahl mit V(A) - a/2 < b < V(A). Die Folge z konstruieren wir rekursiv wie folgt: Angenommen, z(n) sei bereits so konstruiert, daß n V(z(i)) s b + a 2-i-1 (i s n) j=0 erfüllt ist. (Man beachte, daß diese Induktionsvoraussetzung für n = 0 trivial ist.) Aus der Induktionsvoraussetzung folgt, daß es ein x E X gibt mit n V(z(n)x) s b + a 11 2-j-1. j=0 Demnach kann man auf effektive Weise ein i E N und ein x E X bestim- n+1 g(i,z(n)x) s b + a E 2-j-1. j=0 Wir definieren z(n+1) = z(n)x. Aus dieser Konstruktion folgt die Behauptung: V(z(n)) s b + a < V(A) + a (n E N), q.e.d. Beweis von (7.2): Sei (Viii E N) eine Aufzählung aller (0)-Tests mit Vi(A) <_ 1. Es genügt, eine Folge z zu definieren, die nicht hyperzu- fällig ist und für die lim Vi(z(n)) (i E N). n Sei U c N x X* ein universeller rekursiver Sequentialtest. Wir definieren z E X°° induktiv wie folgt. Wir nehmen an, daß z(nk) mit nk E N bereits so definiert ist, daß [z(nk)] [Uk] und k k 2-ni-i V(z(j)) < 2-i (j < nk). 0 1 i-0 men, so daß (Man beachte, daß die Induktionsannahme für k = 0 trivial ist, wenn - 54 - man no = 0 wählt.) Nun betrachten wir Vk+1. Offensichtlich gilt k 2 Vk+1(z(nk)) s 2-k. Dies folgt aus Vk+1(A) s 1 und der Martin- galeigenschaft. Folglich gibt es ein rekursives y E X'', so daß y(nk) = z(nk) und daß k+1 k++1 2-ni-i V (y(j)) s 2-i (j E N). 1=0 i i=0 Dies folgt nämlich im wesentlichen aus der Konstruktion, die wir im Beweis zu (7.3) benutzten. Weil y rekursiv ist, gibt es ein nk+1 > nk, so daß Cy(nk+1)] c [Uk+l]. Wir definieren z(nk+1) = y(nk+1). Diese Definition von_z impliziert z E Tu. Andererseits gilt . ~m E 2-ni-i Vi(z(j)) 5 2 (i E N). j i=0 Folglich gilt z 4 Tv (i E N), q.e.d. i Dieselbe Beweismethode führt zu dem lemma (7.4) Jede hyperzufällige Folge ist (0)-zufällig. Beweis: Sei V: X - R+ ein (0)-Test, der gegeben ist durch die rekur- sive Funktion g: N x X* Q mit g(i+1,x) s g(i,x) und lim g(i,x)=V(x). i Wir konstruieren zu V ein rekursives Martingal V: X* Q+ mit RV c R. Dabei sei Q+ die Menge der nicht negativen rationalen Zahlen. Wir konstruieren V rekursiv wie folgt: V(A) = g(0,A) + 2. Sei V(x) bereits so konstruiert, daß V(x) > V(x) + 2- IxI. Man setze V(x1) = g(i,xl) + 2- Ixl-1 mit i = min {jlg(j,x1) + g(j,xO) .A 2(V(x) - 2 IxI))- - und V(xO) = 2 V(x) - 17(x1). Aus der Rekursionsannahme folgt, daß man das obige i effektiv bestimmen kann. Wir verifizieren noch die Rekursionsannahme für V(xO): V(xO) = 2 V(x) - V(xl) = 2 V(x) - g(i,xl) - 2- IxI-1 z g(i,xO) + 2 IxI-1 > V(xO) + 2- Ix0I. V: X* Q+ ist somit ein rekursives Martingal mit RV c 7tV, q.e.d. Wir haben insgesamt das überraschende Ergebnis, daß es für ein Martingal V: X* - R+ wesentlich ist, ob man V oder -V als subberechenbar voraussetzt. Als nächstes wollen wir ein Konzept der Zufälligkeit entwickeln, das auf Martingalen V: X* -- R+ beruht, deren algorithmische Struktur symmetrisch ist. Definition (7.5) Ein Martingal V: X* -. R+ ist ein (1)-Test, wenn es eine rekursive Funktion g: N x X* -. Q gibt mit lim g(i,x) = V(x) für alle x E X*. i Tv = {z E X~ I lim V(z(n)) = ist die Menge der Folgen, die den def n (1)-Test V nicht bestehen. Eine Folge z E Xc° heiße (1)-zufällig, wenn sie jeden (1)-Test be-steht. Wir zeigen, daß (1)-Zufälligkeit wesentlich schärfer ist als Zufälligkeit im Sinne von MARTIN-16F. Offensichtlich ist jedes subberechenbare Martingal V: X* R+ ein (1)-Test. Somit ist jede (1)-zufällige Folge auch hyperzufällig. Um zu beweisen, daß die Umkehrung hierzu nicht gilt, betrachten wir die Kleene Hierarchie der arithmetischen Mengen. Die Kleene Hierarchie der Prädikate klassifiziert die "arithmetischen" Mengen wie folgt in Klassen £n, [In n = 0,1...: £n ist die (nach Def. von i) -56- Klasse aller Mengen A der Form A = {al(Q1x1)(Q2x2)...(Qnxn) P(a,x1,x2,...xn)). Dabei ist P ein rekursives Prädikat, die Q2k+1 sind Existenzquantoren und die Q2k sind Generalisierungen (für alle -Quantoren). Die Klasse IIn von Mengen wird ebenso definiert, nur daß hier die Q2k Existenzquantoren und die Q2k+1 Generalisierungen sind. Folgende Beziehungen der Klassen En und Zn sind bekannt [38 ]: (2) A E En o Ao E nn (A° ist das Komplement von A). (3) En U IIn c En+1 n nn+1 für alle n Z 0 und die Inklusion ist echt für n > O. (4) A E En+1 " A ist rekursiv aufzählbar bezüglich einer Menge B E IIn. (5) A E En+1 n nn+1 * A ist rekursiv bezüglich einer Menge B E IIn. Die Klasse En n En wird üblicherweise mit An bezeichnet. Eine Folge z E X~ gehört per Definition zur Klasse En (bzw. nn), wenn {nIzn = 1) in En (bzw. En) liegt. Satz (7.6) Es gibt hyperzufällige Folgen in A2. Beweis: Sei V: X* R+ ein universelles subberechenbares Martingal, d.h. Rh = X~ - Mv. Die Existenz eines solchen Martingals folgt z.B. daraus, daß es zu jedem rekursiven Sequentialtest Y (also auch zu je-dem universellen) ein subberechenbares V gibt mit MY c Mv (siehe den Beweis zu (5.3)). V sei gegeben durch die rekursive Funktion g: N x X* Q mit g(i+1,x) z g(i,x), lim g(i,x) = V(x). Ferner nehmen i77 - wir o.B.d.A. an, daß V(A) < 1. Dann ist das folgende Prädikat P: X* {0,1) in Ui: P(x) = 1 « V g(i,x) < 1. iEN Aus P kann man z E rekursiv wie folgt konstruieren: zi+1 = 1 P(z(i)1) = 1. Aus der obigen Eigenschaft (5) folgt, daß z E A2. Die Konstruktion von z sichert z (t Mv, q.e.d. Zusammen-mit (7.6) drückt der folgende Satz aus, daß (1)-Zufälligkeit wesentlich schärfer ist als Zufälligkeit im Sinne von MARTIN-LÖF. Satz (7.7) Es gibt keine Folgen in E2 U n2, die (1)-zufällig sind. Beweis: (I) Es sei z E Xm eine Folge aus E2. Dies bedeutet nach Definition, daß {nlzn = 1) in E2 liegt. Dann gibt es ein rekursives Prädikat P: N3 - {0,1), so daß für alle n E N: zn = 1 a 3 V P(j,i,n) = 1. jEN iEN Wir definieren einen (1)-Test V mit z E Iv, indem wir eine rekursive Funktion g: N x X* -. Q angeben. Wir bezeichnen f(i,n) _ {jl d P(j,r,n) = 1, j s U. rsi Die endliche Menge f(i,n) kann man zu gegebenem i und n effektiv be-stimmen. Nun berechnen wir g(i,x) rekursiv wie folgt: g(i,A) = 1 (i E N). Im Falle (f(i,n) 0 A yn = 1) v (f(i,n) = O A yn = 0) definieren wir: g(i,y(n)) = 2 g(i,y(n - 1)) (Y E r). (1) EO = no = E1 (1 n1 ist die Klasse aller rekursiven Mengen. - 58 - Im Falle (f(i,n) 0 .. yn = 0) v (f(i,n) = 0 n definieren wir: g(i,y(n)) = 0 (y E XW). Daraus folgt: 2 lim g(i.y(n-1)) zn = yn+ lim g(i,y(n)) = i i 0 zn yn' 0 y(n) # z(n). Das bedeutet z E Mv. (II) Sei z eine Folge i-n II2. Das bedeutet, daß (nIzn = 0) in £2 liegt. Nach dem gleichen Argument wie in (I) folgt somit, daß z nicht (1)-zufällig ist, q.e.d. Somit ist gezeigt, daß man die Zufälligkeit im Sinne von MARTIN-LÖF weiter verschärfen kann. Vergleiche hierzu auch den Vorschlag von D.W. MÜLLER [33 ], der ebenfalls eine Verschärfung des Begriffs der Zufallsfolge im Sinne von MARTIN-LÖF enthält. Außerdem sei noch dar-auf hingewiesen, daß man den Begriff des rekursiven Sequentialtests U c N x X* natürlich dadurch erweitern kann, indem man für U alle Mengen aus den Klassen £n, IIn n 2 0 der Kleene Hierarchie zuläßt, mit µ [Ui] s 2-i. Auf diese Weise kommt man zu einem Konzept der Zufälligkeit, für das alle arithmetischen Folgen, d.h. Folgen in den Klassen £n, IIn n a 0 , nicht zufällig sind. Einem Vorschlag von WALD [50] zufolge sollte die Menge der statistischen Gesetze durch die Klasse derjenigen Nullmengen (der Vor-schlag von WALD bezog sich damals nur auf Auswahlregeln) präzisiert werden, die sich in einem festen logischen System ausdrücken lassen. Das Komplement der Vereinigung dieser Nullmengen hat dann das Map 1 (denn in einer logischen Sprache können nur abzählbar viele Nullmengen bezeichnet werden) und könnte somit als die Menge der Zufallsfolgen definiert werden. Da man aber jede logische Sprache noch erweitern kann, erscheint es nicht möglich, auf diese Weise zu einem end-gültig schärfsten Konzept der Zufallsfolge zu gelangen. Beispielsweise hat MARTIN-LÖF [28] die Menge aller hyperarithme- tischen Zufallseigenschaften betrachtet. Die Klasse 411 = £11 fl II11 der hyperarithmetischen Mengen besteht gerade aus denjenigen Mengen, die sich in- beiden 1-Funktionsquantorenformen darstellen lassen (siehe z.B. ROGERS [38]). Die Gesamtheit der Mengen der arithmetischen Hierarchie bildet eine echte Teilklasse von 411. MARTIN-LÖF hat gezeigt, daß der Durchschnitt aller hyperarithmetischen Mengen vom Maß 1 selbst keine hyperarithmetische Menge ist. Die Menge der Folgen, welche alle hyperarithmetischen Zufallseigenschaften erfüllen, führt daher gerade aus der Klasse der hyperarithmetischen Men-gen hinaus. Diese Argumente bestärken unsere Überzeugung, daß logischer Formalismus alleine nicht zur endgültigen Präzisierung des Zufallsbegriffs führt. Dagegen muß, wie im folgenden noch ausgeführt wird, der intuitive Begriff des effektiv nachprüfbaren statistischen Zufallsgesetzes geklärt werden. Folglich ist V ein (1)-Test, und es folgt: 2n y(n) = z(n), V(y(n)) Drittes Kapitel Die statistischen Zufallsgesetze (Endgültige Definition der zufälligen Folgen) Eine Schwäche des MARTIN-LÖF'schen Konzepts der Zufallsfolgen liegt darin, daß Zufallseigenschaften gefordert werden, die keine physikalische Bedeutung haben. Zu einem Zufallsgesetz im Sinne von MARTIN-LÖF kann man im allgemeinen keine Folge effektiv angeben, die dieses Gesetz erfüllt. Die Existenz der Zufallsfolgen im Sinne von MARTIN-LÖF beruht auf dem Auswahlaxiom, und die Theorie liefert keinen Hinweis, wie diese Folgen auf effektive Weise approximiert werden können. Dies alles beruht im wesentlichen darauf, daß Fastliberallgesetze zugelassen wurden, die nicht in einem effektiven Sinne nachprüfbar sind. Die effektive Nachprüfbarkeit eines Fastüberallgesetzes bzgl. einer Folge z E X~ kann nur in asymptotischer Weise gemeint sein. Zu einer dichten Nullmenge 7t c X ist die Relation z E 7t nicht in endlich vielen Schritten entscheidbar. Denn z E 7t hängt nicht von einem endlichen Anfangsstück von z ab. Z.B. kann man zu einer vorgegebenen Folge nicht in endlich vielen Schritten feststellen, ob sie das starke Gesetz der großen Zahlen erfüllt, d.h. ob n Lim n-1 f zi = 1/2. Aber wir können zu jeder Anfangsfolge z(n) in n i=1 effektiver Weise die relative Häufigkeit n-1 zi bilden und somit i=1 messen, inwieweit diese Anfangsfolge dem starken Gesetz der großen Zahlen entspricht. Allgemein postulieren wir, daß ein nachprüfbares Zufallsgesetz mit einer effektiven Bewertung verbunden ist, die zu jeder endlichen Folge angibt, inwieweit diese Folge dem Gesetz entspricht. Eine solche Bewertung ist dann ein effektiver Zufallstest. Die effektiven Zufallstests sollen genau die Eigenschaften von Zufallsfolgen erfassen, die in Rechenprozessen effektiv zum Ausdruck kommen. Es sind dies genau diejenigen Zufallseigenschaften, die physikalische Bedeutung haben und die durch statistische Erfahrung belegt werden können. Eine Folge ist genau dann nicht zufällig, wenn es einen Rechenprozeß gibt, indem diese Nicht-Zufälligkeit effektiv sichtbar wird. Andererseits ist es klar, wenn es keinen Rechenprozeß gibt, in dem sich die Folge in effektiver Weise als nicht zufällig erweist, dann verhält sich diese Folge wie eine ideale Zufallsfolge. Die Definition der Zufälligkeit muß daher so angelegt sein, daß diese Folge per definitionem zufällig ist. Es ist unsere tberzeugung, daß die geforderte Absolutheit des Begriffs des effektiven Zufallstests nicht durch einen formalen mathematischen Beweis nachgewiesen werden kann. Die Vielfalt der Möglichkeiten, mit denen Zufallseigenschaften in Rechenprozessen zum Ausdruck kommen können, ist nicht a priori überschaubar. Daher ist jede Präzisierung unserer intuitiven Vorstellung vom effektiven Zufallstest nur ein Vorschlag zu einer Definition. Dieser Vorschlag erhärtet sich, wenn sich eine Reihe von verschiedenen Zugängen zum Begriff des effektiven Zufallstests als äquivalent erweisen. Der Vorschlag zur Definition der Zufallsfolgen muß letztlich eine These sein, ähnlich der CHURCH'schen These. Dabei wird die CHURCH'sche These bereits voraus-gesetzt, denn jeder der Zugänge zum Begriff des effektiven Zufalls-tests beruht auf dem Begriff der effektiven arithmetischen Funktion. In den Paragraphen 8 - 12 wird gezeigt, daß alle im zweiten Kapitel behandelten Charakterisierungen der hyperzufälligen Folgen äqui- - 62 - valente Definitionen der Zufälligkeit liefern, wenn man sich jeweils auf diejenigen Zufallstests beschränkt, die effektiv sind. Daneben leiten wir noch weitere äquivalente Darstellungen der effektiven Zufallstests her. In Paragraph 14 zeigen wir, daß Zufallsfolgen durch Optimalitätseigenschaften für die Bank ausgezeichnet sind. In Para-graph 15 behandeln wir die Programmkomplexität nach KOLMOGOROFF. Es ist eine weitere Rechtfertigung unserer Theorie, daß sich Zufallsfolgen durch die von uns definierte "effektive" Programmkomplexität charakterisieren Lassen. - 63 - 8. Charakterisierung von Zufallsfolgen durch konstruktive Nullmengen nach L.E.J. BROUWER In Paragraph 4 wiesen wir darauf hin, daß rekursive Sequential-tests im allgemeinen nicht als effektive Tests interpretiert werden können. Dies liegt daran, daß für einen rekursiven Sequentialtest Y c N x X* die Werte µ ([Yi] n [x])2IxI x E X*, i E N im allgemeinen nicht effektiv berechnet werden können. Der obige Wert gibt gerade die Wahrscheinlichkeit an, daß eine mit x beginnende Folge in der r.o. Umgebung [Yi] von My liegt. Er sagt etwas darüber aus, in-wieweit die Folge x dem zu TY gehörigen Fastüberallgesetz entspricht. Wir behandeln nun einen Typ einer Nullmenge mit entsprechend schärferen Konstruktivitätseigenschaften. Diese Nullmengen entsprechen den in intuitionistischer Form von L.E.J. BROUWER untersuchten Nullmengen [ 3 ]. Eine Übersicht der Ideen von BROUWER findet sich in [18]. Eine Funktion f: N ~ R heißt berechenbar, wenn es eine rekursive Funktion g: N x N Q gibt mit If(n) - g(n,i)I s 2-i (n, i E N). Diese Definition gilt wie üblich in entsprechender Weise für Funktionen f: Y R, wobei Y eine ohne Wiederholung effektiv aufzählbare Menge ist. Man verifiziert sofort, daß f genau dann berechenbar ist, wenn f und -f subberechenbar i.S. von (5.2) sind. Eine reelle Zahl r heißt berechenbar, wenn es eine rekursive Funktion h: N Q gibt mit Ih(i) - rI s 2-i (i E N). Definition (8.1) Ein rekursiver Sequentialtest Y c N x X* heißt total rekursiv, wenn durch f(n) = [Yn] eine berechenbare Funktion f: N R definiert wird. Eine Menge 2 c Ty heißt dann eine total rekursive Nullmenge. -64- Wir bezeichnen diese Nullmengen als total rekursiv, weil wir sie als Gegenstück der total rekursiven Funktionen ansehen, während die rekursiven Nullmengen p.r. Funktionen entsprechen. Korollar (8.2) Ist Y c N x X* ein total rekursiver Sequentialtest, so wird durch g(i,x) = µ ([Y i] n[x]) 21xl eine berechenbare Funktion g: N x X* -" R definiert. Beweis: Zur Berechnung von g(i,x) bis auf eine Genauigkeit 2-n be-stimme man eine endliche Teilmenge A c Yi, so daß lµ [A] - [Yi] s 2-Ixl 2-n. Dann bestimme man ([A] n [x])= µ [A Xlxl n xX*]. Es folgt dann lµ ([A] n [x])- (Eli] n [x]) I t-n 2-Ixl, q.e.d. Wir geben nun eine erste Definition der zufälligen Folgen. Definition (8.3) Eine Folge z E X~ heißt zufällig, wenn sie in keiner total rekursiven Nullmenge enthalten ist. R c X~ sei die Menge aller zufälligen Folgen. Es gilt Rh c R und somit µ(R) = 1. Nach dem gleichen Schluß wie zum Beweis von (4.7) folgt das Korollar (8.4) Keine zufällige Folge ist rekursiv. Der wesentliche strukturelle Unterschied zwischen rekursiven und total rekursiven Nullmengen kommt darin zum Ausdruck, daß man zu je-der total rekursiven Nullmenge eine rekursive Folge im Komplement an-geben kann. Hierzu stützen wir uns auf das Lemma (8.5) Es sei A c X* rekursiv aufzählbar, a = [Al sei berechenbar und- 65 - a < 1. b > 0 sei eine rationale Zahl, und es sei ([z1 ... zr] n [A]) < a 2-r. Dann kann man ein zr+1 E X effektiv bestimmen, so daß ([z1 ••• zr+1] n [A])< a 2-r-1 + b. Beweis: Um zr+1 zu bestimmen, genügt es, µ ([z1 ... zr0] n [A]) und ([z1 ... zr1] n [A]) bis auf eine Genauigkeit b/2 zu berechnen. Satz (8.6) Zu jeder rekursiv aufzählbaren Menge A c X* und berechenbarem [A] < 1 kann man eine rekursive Folge z E X** - [A] bestimmen. Beweis: Wegen (8.5) kann man eine rekursive Folge z = z1z2... zi ... E X'' so berechnen, daß für r = 1,2,...: ([z1 ... zr] n [A])< 2-1 ([z1 ... zr_1] n [A]) + (1 - [A]) 2-2r. Durch Induktion über r folgt: r ([z1 ... zr] n [A]) < 2-r µ[A] + (1 - µ[A]) 'Z 2-2j 2-r+j j=1 s 2-r (µ[A] + (1 - u[A])) = 2-r. Damit gibt es kein r E N, so daß [z(r)] c [A]. Weil [A] offen ist, folgt daraus z [A]. Korollar (8.7) Zu jeder total rekursiven Nullmenge kann man eine rekursive Folge im Komplement angeben. Korollar (8.8) Die universelle rekursive Nullmenge ist keine total rekursive Null-menge. Korollar (8.9) Es gibt keine total rekursive Nullmenge, die alle total rekursiven - bb - Nullmengen umfaßt. (8.9) folgt aus (8.7) und (8.4). Eine Menge 9R von total rekursiven Sequentialtests heißt rekursiv aufzählbar, wenn es eine rekursiv aufzählbare Menge Y c N x N x X* gibt, so daß durch f(i,n) = [Yi,n] eine berechenbare Funktion f: N x N -. R definiert wird, und wenn ferner Tt = [Yi I i E N]. In Analogie zu den rekursiven Nullmengen gilt der Satz (8.10) Zu einer rekursiv aufzählbaren Menge MI von total rekursiven Sequentialtests kann man stets einen total rekursiven Sequentialtest U kon- struieren, so daß U My. c TU. YiEll Beweis: Di sei gegeben durch die rekursiv au£zählbare Menge Y c N x N x X*. U c N x X* wird definiert durch Uk = U Yi,i+k (k E N). i=0 Damit ist U ein rekursiver Sequentialtest (vergleiche den Beweis zu (4.4)). Wegen n _ [Uk] - [ U Yi,i+k] s 2-k-n i=0 genügt es, zur Berechnung von [Uk] die Werte [ U Yi i+k] hin-reichend genau zu berechnen. Zur Berechnung von µ [ U Yi,i+k] bis i=0 auf eine Genauigkeit kleiner gleich 2-r genügt es, endliche Teilmengen Ai,k c Yi,i+k so zu bestimmen, daß µ [Ai,k] - µ [Yi,i+k] s 2-r n-1. Dann gilt n-1 n-1 I µ[ U Ai,k] - [ U i,i+k] s 2-r. 1=0 i=0 Damit ist gezeigt, daß U ein total rekursiver Sequentialtest ist. Nach Konstruktion gilt U TY c TU (vergleiche den Beweis zu (4.4)). YiEMR i Zusammen mit Korollar (8.7) folgt aus (8.10) das Korollar (8.11) Zu einer rekursiv au£zählbaren Menge von total rekursiven Sequential-tests kann man stets eine rekursive Folge konstruieren, die alle die-se Tests besteht. Es folgt weiter das Korollar (8.12) Die Menge aller total rekursiven Sequentialtests ist nicht rekursiv aufzählbar. Bei dem obigen Ansatz zur Präzisierung von Zufallsfolgen wurde im wesentlichen die Vorstellung zugrundegelegt, daß eine Folge genau dann zufällig ist, wenn sie in keiner konstruktiven Nullmenge eines gewissen Typs liegt. Stattdessen könnte man ebenso gut davon ausgehen, daß eine Folge genau dann zufällig ist, wenn sie in jeder konstruktiven Menge vom Maß 1 liegt. Wir zeigen, daß beide Ansätze erwartungsgemäß äquivalent sind. Wir haben eine rekursive Nullmenge als Durchschnitt von rekursiv offenen Mengen definiert. Daher liegt es nahe, konstruktive Mengen vom Maß 1 als Vereinigung von rekursiv abgeschlossenen Mengen darzustellen. Eine Menge A c X'' ist genau dann bezüglich der Produkttopologie (zur diskreten Topologie auf X) abgeschlossen, wenn es eine Menge B c X* gibt mit A = n [B f1 Xn]. Genau dann gilt nämlich für das nEN Komplement von A: Ac = U [Bc fl Xn], und somit ist Ac offen. Wir nEN -69- nannten A c X° rekursiv offen, wenn es eine rekursiv aufzählbare Men- ge B c X* gibt mit A = U [B f1 Xn]. Dies ist äquivalent zur Existenz nEN einer rekursiven Menge B c X* mit A = U [B f1 Xn] (vergleiche (4.9)). nEN Dementsprechend heißt eine Menge A° c X°° rekursiv abgeschlossen, wenn es eine rekursive Menge B° c X* gibt mit A° [B° f1 Xn]. nEN Dann folgt, daß A° genau dann rekursiv abgeschlossen ist, wenn A re-kursiv offen ist. Definition (8.13) Eine Menge @ c X°° ist eine rekursive Menge vom Maß 1, wenn es eine re-kursive Menge Z c N x X* gibt, so daß mit der Bezeichnung Z(1) = [x E Xn I (i,x) E Z] folgendes gilt: nEN (1) Z(i) x 1 - 2-i (iEN), (2) U Z(1) = a. iEN @Z = U Z(1) heißt die von Z erzeugte Menge vom Map 1. iEN Korollar (8.14) Eine Menge @ c X ist genau dann eine rekursive Menge vom Maß 1, wenn @° eine rekursive Nullmenge ist. Beweis: (I) Sei Y c N x X* ein rekursiver Sequentialtest. Y c N x X* sei eine rekursive Teilmenge. Dann ist Z = Y° c N x X* ebenfalls def rekursiv, und es gilt: [Yi] = (Z(i))° (i E N). Daraus folgt, daß (Ty)° _ @Z eine rekursive Menge vom Maß 1 ist. (II) Sei Z c N x X* eine rekursive Teilmenge mit Z(1) z 1 - 2-1 (i E N). Dann gilt für Y = Z° . def Yi = (Z(1))° (i E N),und somit ist Ty = (OZ)° eine rekursive Nullmenge. Definition (8.15) Sei Z c N x X* eine rekursive Menge, so daß Z(i) 1 - 2-i (i E N) und daß durch f(i) = Z(1) eine berechenbare Funktion f: N R defi- niert wird. Dann heißt jede Menge 2 D @Z eine total rekursive Menge vom Maß 1. Ebenso wie Korollar (8.14) beweist man das Korollar (8.16) R c X°0 ist genau dann eine total rekursive Nullmenge, wenn R° eine total rekursive Menge vom Maß 1 ist. Korollar (8.17) Eine Folge z E X ist genau dann hyperzufällig, wenn sie in jeder rekursiven Menge vom Maß 1 liegt. Eine Folge z E X°° ist genau dann zufällig, wenn sie in jeder total rekursiven Menge vom Maß 1 liegt. - 70 - 9. Charakterisierung von Zufallsfolgen durch das Prin- - 71 - wenn T m (f(n) - h(n)) > O. n zip vom ausgeschlossenen Spielsystem Wir schreiben abkürzend Bei der Charakterisierung hyperzufälliger Folgen durch Martingale wiesen wir darauf hin, daß subberechenbare Einsatz- und Vermögensfunktionen i.a. keine effektiven Funktionen sind. Um diejenigen Zufallseigenschaften zu fassen, die in Rechenprozessen effektiv zum Ausdruck kommen, muß man sich auf effektive, d.h. berechenbare Martin-gale beschränken. Um eine Folge z E Xm aufgrund des Prinzips vom aus-geschlossenen Spielsystem als regelmäßig zu erkennen, genügt es aber nicht, daß für ein berechenbares Martingal V: X* - R+ die Folge (V(z(n)) I n E N) unbeschränkt ist. Denn das Wachstum dieser Folge könnte so langsam sein; daß es für einen Beobachter, der nur über effektive Methoden verfügt, überhaupt nicht erkennbar ist. Für ein be- rechenbares Martingal V: X* -• R+ bedeutet Tim V(z(n)) = m also nicht n in jedem Fall, daß eine Regelmäßigkeit in der Folge z effektiv sichtbar wird. Gibt es dagegen ein berechenbares Martingal V: X* R+ mit rasch wachsenden Werten V(z(n)), so wird man die Folge z als stark regelmäßig ansehen. Ein solcher Zufallsgenerator würde in kurzer Zeit zum Konkurs der Spielbank führen. Man sieht also, daß nicht der Wert V(z(n)) allein, sondern vor allem die Geschwindigkeit des Wachstums der Folge (V(z(n)) I n E N) Auskunft über Regelmäßigkeiten der Folge z gibt. Um diese Geschwindigkeit des Wachstums zu messen, führen wir Ordnungsfunktionen ein. Unter einer Ordnungsfunktion verstehen wir eine rekursive, monotone und unbeschränkte Funktion h: N N. Sei f: N -. R eine Funktion. Dann sagen wir, die Folge (f(n) n E N) wachse mit der Ordnung h, kTim f(n) = m, n wenn es eine Ordnungsfunktion h: N N gibt mit Tim (f(n) - h(n)) > O. n Ferner bedeute klim f(n) = m, n daß es eine Ordnungsfunktion h: N N gibt, so daß lim (inf f(i) - h(n)) > O. n i2n Man verifiziert leicht folgende Äquivalenzen. Lemma (9.1) (a) kTim f(n) = m gilt genau dann, wenn es eine rekursive Funktion n g: N N und eine unendliche Menge M c N gibt, so daß es zu jedem n E M ein i < g(n) gibt mit f(i) > n. (b) klim f(n) = m gilt genau dann, wenn es eine rekursive Funktion n g: N - N und eine unendliche Menge M c N gibt, so daß für alle n E M und für alle i > g(n) stets f(i) > n gilt. Beweis: Man setze jeweils zum Beweis der einen Richtung h(n) = max ({mIg(m) < n),{0)) und zum Beweis von links nach rechts setze man in beiden Fällen g(n) = min {mIh(m) > n}. Üblicherweise benutzt man in der konstruktiven Analysis inhaltlich stärkere Konstruktivisierungen von lim und T. Diese ergeben sich aus den obigen, indem man stets nur M = N zuläßt. Im Falle des oberen Grenzwertes und unter der in der konstruktiven Analysis häufig generell gemachten Voraussetzung, daß f: N N berechenbar ist, stimmen - 72 - beide Definitionen überein. Es gilt folgendes, leicht nachprüfbares Lemma (9.2) Für eine berechenbare Funktion f: N R sind folgende Aussagen äquivalent: (i) kZ m f(n) = n (ii) Es gibt eine rekursive Funktion g: N N, so daß es zu jedem n E N ein i < h(n) gibt mit f(i) > n. (iii) Die Folge (f(i)Ii E N) ist nicht beschränkt. Zu einer Vermögensfunktion V: X* R+ und einer Ordnungsfunktion h definieren wir die Nullmenge der Ordnung h zu V durch: RV,h = (z E X~ I Tim (V(z(n)) h(n)-1) > 01. n RV,h besteht aus allen Folgen z, für die (V(z(n)) In E N) bis auf einen konstanten Faktor mit der Ordnung h wächst. Es genügt uns, die Wachstumsgeschwindigkeit von V bis auf einen konstanten Faktor zu be-trachten. Dies wird sich in Paragraph 16 noch als sinnvoll erweisen. Wegen (5.5) ist RV,h eine Nullmenge. Wir zeigen, daß RV,h eine total rekursive Nullmenge ist, sofern V berechenbar ist. Zunächst beweisen wir das Lemma (9.3) Zu einer gegebenen, berechenbaren Vermögensfunktion V: X* R+ und n E N kann man stets eine rekursive Vermögensfunktion V: X* - Q+ konstruieren, so daß V(x) z V(x), IV(x) - V(x)Is 2-n (x E X*). Dabei sei Q+ die Menge der nicht negativen rationalen Zahlen. Beweis: Man kann eine rekursive Funktion f: X* Q konstruieren, so daß -73- If(x) - V(x) + V(x1)I S 2-n-3 2-Ixl. 7: X* Q+ berechne man wie folgt. V(A) E berechne man so, daß IV(A) + 2-n-1 - V(A)I s 2-n-2. Dann berechne man rekursiv für alle x E X*: V(x1) = V(x) - f(x) V(x0) = 7(x) + f(x) V erfüllt dann die Funktionalgleichung (M), und es gilt: IV(x) + 2-n-1 - V(x)I s 2-n-2 + 2-n-3 I~ -1 2-1 s 2-n-1. i=0 Hieraus folgt V(x) a V(x) , IV(x) - V(x)I s 2-n für alle x E X*. Damit ist 7: X* Q+ eine Vermögensfunktion der gesuchten Art. Satz (9.4) Zu einem gegebenen, berechenbaren Martingal V: X* -" R+ und einer Ordnungsfunktion f kann man stets einen total rekursiven Sequentialtest Y konstruieren mit RV,f c Ty. Beweis: Zu V konstruiere man eine rekursive Vermögensfunktion 7: X* Q+ mit V(x) z V(x) für alle x E X*. Y c N x X* definiere man wie folgt: V(x)2 z f(Ixl) V(x) z 21 V(A) Y ist eine rekursive Teilmenge von N x X*. µ[Yi] s 2-i folgt nach (5.5). Also ist Y ein rekursiver Sequentialtest. Nach Konstruktion gilt RV,f c RV,f c RY. Um µ[Yi] mit einer Genauigkeit kleiner gleich 2-r zu berechnen, bestimme man ein n E N so, daß f(n) > (2r 7(A))2, und bestimme die Menge An = Yi - XnX*. Es gilt dann: Yi - An c (x E X* I 7(x) > 2r V(A)), - 14 - und wegen lemma (5.5) folgt III[An] - µ[Yi] I S 2-r. Damit ist Y ein total rekursiver Sequentialtest, und nach Konstruktion gilt: My, f c 7t1,. Die Umkehrung von (9.4) liefert der folgende Satz (9.5) Zu einem total rekursiven Sequentialtest Y kann man stets eine be-rechenbare Vermögensfunktion V und eine Ordnungsfunktion f konstruieren mit My c MV f. Beweis: Sei Y c N x X* ein total rek. Sequentialtest. Es sei Y c N x X* rek. Teilmenge und Yi (iEN) prefix-frei (siehe (4.9)). Wir setzen B = U Y.. Dann ist 2-Ixl berechenbar, denn es gilt iEN 1 xEB n IZ 2-lxl - µ[ U Yi]I s 2-n, xEB i=0 n und µ[ LJ Yi] kann man für alle n berechnen. Da die Folge i=O 2-lxl xEB n XnX* mit wachsendem n monoton gegen 0 konvergiert, kann man eine Ordnungsfunktion f: N -. N konstruieren, so daß 2-lxI s 2-2f(n) xEB n xnX* Es gilt dann 2-lxl 2f(Ixl) s 2-2m 2m = 2-m xEB f(IxI)=m Daraus folgt 2-lxl 2f(Ixl) s > 2-m = 2. xEB m=0 -75- Also ist 2-Ixl 2f(Ixl) berechenbar, und man kann eine OrdnungsxEB funktion g: N -. N konstruieren, so daß (I) 2-lxl 2f(IxI) s 2-n. xEB n Xg(n)X* Durch 7n = B n xg(n)x* (n E N) wird nun ein neuer total rekursiver Sequentialtest T c N x X* definiert, und man verifiziert sofort, daß My = My. Nun definieren wir die Vermögensfunktion V: X* R+ wie folgt: V(b) = ( L 2-Iai 2f(Ibal) + 2f(n) XT (b(n))) iEN baETi n 0 zu berechnen, genügt es, V(x) bis auf E/4 zu berechnen und ferner zwei Werte A0 4 V(xO) und Al s V(xl) zu berechnen, so daß I2V(x) - A0 - All 1/2 immer etwas mehr als die Hälfte seines Vermön gens auf das Ereignis zn+1 = 1 und etwas weniger als die Hälfte auf das Ereignis zn+1 = 0 setzen muß. Tatsächlich können wir zeigen, daß eine solche Strategie in diesem Fall dazu führt, daß das Vermögen des Spielers exponentiell wächst. Zu einem rationalen q mit - 1 < q < 1 definieren wir eine Funktion V: X* ~ Q+ durch Vq(A ) = 1 V(x)(1+q) a = 1 Vq(xa) = Vq(x)(1-q) a = 0 Es gilt: Vq(x) = (1-q)Ixl - s(x) (1+q)s(x), und man verifiziert Vq(xi) = Vq(x)(1+q) + Vq(x)(1-q) i=0,1 = 2 Vg(x),Damit ist Vq: X* ~ Q+ eine rekursive Vermögensfunktion einfachster algorithmischer Struktur, denn Vq(xi)/Vq(x) ist nur von i abhängig. Vq entsteht aus Vq(A) = 1, indem immer das (1+q)/2-fache des Vermögens auf das Ereignis a = 1 und das (1-q)/2-fache des Vermögens auf das Ereignis a = 0 gesetzt wird. Im folgenden stehe 2v .b mit b > 1 stets für Tv ~f mit q q b fb(n) = [bn], wobei [ ] die größte ganze Zahl kleiner gleich bedeutet. Satz (10.1)°` Für z E X." gilt genau dann hin n-1 s(z(n)) = 1/2, wenn z 4 2V b n für alle rationalen q,b mit q E (-1,1), b E (1,°°). Beweis: Wir setzen R(z(n)) = s(z(n)) - 2-1n. Es gilt dann Vq(z(n)) = (1-q)2-1n - R(z(n)) (1+q)2-1n + R(z(n)) Es folgt In Vq(z(n)) = 2-1n [ln(1+q) + ln(1-q)] (10.2) + R(z(n)) [ln(1+q) - ln(1-q)]. (In bezeichnet den Logarithmus zur Basis e) (I) Wir nehmen an, daß 'Cim n -l s(z(n)) > 1/2, d.h. 'tim n-1 R(z(n)) > a n für ein geeignetes a > O. Aus (10.2) folgt dann für alle q E (-1,1) TM' n -l In Vq(z(n)) i 2-1 [ln(1+q) + ln(1-q)] n + a [ln(1+q) - 1n(1-q)]. Für ein hinreichend kleines q > 0 ist hier die rechte Seite echt größer als null. Denn ln(1+q) + ln(1-q) strebt für q 0 mit höherer q' - 81 - Ordnung gegen 0 als die für q > 0 positiven Werte ln(1+q) - ln(1-q). Es folgt also Tim n-1 ln Vq(z(n)) c für ein geeignetes c > O. Das heißt aber Vq(z(n)) > enc für unendlich viele n E N. Somit wächst Vq(z(n)) exponentiell, und es gilt z E RV ,b für geeignete rationale q E (0,1), b E (1,m). Symmetrisch hierzu folgert man aus lim n-1 s(z(n)) < 1/2, daß n z E %vq,b für geeignete rationale q E (-1,0) und b E (1,m). Insgesamt ist eine Richtung des Satzes gezeigt. (II) Nun nehmen wir an, daß lnm n -l s(z(n)) = 1/2, und betrachten die Relation (10.2). Für alle q gilt ln(1+q) + ln(1-q) s O. lim n-1 R(z(n)) = 0 impliziert also lnm n-1 ln V(z(n)) s O. Hieraus n folgt Tnm Vq(z(n))e-nc 1 für alle c > O. Folglich gilt z 4 RV b q, für alle rationalen q E (-1,1) und b E (1,m). Wir erweitern das Ergebnis nun, indem wir nach den Vermögensfunktionen fragen, die zu der allgemeinen Relation n (-1 3= B) lim n -l z(i) = µ[w) = 2-Iwl n i=1 für alle w E X* führen. Die Folgen z E X00, welche für alle w E X* die Relation (B) erfüllen, sind uns aus Paragraph 3 als Bernouillifolgen bekannt. Sei cpw: X* {0,1} die Auswahlregel mit 1 falls v E X*w :Gw(v) = 0 falls v 4 X*w, und seien 1)w: X* - X*, Tw: X°° -. X00 die hiervon erzeugten partiellen Funktionen. Dann wissen wir aus Satz (3.1), daß z genau dann Ber- nouillifolge ist, wenn für alle T, mit z E D(4w) die Folge Tw(z) das starke Gesetz der großen Zahlen erfüllt. Diesen Umstand nutzen wir nun aus. Zu einer Folge w E X* und einem rationalen q mit q E (-1,1) definieren wir eine rekursive Vermögensfunktion V(q,w): X* Q+ durch V(q.w)(A) = 1 V(q,w)(x)(1+q) xa E X*w1 V(q,w)(xa) V(q,w)(x)(1-q) xn E X*wO V(q,w)(x) x 4 X*w V(q,w) ist offensichtlich eine rekursive Vermögensfunktion. V(q,w) hängt mit Vq und der Auswahlregel cpw zusammen durch die Beziehung V(q,w)(x) = Vq(Ow(x))• Indem man (9.4) auf (1)w(z) anwendet und die Bezeichnung zwdä k(z) benutzt, folgt für alle z E D(4w) die Äquivalenz von (1) und (2): (1) lim n -l s(zw(n)) = 1/2 n (2) zw 4 2V b für alle rationalen q E (-1,1) und b E (1,m). cl' Unter der zusätzlichen Voraussetzung (3) lim n-1 10w(z(n))I > 0 n ist (2) noch äquivalent mit (4): (4) z 0 Tv ) b für alle rationalen q E (-1,1) und b E (1,m). (q,w , Hieraus können wir mit der gleichen Argumentation wie zu Satz (3.1) den folgenden Satz beweisen. Satz (10.3) z E ist genau dann Bernouillifolge zur Gleichverteilung auf X, wenn für alle w E X* und für alle rationalen q,b mit q E (-1,1), b E (1,m) stets z 4 Tv ) b gilt. q - 82 - Beweis: (I) Wenn z Bernouillifolge zur Gleichverteilung auf X ist, dann gilt für jedes w E X* lnm n -l I1)w(z(n))j = 2-1141, also ist die Zusatzvoraussetzung (3) stets erfüllt. Es folgt somit z 4 RV(q,w)'b für alle rationalen q E(-1,1) und b E (1,m). (II) Unter der umgekehrten Annahme z 4 Tv b für alle rationalen (q+w)' q E (-1,1) und b E (1,m) beweist man die Relation (B) durch Induktion über die Länge von w. Für w = A ist (B) trivial. Angenommen, (B) gilt für w. Dann folgt lim n -l I4w(z(n))I = 2-1141. Also ist die Zusatzvorn aussetzung (3) erfüllt, und es folgt lnm n -l s(zw(n)) = 1/2. Somit gilt die Relation (B) für w1 und wO, q.e.d. Die Eigenschaft einer Zufallsfolge, Bernouillifolge zu sein, hat sich damit als eine besonders wichtige Zufallseigenschaft herausgestellt. Denn wenn eine Folge z nicht Bernouillifolge ist, dann gibt es eine Vermögensfunktion V und ein festes n E N, so daß V(xa)/V(x) nur von den letzten n Gliedern von xa abhängt und V(z(n)) exponentiell wächst. Bemerkung (10.4) Aufgrund der Beweise zu (10.1) und (10.3) kann die Formulierung "für alle rationalen q und b mit q E (-1,1), b E (1,oo)" stets er-setzt werden durch die Formulierung "für alle rationalen q E B und b E B", wobei B c (-1,1) und B c (1,es) beliebige Mengen berechenbarer Zahlen sind, so daß B 0 (0,1) und B 0 (-1,0) in 0 und B in 1 einen Häufungspunkt haben. 11. Invarianzeigenschaften von Zufallsfolgen In diesem Paragraph zeigen wir, daß diejenigen Invarianzeigenschaften der hyperzufälligen Folgen, die im intuitiven Sinne effektiv sind, gerade Invarianzeigenschaften von Zufallsfolgen darstellen. Das heißt, jede partielle, berechenbar stetige, maßbeschränkte Funktion führt Zufallsfolgen wieder in Zufallsfolgen über (11.1). Auch die partiellen, subberechenbar stetigen Funktionen bilden, sofern man von ihnen noch die strengere Eigenschaft der Maßinvarianz verlangt, Zufallsfolgen wieder in solche ab. Schließlich geben wir einige Beispiele von Inva- rianzeigenschaften von Zufallsfolgen an. Satz (11.1) Sei H.: Xco -• Xco, eine partielle, berechenbar stetige, maßbeschränkte Funktion, dann gilt Hh(R n D(Hh)) c R. In Analogie zum Beweis von Satz (6.5) genügt es, folgendes Lemma zu zeigen. Lemma (11.2) oo m Sei ! c X°° eine total rekursive Nullmenge und Hh: X -• X eine partielle, berechenbar stetige, maßbeschränkte Funktion. Dann ist H-1(T) ebenfalls eine total rekursive Nullmenge. Beweis: Die total rekursive Nullmenge T sei durch den total rekursiven Sequentialtest Y c N x X* gegeben, Hh sei durch die rekursive, monotone Funktion H: X* -. X* und die Ordnungsfunktion h: N N gegeben. Für das feste k E N gelte für alle meßbaren A c r: Rh-1(A) S k (A). Den total rekursiven Sequentialtest Y zu Hh-1(R) definiere man wie folgt: _ ixi h(n) IH(x)I a n Yi = fx E H-1(Yi+kX*) I 1 f.a. n E N -a4- Es ist klar, daß i ein rekursiver Sequentialtest ist mit Hn 1(7t) c %Y (vergleiche hierzu den Beweis zu (6.6)). Es bleibt zu zeigen, daß Y total rekursiv ist. O.B.d.A. können wir annehmen, daß Yi n YiXX* = 0 (i E N). Dann gilt lim [Yi f1 XnX*] = O. Um [Yi] bis auf 2-n zu berechnen, gehe man n wie folgt vor. Man bestimme ein m E N, so daß [Yi+k n XmX*] s 2-k2-m. Dann kann man die endliche Menge Ai,m déf Yi f [xi lxl s h(m)) effektiv bestimmen. Es folgt leicht, daß CAi,m] - [Yi]~s 2-m. Somit kann man µ[Yi] gleichförmig für alle i berechnen, q.e.d. Wir interessieren uns nun für subberechenbar stetige, partielle Funktionen X° -. Xm, so daß H(z) für alle Zufallsfolgen z definiert ist, d.h. R c D(H). Diese Eigenschaft läßt sich für alle partiellen, sb. s. Funktionen H relativ unabhängig von R formulieren: Satz (11.3) Für jede partielle, subberechenbar stetige Funktion H: Xm X° ist R c D(H) äquivalent zu D(H) = 1. Beweis: (I) Wegen (R) = 1 folgt aus R c D(H), daß µ D(H) = 1. (II) Sei nun D(H) = 1. H werde von der rekursiven, monotonen Funktion H: X* X* erzeugt. Wir definieren: An = [x E D(H) i 1H(x)I n). An ist rekursiv aufzählbar,und wegen D(H) = 1 folgt µ[An] = 1. Als nächstes zeigen wir, daß Xe0 - [An] eine total rekursive Nullmenge ist. Man kann eine rekursive Menge Bn c N x X* mit folgenden Eigenschaften konstruieren: (1) Bin c X* ist endlich, µ[Bin] > 1 - 21 (i E N), (2) An = U Bi iEN Zu Bin kann man eine rekursive Menge Cnc N x X* konstruieren, so daß Cin c X* endlich, [Cin] = Xm - [Bin] (i E N). Damit ist Cn ein total rekursiver Sequentialtest. Wegen Xm - [A_] c /1 [B.n] ist Xe0 - [An] eine total rekursive Null-re iEN 1 n menge. Damit ist auch Xm - D(H) = U (XW - [An]) nE N eine total rekursive Nullmenge. Somit folgt R c D(H), q.e.d. Nun betrachten wir partielle, subberechenbar stetige Funktionen, die maßinvariant sind. Eine partielle Funktion H: Xe0 -. Xe0 heiße map-invariant, wenn µ H-1(A) = µ(A) für alle meßbaren A c Xe0. Damit gilt insbesondere 5'1(x-) = 1. Aufgrund von Satz (11.3) folgt damit für jede partielle, subberechenbar stetige, maßinvariante Funktion H: X°° -" Xe0, daß R c D(H). Es ergibt sich nun eine weitere Klasse von Invarianzeigenschaften von Zufallsfolgen. Satz (11.4) Für jede partielle, subberechenbar stetige, maßinvariante Funktion H: Xm -. Xe0 gilt H(R) c R. In Analogie zu den Beweisen der Sätze (6.5) und (11.1) folgt der Satz sofort aus dem Lemma (11.5) Sei 7t c Xe0 eine total rekursive Nullmenge und H: Xe0 ~ Xe0 eine partielle, subberechenbar stetige und maßinvariante Funktion. Dann ist R-1(%) ebenfalls eine total rekursive Nullmenge. - - Beweis: Sei Y c N x X* ein total rekursiver Sequentialtest zu R. g sei durch die rekursive, monotone Funktion H: X* X* gegeben. Dann wird offensichtlich durch Yi = H-1(YiX*) (i E N) ein rekursiver Sequentialtest definiert mit g-1(M) c RY (vergleiche den Beweis zu (6.6)). Wir zeigen, daß Y total rekursiv ist. Es gilt: u[Yi] =µCH-1(YiX*)]. und wegen H-1[Yi] = [H-1(YiX*)] n D(H) und D(H) = 1 folgt weiter µCYi] = µ H-1CYi] = [Yi]. Wegen µ[Y1] = µ[Yi] ist Y total rekursiv, q.e.d. Beispiele für Invarianzeigenschaften von Zufallsfolgen 111 Sei q: X* [0,1) eine rekursive Auswahlfunktion und h: N N eine rekursive Funktion. cp erzeugt eine rekursive, monotone Funktion (1): X* -. X*. Die hiervon erzeugte partielle Funktion Th: ist berechenbar stetig und maßverkleinernd. stellt somit eine Inva- rianzeigenschaft für Zufallsfolgen bzgl. jeder Verteilung µ dar. Das folgende Beispiel sei ohne vollständigen Beweis angegeben. 121 LOVELAND [ 24] schlug vor, den Begriff der Auswahlregel zu er-weitern, indem man die Auswahl von Gliedern nicht an die Reihenfolge bindet, mit der diese Glieder in der vorgegebenen Folge auftreten. Um die Maßinvarianz der so erzeugten Funktion g: zu sichern, muß man darauf achten, daß die Auswahl eines Gliedes stets ohne sein Ansehen erfolgt, also unabhängig vom Glied selbst ist. Wir formalisieren einen solchen Typ von Stellenauswahlen. Zu z E X~ und n E N bezeichne: z[n] = z1z2 ... zn_1zn+1zn+2 E r.Einer rekursiven Funktion h: X* - N - [0) ordnen wir wie folgt eine Abbildung H: Xm X~ zu. H(z) = y werde zusammen mit der Folge (zili E N) mit z1 E X'0 konstruiert: z0 = z zi+1 = zi[h(y(i))]. y(i+1) = y(i) zh(y(i))' y(i) besteht aus den i ersten von z ausgewählten Gliedern. zi entsteht aus z durch Entfernen der i ersten ausgewählten Glieder. Die Auswahl des nächsten Gliedes hängt dabei nur von den bereits ausgewählten Gliedern ab. Somit ist die Auswahl eines Gliedes unabhängig von dem betreffenden Glied selbst. Dies führt dazu, daß die durch g(z) = y definierte Funktion q: X° - X- mapinvariant bezüglich jedes Produktmaßes ist. Weil h rekursiv ist, muß g nach Konstruktion be-rechenbar stetig sein. 131 Die Zusammensetzung HhH der Abbildungen Hh von Beispiel I1~ und g von Beispiel 121 entsprechen gerade denjenigen verallgemeinerten Auswahlregeln nach LOVELAND, die berechenbar stetige, partielle Transformationen von X liefern. 141 Die Funktion g: die alle Einsen durch Nullen und alle Nullen durch Einsen ersetzt, ist berechenbar stetig. Sie ist maßinvariant für das Produktmaß zur Gleichverteilung auf X. In Paragraph 3 benutzten wir das folgende Beispiel einer partiellen, sb, s., mapinvarianten Funktion zur Charakterisierung der Bernouillifolgen: 151 Sei cpw: X* - [0,1) diejenige rekursive Auswahlregel mit 1 v E X*w 0 sonst. pw erzeugt eine rekursive, monotone Funktion 4w: X* ~ X*. Die hiervon erzeugte Funktion Tw : Xe' ist partiell. Aufgrund des starken w(v) = Gesetzes der großen Zahlen gilt µ D(~iw) = 1, und daraus folgt, daß ~w maßinvariant bzgl. jedes Produktmaßes ist. 161 Es sei f: X* x Xn Xn eine rekursive Funktion, so dap für jedes y E X* die einstellige Funktion f(y,*): Xn Xn eine Permutation von Xn liefert. H: X* X* werde folgendermaßen definiert: H/xn = f(A,*). Zu y1,y2,..,yk E Xn definiere man rekursiv: H(yly2...yk) = H(Y1Y2...yk_1) f(y1y2...yk_1,yk). H ist rekursiv und monoton, somit ist H: berechenbar stetig. H ist maßinvariant bezüglich des Produktmaßes zur Gleichverteilung auf X. 171 Sei H: X* -. X* eine Funktion, für die es eine Funktion 4): Xn - X* gibt mit H(xy) =1)(x)Y (x E Xn, y E x*)• Dann ist berechenbar stetig und maßbeschränkt bzgl. jedes Produktmaßes mit 0 < µ(x) < 1 für alle x E X. 12. Charakterisierung der Zufallsfolgen durch Invarianzeigenschaften Wir wollen in diesem Paragraph zeigen, daß man Zufallsfolgen durch ihre Invarianzeigenschaften charakterisieren kann. Somit ergibt sich ein weiterer Zugang zum Begriff der Zufälligkeit. Die entsprechende Definition schließt sich eng an den ursprünglichen VON MISES'schen Ansatz an. Diesen kann man wie folgt aussprechen. Eine Folge z ist genau dann ein Kollektiv, wenn alle unendlichen Folgen, die aus ihr durch Auswahlregeln gebildet werden können, das starke Gesetz der gropen Zahlen erfüllen. Wir zeigen nun, daß eine Folge z genau dann zu-fällig in unserem Sinne ist, wenn H(z) für jede berechenbar stetige, maßinvariante Transformation TT: X° ~ X'° das starke Gesetz der großen Zahlen erfüllt. Zum Beweis benutzen wir den Satz (12.1) Sei Mv f eine total rekursive Nullmenge der Ordnung f. Dann gibt es eine berechenbar stetige, maßinvariante Funktion ff: X~ ~ X'', so daß kein z E H(2v,f) das starke Gesetz der großen Zahlen erfüllt. Beweis: O.B.d.A. nehmen wir an, dap V: X* ~ Q+ rekursiv ist. Es sei r > 3 und g: N -. N eine Ordnungsfunktion, so da.ß f g(n) > V(A) 2rn (n E N). Ferner sei g streng monoton. Man sieht nun leicht, daß man eine re-kursive, monotone Funktion H: X* - X* mit folgenden Eigenschaften konstruierenkann. Vorab gelte H(Xg(n)) c xn; ferner (a) und (b): (a) II H-1(x) n xg(n) II = 2g(n)-n (x E xn). ( II II bedeute hier die Kardinalzahl einer Menge.) (b) Für alle y E Xg(n+1) mit max V(y(i)) > V(A) 2n+1 gilt isg(n+1) -90- H(y) = H(y(g(n))) 1. Hierzu müssen wir lediglich nachweisen, daß die Eigenschaft (b) nicht mit der Eigenschaft (a), welche die Maßinvarianz von g sichert, und der Monotonie von H in Konflikt gerät. Daher darf es zu einem x E Xn höchstens 2g(n+1)-n-1 Worte y E Xg(n+1) geben mit H(y(g(n))) = x und max V(y(i)) > V(A) 2n+1. isg(n+1) Aus dem Lemma (5.5) folgt aber unmittelbar folgende schärfere Abschät- zung: II [y E Xg(n+1) I max V(y(i)) > V(A) 2n+1} 0 s 2g(n+1)-n-1 ig(n+1) Es bleibt zum Beweis von (12.1) noch zu zeigen, daß für kein Y n z E 2(22 f) die Relation Um ri-1 ' z1 . = 1/2 erfüllt ist. Es sei n i=1 z = 2(y) mit T V(y(n)) f(n)-1 > O. Wegen f g(n) > V(A) 2rn (n E N) n mit r > 3 gibt es unendlich viele n, so daß max V(y(i)) > V(A) 23n. isg(n) Damit gibt es unendlich viele n mit max V(y(i)) > V(A) 2° (n s j s 3n). isg(j) Daraus folgt, daß es unendlich viele n gibt, so daß die letzten 2 n Glieder von H(y(g(3n))) E X3n nur aus Einsen bestehen. Das bedeutet, daß 2(y) das starke Gesetz der großen Zahlen nicht erfüllt. Aus (12.1) folgt zusammen mit (11.5) der - 91 - Satz (12.2) Eine Folge ist genau dann zufällig, wenn 2(z) für jede berechenbar stetige, maßinvariante Funktion 2: X~ -. Xm das starke Gesetz der großen Zahlen erfüllt. Beweis: (I) Wenn z nicht zufällig ist, dann liegt z in einer total rekursiven Nullmenge R. Dann gibt es nach (12.1) eine b.s., maßinvariante Funktion 2: XW f, so daß 2(z) das starke Gesetz der gropen Zahlen nicht erfüllt. (II) Die Umkehrung folgt aus (11.5). Bemerkung: Mit etwas Mehraufwand zeigt man [40 ], daß man in (12.2) das starke Gesetz der gropen Zahlen durch ein beliebiges Zufallsgesetz 2 ersetzen kann, für das es einen total rekursiven Sequentialtest Y gibt mit TY c 2 und so daß 2y dicht in Xm ist. ]R1 sei die Menge der partiellen, berechenbar stetigen, maßbeschränkten Funktionen 2: X" ~ r. 22 sei die Menge der partiellen, berechen- bar stetigen, maßverkleinernden Funktionen 2: X~ X°°. D3 sei die Menge der partiellen, subberechenbar stetigen, maßinvarianten Funktionen 2: Xm r. Il4 sei die Menge der berechenbar stetigen, mapinvarianten Funktionen 2: Wir haben folgenden Satz bewiesen: Satz (12.3) Für i = 1,2,3,4 gilt folgendes: Eine Folge z E X~ ist genau dann zu-fällig, wenn für jede Funktion 2 E 2i mit z E D(2) die Folge 2(z) das starke Gesetz der großen Zahlen erfüllt. - 3 - 13. Einige modifizierte Spielsysteme In diesem Paragraph charakterisieren wir Zufallsfolgen durch berechenbare Supermartingale. Wir untersuchen, ob eine Beschränkung der Einsatzfunktionen die Gewinnmöglichkeiten eines Spielers auf Lange Sicht einschränken. Ferner behandeln wir Spiele, in denen es erlaubt ist, Schulden zu machen. In den vorangehenden Paragraphen war eine Vermögensfunktion V: X* R eine Funktion mit (M) V(x) = 1/2(V(xO) + V(x1)) (x E X*). Den Begriff des Ma.rtingals kann man abschwächen, indem man nur noch fordert (SM) F(x) z 1/2(F(x0T + F(xl)) (x E X*). Eine Funktion F: X* - R mit (SM) nennt man ein Supermartingal. Das Zustandekommen eines Supermartingals kann man sich so vorstellen, daß F das Vermögen in einem Spiel angibt, in dem die Auszahlungsbedingungen zugunsten der Bank verändert wurden. D.h. die Bank schöpft vom Vermögen des Spielers zusätzlich ab. Den Satz (9.6) kann man nun leicht erweitern: Satz (13.1) Eine Folge z ist genau dann zufällig, wenn es kein berechenbares Supermartingal F: X* - R+ gibt mit k' F(z(n)) = . n Hierzu übertragen wir zunächst Lemma (9.3) auf Supermartingale. Lemma (13.2) Zu einem gegebenen, berechenbaren Supermartingal F: X* und n E N kann man stets ein rekursives Supermartingal X* Q+ konstruieren mit F(x) a F(x) und IF(x) - F(x)I s 2-n für alle x E X*. Beweis: Man kann rekursive Funktionen fi: X* Q, i = 0,1 so konstruieren, daß für alle x: Ifi(x) - V(x) + V(xi)I s 2-n-3 2-Ixl, f0(x) + f1(x) s O. F(A) E berechne man so, dap IF(A) + 2-n-1 - F(A)l s 2-n-2. Dann be-rechne man F rekursiv durch F(xi) =-P(x) + fi(x) (x E X*). F erfüllt (SM) und hat die gewünschten Eigenschaften. Zu einer Funktion H: X* -" R definieren wir die Differenz A H: XI* R durch A H(xa) = H(xa) - H(x) (x E X*, a E X). Zum Beweis von (13.1) zeigen wir nun folgendes Lemma, das auch weiterhin noch nützlich ist. Lemma (13.3) Zu einem gegebenen rekursiven Supermartingal F: X* Q+ kann man stets ein rekursives Martingal V: X* - Q+ so konstruieren, daß F(A) = V(A), A V(xa) x A F(xa), IA V(xa)I = max (A F(xO), A F(xl),0) für x E X*, a E X. Beweis: V berechne man rekursiv wie folgt: V(A) = F(A). V(xa) = V(x) + A F(xn), falls A F(xa) a O. Falls A F(xa) < 0, setze man (es sei a = 1 und T = 0): V(xa) = V(x), falls A F(xâ) s 0 V(xa) = V(x) - A F(xâ), falls A F(xa) > O. Ja - -95- Man verifiziert leicht, daß V eine Vermögensfunktion der gesuchten Art ist. Es gilt V(x) F(x) (x E X*), und hieraus folgt der Satz (13.1) Im allgemeinen ist es in Spielbanken üblich, den maximalen Einsatz pro Spielrunde zu beschränken. Es erhebt sich die Frage, ob davon die Gewinnaussichten der Spieler betroffen werden. Es gilt der Satz (13.4) Zu einer g