Randomness and probability. An algorithmic foundation of probability theory

From MaRDI portal





Dies Buch gibt eine ausfihrliche und leicht lesbare Darstellung der Theorie der Zufallsfolgen so weit sie bisher entwickelt worden ist. Der Verf. schreibt: \glqq 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 Misessche 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älizgkeit führen.\grqq{} Diesem Programm folgend, gibt Verf. in den ersten zwei Kapiteln die historische Entwicklung von den ersten von Misesschen Kollektiven bis zu Martin-Löfs rekursiven Sequentialtests. Dabei strebt er nach einer Synthese der verschiedenen Zufälligkeitsbegriffe. Die Hauptschwierigkeit, der man in der Theorie begegnet, ist die Charakterisierung der Zufallsfolgen (möglichst derart, daß alle \glqq Fast-überall-Gesetze\grqq{} der Wahrscheinlichkeitstheorie erfullt werden). Die Fast-überall-Gesetze wurden von Martin-Löf in der Form von rekursiven Sequentialtests gegeben. Die zugehörigen Zufallsfolgen werden hier \glqq hyperzufällige Folgen\grqq{} und die zugehörigen Nullmengen \glqq rekursive Nullmengen genannt. In Kapitel 2 werden die hyperzufälligen Folgen auch durch das Prinzip vom ausgeschiossenen Spielsystem und durch Invarianzeigenschaften charakterisiert. Verf. äuBert aber mehrere Einwände gegen die Martin-Löfsche Zufälligkeit, z.B. \glqq Die Definition des rekursiven Sequentialtests liefert keinen Hinweis, wie das entsprechende Fast-überall-Gesetz an einer vorgegebenen Folge effektiv nachzuprifen ist\grqq{} und wenn eine Folge (0)-zufällig genannt wird, wenn sie jeden 0-Test erfüllt, so gibt es (wie hier gezeigt wird) 0-zufällige Folgen, die nicht hyperzufällig sind. In früheren Arbeiten, deren Ergebnisse hier zusammenfassend wiedergegeben sind, und in diesem Buch (Kapitel 3 und 4) hat der Verf. die Begriffe \glqq total rekursiv\grqq{}, \glqq total rekursive Nullmenge\grqq{} und \glqq total rekursiver Sequentialtest\grqq{} eingeführt. Eine Folge heißt zufällig, wenn sie in keiner total rekursiven Nullmenge enthalten ist. Diese Zufallstests werden effektiv genannt, weil sie in dem Sinne effektiv sind, daß man nachprüfen kann, ob das entsprechende Fast-überall-Gesetz an einer vorgegebenen Folge (in asymptotischer Weise) erfüllt ist. Es wird dann gezeigt, daß die früheren verschiedenen Charakterisierungen der hyperzufälligen Folgen äquivalente Definitionen liefern, wenn man sich auf diejenigen Zufallstests beschränkt, die effektiv sind. Die Programmkomplexität nach Kolmogoroff wird in eine \glqq effektive Programmkomplexität\grqq{} überführt und die Zufallsfolgen werden dadurch charakterisiert. Hauptsächlich werden binäre Zufallsfolgen behandelt, aber zum Schluß werden auch allgemeinere Folgen betrachtet und es wird dann gezeigt, daß eine Wahrscheinlichkeitstheorie, die auf dem Zufallsbegriff gegründet ist, zu den Kolmogoroffschen Axiomen in einer konstruktiven Form führt.





Cited in
(only showing first 100 items - show all)








This page was built for publication: Randomness and probability. An algorithmic foundation of probability theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2550943)