Pages

Friday, November 2, 2012

Zufälligkeit und algorithmische Komplexität

Richard von Mises
(by Konrad Jacobs)
Hier noch mal ein aus der Mottenkiste hervorgeholter Artikel aus meinem Leben als philosophisch Interessierter Wahrscheinlichkeitstheoretiker. 

Mit der intuitiv einleuchtenden Idee, Zufälligkeit als den höchsten Grad möglicher Irregularität zu beschreiben, hatte sich schon Richard von Mises in den 20er Jahren des 20. Jahrhunderts beschäftigt. Auf seinen Grundlagen beschäftigte sich eine ganze Reihe von bedeutenden Mathematikern und Philosophen mit dieser nicht maßtheoretisch begründeten Axiomatik der Wahrscheinlichkeitstheorie. In einem kurzen Essay habe ich diese Entwicklung im Rahmen meiner Diplom-Arbeit beschrieben. 

Download des Essays

Anbei der weniger formellastige Teil des Essays. 


Schon vor der maßtheoretischen Begründung der Wahrscheinlichkeitstheorie durch Kolmogorov in seinem 1933 erschienen Klassiker Grundbegriffe der Wahrscheinlichkeitsrechnung gab es Ansätze von Richard von Mises in Wahrscheinlichkeit, Statistik und Wahrheit (1928) das sechste von Hilberts Jahrhundertproblem - nämlich die mathematische Axiomatisierung der Wahrscheinlichkeitslehre - aus der Unmöglichkeit einer algorithmischen Beschreibung einer zufälligen Folge von 0ern und 1ern zu lösen. Von Mises Ansatz scheiterte zwar, wie Ville 1939 zeigen konnte. 

In von Mises Nachfolge konnten jedoch Abraham Wald (1936), Alonzo Church (1940), Kolmogorov (1963) und schlussendlich Martin-Löf (1966) die grundsätzlichen Ideen zur modernen algorithmischen Theorie des Zufalls zusammenfügen. Schnorr (1971) hat zudem mit Grundgedanken von Ville, Brouwer und dem Ergebnis von Martin-Löf eine zur Church'schen These anologe These zur Äquivalenz aller Stochastizität beschreibenden Theorien aufgestellt. 

Die Zufälligkeit einer Folge von 0ern und 1ern (wir nennen sie von nun an Bernoulli-Folge) wird dabei von Martin-Löf als ein Maß ihrer Irregularität gesehen. Kolmogorov hatte die Irregularität einer Bernoulli-Folge als die Länge der kürzest möglichen Beschreibung der Folge definiert. Die Beschreibung einer Folge wird gedeutet als Turing-Maschine, die die Folge reproduziert. Mittels einer universellen Turing-Maschine lässt sich dann eine bis auf Isomorphie eindeutige Skala der Irregularität von Bernoulli-Folgen definieren. Ist die minimale Länge der Beschreibungen unendlich, nennen wir die Folge zufällig. 


Tatsächlich ist eine stochastische Folge von unabhängigen identisch verteilten Bernoulli-Variablen in diesem Sinne zufällig: Gäbe es eine die Folge reproduzierende Turing-Maschine, dann existiert nach der Berechenbarkeitstheorie eine rekursive Funktion f, die sich wiederum als endliche Binärfolge (a0,...,an) für ein n aus N schreiben lässt und so wählbar ist, dass nach spätestens 2^n Gliedern der Folge die 2^n+1 Stelle berechenbar wäre. Das aber verstößt gegen die Unabhängigkeit der Folgenglieder oder anders ausgedrückt - um die Referenz zur Arbeit von Ville herzustellen: Es existiert ein Spielsystem mit positiver Gewinnmöglichkeit ohne Verlustrisiko. In der Finanzmathematik ist man an dieser Stelle am zentralen Begriff der Arbitragemöglichkeit angelangt.Die Folge ist also kein Martingal, was im Widerspruch zur Voraussetzung steht. 

In von Mises ursprünglichem Ansatz war die Idee enthalten, dass die relative Häufigkeit des Vorkommens von 1ern in einer Bernoulli-Folge invariant unter der Beschränkung auf eine deterministisch ausgewählte Teilfolge sein sollte. Ville hatte gezeigt, dass die dadurch definierte Klasse von Folgen (die von Mises Kollektive nannte) mitnichten identisch ist mit der Klasse der etwa maßtheoretisch definierten tatsächlichen Zufallsfolgen. Als Randbemerkung sei erwähnt, dass Borel zeigte, dass fast alle Zahlen normal sind, d.h. die relative Häufigkeit der Ziffern in der g-adischen Entwicklung der Zahl genau 1/g beträgt, für alle g. 


Doch auch normal sein ist kein hinreichendes Kriterium für Zufälligkeit. Ville konstruierte nach Mises Theorie ein Kollektiv, dass dem Gesetz des iterierten Logarithmus widersprach. Damit rührte er ein grundsätzliches Problem der Irregularitätsdefinition von Zufälligkeit an. Wir nennen eine Eigenschaft A nach Schnorr ein Fastüberallgesetz, wenn eine (total) rekursive Nullmenge existiert, so dass die Eigenschaft auf alle Bernoulli-Folgen außerhalb dieser Nullmenge zutrifft. Dabei ist eine total rekursive Nullmenge eine Teilmenge einer über einen total rekursiven Sequentialtest ermittelten Ausnahmemenge. Ein total rekursiver Sequentialtest wiederum ist eine Folge von rekursiven Tests (im Church'schen Sinne), die die zu untersuchende Eigenschaft approximativ an den ersten k Folgengliedern überprüft. 

Es handelt sich also verkürzt gesprochen um ein berechenbarkeitstheoretisches Likelihood-Prinzip. Fastüberallgesetze sind beispielsweise das Gesetz der Großen Zahl oder das Gesetz des iterierten Logarithmus. Es ist klar, dass die Menge der Fastüberallgesetze abzählbar ist, da in einem System definierte Gesetze immer nur eine endliche Folge über einem abzählbaren Alphabet darstellen und rekursiv definiert sein müssen. Die Vereinigung zweier total rekursiver Nullmengen ist selbstverständlich wieder eine total rekursive Nullmenge. Die Vereinigung aller total rekursiver Nullmengen von Bernoulli-Folgen jedoch ist nicht mehr total rekursiv und steht daher keinem Fastüberallgesetz mehr gegenüber. 

Das beweist man mit einem klassischen Gödel-Trick. Es lässt sich zeigen, dass zu jeder total rekursiven Nullmenge eine rekursive Folge im Komplement existiert. Zufallsfolgen sind aber per Definition nicht rekursiv. Da die Zusammenfassung aller Fastüberallgesetze aber der Irregularitätsdefinition von Zufallsfolgen entspricht, bedeutet das, dass die Menge aller total rekursiven Sequentialtests nicht rekursiv aufzählbar sein kann. Schnorr konnte zeigen, dass andere Definitionen von Zufälligkeit, wie etwa die Charakterisierung durch das Prinzip des ausgeschlossenen Spielsystems oder via Invarianzeigenschaften von Zufallsfolgen zu äquivalenten Ergebnissen führen. Eine Zusammenfassung zu dieser Thematik mit geschichtlichen Hintergründen findet sich etwa bei Martin-Löf und Vovk. 
Post a Comment